Sumegha Garg

According to our database, Sumegha Garg authored at least 24 papers between 2016 and 2026.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2026

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures.

Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, Vatsal Sharan

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Online Learning with Limited Information in the Sliding Window Model.

Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

Query Lower Bounds for Correlation Clustering Under Memory Constraints.

Sumegha Garg, Songhua He, Periklis A. Papakonstantinou

Proceedings of the 17th Innovations in Theoretical Computer Science Conference, 2026

2025

The Space Complexity of Learning-Unlearning Algorithms.

Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty

CoRR, June, 2025

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes.

Sumegha Garg, Akash Sengupta

Electron. Colloquium Comput. Complex., 2025

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes.

Sumegha Garg, Akash Kumar Sengupta

Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science, 2025

Testing Tensor Products of Algebraic Codes.

Sumegha Garg, Madhu Sudan, Gabriel Wu

Proceedings of the Approximation, 2025

2024

A New Information Complexity Measure for Multi-pass Streaming with Applications.

Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Oracle Efficient Online Multicalibration and Omniprediction.

Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2021

Tight Space Complexity of the Coin Problem.

Mark Braverman, Sumegha Garg, Or Zamir

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Memory-Sample Lower Bounds for Learning Parity with Noise.

Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz

Proceedings of the Approximation, 2021

2020

Implications of Space-Bounded Computation

Sumegha Garg

PhD thesis, 2020

Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs.

Mark Braverman, Gil Cohen, Sumegha Garg

SIAM J. Comput., 2020

The Role of Randomness and Noise in Strategic Classification.

Mark Braverman, Sumegha Garg

Proceedings of the 1st Symposium on Foundations of Responsible Computing, 2020

The Coin Problem with Applications to Data Streams.

Mark Braverman, Sumegha Garg, David P. Woodruff

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG.

Sumegha Garg, Pravesh K. Kothari, Ran Raz

Proceedings of the Approximation, 2020

2019

The Space Complexity of Mirror Games.

Sumegha Garg, Jon Schneider

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Tracking and Improving Information in the Service of Fairness.

Sumegha Garg, Michael P. Kim, Omer Reingold

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Time-Space Lower Bounds for Two-Pass Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Extractor-based time-space lower bounds for learning.

Sumegha Garg, Ran Raz, Avishay Tal

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Hitting sets with near-optimal error for read-once branching programs.

Mark Braverman, Gil Cohen, Sumegha Garg

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All.

Mark Braverman, Sumegha Garg, Ariel Schvartzman

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

New Security Notions and Feasibility Results for Authentication of Quantum Data.

Sumegha Garg, Henry Yuen, Mark Zhandry

Proceedings of the Advances in Cryptology - CRYPTO 2017, 2017

2016

Network coding in undirected graphs is either very helpful or not helpful at all.

Mark Braverman, Sumegha Garg, Ariel Schvartzman

CoRR, 2016