Sumegha Garg

41 papers A* 9A 5Journal 22Unranked 4
YearRankTypeTitle / Venue / Authors
2026 J jnl
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures.
CoRR
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, Vatsal Sharan
2026 A* conf
Online Learning with Limited Information in the Sliding Window Model.
SODA
Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
2026 J jnl
Online Learning with Limited Information in the Sliding Window Model.
CoRR
Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
2026 A conf
Query Lower Bounds for Correlation Clustering Under Memory Constraints.
ITCS
Sumegha Garg, Songhua He, Periklis A. Papakonstantinou
2025 A* conf
Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes.
FOCS
Sumegha Garg, Akash Kumar Sengupta
2025 J jnl
Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes.
Electron. Colloquium Comput. Complex.
Sumegha Garg, Akash Sengupta
2025 A conf
Testing Tensor Products of Algebraic Codes.
APPROX/RANDOM
Sumegha Garg, Madhu Sudan, Gabriel Wu
2025 J jnl
The Space Complexity of Learning-Unlearning Algorithms.
CoRR
Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty
2024 A* conf
A New Information Complexity Measure for Multi-pass Streaming with Applications.
STOC
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024 J jnl
A New Information Complexity Measure for Multi-pass Streaming with Applications.
CoRR
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024 A* conf
Oracle Efficient Online Multicalibration and Omniprediction.
SODA
Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth
2024 J jnl
Testing Tensor Products of Algebraic Codes.
CoRR
Sumegha Garg, Madhu Sudan, Gabriel Wu
2023 J jnl
Oracle Efficient Online Multicalibration and Omniprediction.
CoRR
Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth
2021 — conf
Memory-Sample Lower Bounds for Learning Parity with Noise.
APPROX-RANDOM
Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
2021 J jnl
Memory-Sample Lower Bounds for Learning Parity with Noise.
CoRR
Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
2021 A* conf
Tight Space Complexity of the Coin Problem.
FOCS
Mark Braverman, Sumegha Garg, Or Zamir
2021 J jnl
Tight Space Complexity of the Coin Problem.
Electron. Colloquium Comput. Complex.
Mark Braverman, Sumegha Garg, Or Zamir
2020 — —
Implications of Space-Bounded Computation
Sumegha Garg
2020 J jnl
Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs.
SIAM J. Comput.
Mark Braverman, Gil Cohen, Sumegha Garg
2020 A* conf
The Coin Problem with Applications to Data Streams.
FOCS
Mark Braverman, Sumegha Garg, David P. Woodruff
2020 J jnl
The Coin Problem with Applications to Data Streams.
Electron. Colloquium Comput. Complex.
Mark Braverman, Sumegha Garg, David P. Woodruff
2020 — conf
The Role of Randomness and Noise in Strategic Classification.
FORC
Mark Braverman, Sumegha Garg
2020 J jnl
The Role of Randomness and Noise in Strategic Classification.
CoRR
Mark Braverman, Sumegha Garg
2020 — conf
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG.
APPROX-RANDOM
Sumegha Garg, Pravesh K. Kothari, Ran Raz
2020 J jnl
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG.
CoRR
Sumegha Garg, Pravesh K. Kothari, Ran Raz
2019 A conf
The Space Complexity of Mirror Games.
ITCS
Sumegha Garg, Jon Schneider
2019 A conf
Time-Space Lower Bounds for Two-Pass Learning.
CCC
Sumegha Garg, Ran Raz, Avishay Tal
2019 J jnl
Time-Space Lower Bounds for Two-Pass Learning.
Electron. Colloquium Comput. Complex.
Sumegha Garg, Ran Raz, Avishay Tal
2019 A* conf
Tracking and Improving Information in the Service of Fairness.
EC
Sumegha Garg, Michael P. Kim, Omer Reingold
2019 J jnl
Tracking and Improving Information in the Service of Fairness.
CoRR
Sumegha Garg, Michael P. Kim, Omer Reingold
2018 A* conf
Extractor-based time-space lower bounds for learning.
STOC
Sumegha Garg, Ran Raz, Avishay Tal
2018 A* conf
Hitting sets with near-optimal error for read-once branching programs.
STOC
Mark Braverman, Gil Cohen, Sumegha Garg
2017 A conf
Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All.
ITCS
Mark Braverman, Sumegha Garg, Ariel Schvartzman
2017 J jnl
Extractor-Based Time-Space Lower Bounds for Learning.
CoRR
Sumegha Garg, Ran Raz, Avishay Tal
2017 J jnl
Extractor-Based Time-Space Lower Bounds for Learning.
Electron. Colloquium Comput. Complex.
Sumegha Garg, Ran Raz, Avishay Tal
2017 J jnl
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs.
Electron. Colloquium Comput. Complex.
Mark Braverman, Gil Cohen, Sumegha Garg
2017 — conf
New Security Notions and Feasibility Results for Authentication of Quantum Data.
CRYPTO (2)
Sumegha Garg, Henry Yuen, Mark Zhandry
2017 J jnl
New security notions and feasibility results for authentication of quantum data.
IACR Cryptol. ePrint Arch.
Sumegha Garg, Henry Yuen, Mark Zhandry
2017 J jnl
The space complexity of mirror games.
CoRR
Sumegha Garg, Jon Schneider
2016 J jnl
Network coding in undirected graphs is either very helpful or not helpful at all.
CoRR
Mark Braverman, Sumegha Garg, Ariel Schvartzman
2016 J jnl
New security notions and feasibility results for authentication of quantum data.
CoRR
Sumegha Garg, Henry Yuen, Mark Zhandry