Sumegha Garg

I am a PhD student in the Department of Computer Science at Princeton University. I am extremely fortunate to be advised by Mark Braverman. Before coming here, I finished my undergraduate studies in the Department of Computer Science and Engineering at Indian Institute of Technology, Delhi.

I am interested in Theoretical Computer Science, particularly in complexity theory, algorithmic fairness, information theory and quantum computing.


PC Member: ITCS 2020

Sumegha Garg,
35 Olden Street,
Princeton, NJ - 08540



sumeghag AT cs dot princeton dot edu
sumegha dot garg AT gmail dot com
Research Papers

The Role of Randomness and Noise in Strategic Classification

- with Mark Braverman. Learning in the Presence of Strategic Behavior (EC 2019 Workshop). [Workshop Version]

Time-Space Lower Bounds for Two-Pass Learning

- with Ran Raz and Avishay Tal. CCC 2019. [ECCC]

Tracking and Improving Information in the Service of Fairness

- with Michael Kim and Omer Reingold. EC 2019. [arXiv]

The Space Complexity of Mirror Games

- with Jon Schneider. ITCS 2019. [arXiv]

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs

- with Mark Braverman and Gil Cohen. STOC 2018. Invited to the SICOMP Special Issue for STOC 2018 [ECCC]

Extractor-Based Time-Space Lower Bounds for Learning

- with Ran Raz and Avishay Tal. STOC 2018. [ECCC]

Network Coding in Undirected Graphs is Either Very Helpful or Not Helpful at All

- with Mark Braverman and Ariel Schvartzman. ITCS 2017. Invited paper [arXiv]

New Security Notions and Feasibility Results for Authentication of Quantum Data

- with Henry Yuen and Mark Zhandry. QCrypt 2016. Crypto 2017. [arXiv]

Princeton University

IIT Delhi