Sumegha Garg

Publication Activity (10 Years)

Years Active: 2016-2024
Publications (10 Years): 32

Top Topics

Space Complexity

Continuous Data Streams

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
A New Information Complexity Measure for Multi-pass Streaming with Applications. STOC (2024)
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
A New Information Complexity Measure for Multi-pass Streaming with Applications. CoRR (2024)
Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth
Oracle Efficient Online Multicalibration and Omniprediction. SODA (2024)
Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth
Oracle Efficient Online Multicalibration and Omniprediction. CoRR (2023)
Mark Braverman, Sumegha Garg, Or Zamir
Tight Space Complexity of the Coin Problem. FOCS (2022)
Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
Memory-Sample Lower Bounds for Learning Parity with Noise. APPROX-RANDOM (2021)
Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
Memory-Sample Lower Bounds for Learning Parity with Noise. CoRR (2021)
Mark Braverman, Sumegha Garg, Or Zamir
Tight Space Complexity of the Coin Problem. FOCS (2021)
Mark Braverman, Sumegha Garg, Or Zamir
Tight Space Complexity of the Coin Problem. Electron. Colloquium Comput. Complex. 28 (2021)
Mark Braverman, Sumegha Garg, David P. Woodruff
The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. 27 (2020)
Sumegha Garg, Pravesh K. Kothari, Ran Raz
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. APPROX-RANDOM (2020)
Mark Braverman, Sumegha Garg, David P. Woodruff
The Coin Problem with Applications to Data Streams. FOCS (2020)
Mark Braverman, Gil Cohen, Sumegha Garg
Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs. SIAM J. Comput. 49 (5) (2020)
Sumegha Garg, Pravesh K. Kothari, Ran Raz
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. CoRR (2020)
Mark Braverman, Sumegha Garg
The Role of Randomness and Noise in Strategic Classification. CoRR (2020)
Mark Braverman, Sumegha Garg
The Role of Randomness and Noise in Strategic Classification. FORC (2020)
Sumegha Garg, Jon Schneider
The Space Complexity of Mirror Games. ITCS (2019)
Sumegha Garg, Michael P. Kim, Omer Reingold
Tracking and Improving Information in the Service of Fairness. EC (2019)
Sumegha Garg, Ran Raz, Avishay Tal
Time-Space Lower Bounds for Two-Pass Learning. Computational Complexity Conference (2019)
Sumegha Garg, Ran Raz, Avishay Tal
Time-Space Lower Bounds for Two-Pass Learning. Electron. Colloquium Comput. Complex. 26 (2019)
Sumegha Garg, Michael P. Kim, Omer Reingold
Tracking and Improving Information in the Service of Fairness. CoRR (2019)
Mark Braverman, Gil Cohen, Sumegha Garg
Hitting sets with near-optimal error for read-once branching programs. STOC (2018)
Sumegha Garg, Ran Raz, Avishay Tal
Extractor-based time-space lower bounds for learning. STOC (2018)
Sumegha Garg, Henry Yuen, Mark Zhandry
New security notions and feasibility results for authentication of quantum data. IACR Cryptol. ePrint Arch. 2017 (2017)
Sumegha Garg, Ran Raz, Avishay Tal
Extractor-Based Time-Space Lower Bounds for Learning. Electron. Colloquium Comput. Complex. 24 (2017)
Sumegha Garg, Jon Schneider
The space complexity of mirror games. CoRR (2017)
Mark Braverman, Gil Cohen, Sumegha Garg
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs. Electron. Colloquium Comput. Complex. 24 (2017)
Mark Braverman, Sumegha Garg, Ariel Schvartzman
Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. ITCS (2017)
Sumegha Garg, Henry Yuen, Mark Zhandry
New Security Notions and Feasibility Results for Authentication of Quantum Data. CRYPTO (2) (2017)
Sumegha Garg, Ran Raz, Avishay Tal
Extractor-Based Time-Space Lower Bounds for Learning. CoRR (2017)
Sumegha Garg, Henry Yuen, Mark Zhandry
New security notions and feasibility results for authentication of quantum data. CoRR (2016)
Mark Braverman, Sumegha Garg, Ariel Schvartzman
Network coding in undirected graphs is either very helpful or not helpful at all. CoRR (2016)