Sumegha Garg

According to our database, Sumegha Garg authored at least 16 papers between 2016 and 2024.

Collaborative distances:

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

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

CoRR, 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

Electron. Colloquium Comput. Complex., 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

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

Mark Braverman, Gil Cohen, Sumegha Garg

SIAM J. Comput., 2020

The Coin Problem with Applications to Data Streams.

Mark Braverman, Sumegha Garg, David P. Woodruff

Electron. Colloquium Comput. Complex., 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

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

Time-Space Lower Bounds for Two-Pass Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Electron. Colloquium Comput. Complex., 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

2017

New security notions and feasibility results for authentication of quantum data.

Sumegha Garg, Henry Yuen, Mark Zhandry

IACR Cryptol. ePrint Arch., 2017

Extractor-Based Time-Space Lower Bounds for Learning.

Sumegha Garg, Ran Raz, Avishay Tal

Electron. Colloquium Comput. Complex., 2017

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

Mark Braverman, Gil Cohen, Sumegha Garg

Electron. Colloquium Comput. Complex., 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

2016

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

Mark Braverman, Sumegha Garg, Ariel Schvartzman

CoRR, 2016