E-LIB Suche - Ergebnisse für: Garg, Sumegha

1

A New Information Complexity Measure for Multi-pass Streami..:

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

Braverman, Mark ; Garg, Sumegha ; Li, Qian... - p. 1781-1792 , 2024

Link: https://dl.acm.org/doi/1..

2

Tight Space Complexity of the Coin Problem:

, In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS),

Braverman, Mark ; Garg, Sumegha ; Zamir, Or - p. 1068-1079 , 2022

Link: https://doi.org/10.1109/..

3

The Coin Problem with Applications to Data Streams:

, In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS),

Braverman, Mark ; Garg, Sumegha ; Woodruff, David P. - p. 318-329 , 2020

Link: https://doi.org/10.1109/..

4

Pseudorandom Pseudo-distributions with Near-Optimal Error f..:

Braverman, Mark ; Cohen, Gil ; Garg, Sumegha
SIAM Journal on Computing. 49 (2020) 5 - p. STOC18-242-STOC18-299 , 2020

Link: https://doi.org/10.1137/..

5

Time-space lower bounds for two-pass learning:

, In: Proceedings of the 34th Computational Complexity Conference,

Garg, Sumegha ; Raz, Ran ; Tal, Avishay - p. 1-39 , 2019

Link: https://dl.acm.org/doi/1..

6

Tracking and Improving Information in the Service of Fairne..:

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

Garg, Sumegha ; Kim, Michael P. ; Reingold, Omer - p. 809-824 , 2019

Link: https://dl.acm.org/doi/1..

7

Hitting sets with near-optimal error for read-once branchin..:

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

Braverman, Mark ; Cohen, Gil ; Garg, Sumegha - p. 353-362 , 2018

Link: https://dl.acm.org/doi/1..

8

Extractor-based time-space lower bounds for learning:

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

Garg, Sumegha ; Raz, Ran ; Tal, Avishay - p. 990-1002 , 2018

Link: https://dl.acm.org/doi/1..

9

Oracle Efficient Online Multicalibration and Omniprediction:

Garg, Sumegha ; Jung, Christopher ; Reingold, Omer.
http://arxiv.org/abs/2307.08999. , 2023

Link: http://arxiv.org/abs/230..

10

Memory-Sample Lower Bounds for Learning Parity with Noise:

Garg, Sumegha ; Kothari, Pravesh K ; Liu, Pengda.
http://arxiv.org/abs/2107.02320. , 2021

Link: http://arxiv.org/abs/210..

11

Memory-Sample Lower Bounds for Learning Parity with Noise:

Garg, Sumegha ; Kothari, Pravesh K ; Liu, Pengda.
doi:10.4230/LIPIcs.APPROX/RANDOM.2021.60. , 2021

Link: https://doi.org/10.4230/..

12

Time-Space Tradeoffs for Distinguishing Distributions and A..:

Garg, Sumegha ; Kothari, Pravesh K ; Raz, Ran
http://arxiv.org/abs/2002.07235. , 2020

Link: http://arxiv.org/abs/200..

13

The Role of Randomness and Noise in Strategic Classificatio:

Braverman, Mark ; Garg, Sumegha
doi:10.4230/LIPIcs.FORC.2020.9. , 2020

Link: https://doi.org/10.4230/..

14

The Role of Randomness and Noise in Strategic Classificatio:

Braverman, Mark ; Garg, Sumegha
http://arxiv.org/abs/2005.08377. , 2020

Link: http://arxiv.org/abs/200..

15

Time-Space Lower Bounds for Two-Pass Learning:

Garg, Sumegha ; Raz, Ran ; Tal, Avishay
Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019). , 2019

Link: https://doi.org/10.4230/..