Mark Braverman

ORCID

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 124

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

FOCS

ITCS

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, Rotem Oshman, Tal Roth
Multi-Party Set Disjointness and Intersection with Bounded Dependence. PODC (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)
Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. CoRR (2024)
Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
Improved Monotonicity Testers via Hypercube Embeddings. ITCS (2023)
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
Parallel Repetition of k-Player Projection Games. CoRR (2023)
Mark Braverman, Subhash Khot, Dor Minzer
Parallel Repetition for the GHZ Game: Exponential Decay. FOCS (2023)
Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora
Understanding Influence Functions and Datamodels via Harmonic Analysis. ICLR (2023)
Mark Braverman, Dor Minzer
Rounding via Low Dimensional Embeddings. ITCS (2023)
Itai Ashlagi, Mark Braverman, Geng Zhao
Welfare Distribution in Two-sided Random Matching Markets. CoRR (2023)
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
Parallel Repetition of k-Player Projection Games. Electron. Colloquium Comput. Complex. (2023)
Itai Ashlagi, Mark Braverman, Geng Zhao
Welfare Distribution in Two-sided Random Matching Markets. EC (2023)
Mark Braverman, Subhash Khot, Dor Minzer
Parallel Repetition for the GHZ Game: Exponential Decay. Electron. Colloquium Comput. Complex. (2022)
Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. EC (2022)
Grace Guan, Mark Braverman
Empirical Characteristics of Affordable Care Act Risk Transfer Payments. CoRR (2022)
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
An Invariance Principle for the Multi-slice, with Applications. FOCS (2022)
Mark Braverman, Subhash Khot, Dor Minzer
Parallel Repetition for the GHZ Game: Exponential Decay. CoRR (2022)
Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
Improved Monotonicity Testers via Hypercube Embeddings. CoRR (2022)
Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran
Statistically Near-Optimal Hypothesis Selection. FOCS (2022)
Yufei Zheng, Xiaoqi Chen, Mark Braverman, Jennifer Rexford
Unbiased Delay Measurement in the Data Plane. APOCS (2022)
Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. CoRR (2022)
Mark Braverman, Sumegha Garg, Or Zamir
Tight Space Complexity of the Coin Problem. FOCS (2022)
Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
Optimal Short-Circuit Resilient Formulas. J. ACM 69 (4) (2022)
Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
Round-vs-Resilience Tradeoffs for Binary Feedback Channels. Electron. Colloquium Comput. Complex. (2022)
Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora
Understanding Influence Functions and Datamodels via Harmonic Analysis. CoRR (2022)
Mark Braverman, Dor Minzer
Rounding via Low Dimensional Embeddings. CoRR (2022)
Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
Near Optimal Distributed Learning of Halfspaces with Two Parties. COLT (2021)
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
An Invariance Principle for the Multi-slice, with Applications. CoRR (2021)
Mark Braverman
Optimization-friendly generic mechanisms without money. CoRR (2021)
Mark Braverman, Jon Schneider, S. Matthew Weinberg
Prior-free Dynamic Mechanism Design With Limited Liability. EC (2021)
Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao
Tiered Random Matching Markets: Rank Is Proportional to Popularity. ITCS (2021)
Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran
Statistically Near-Optimal Hypothesis Selection. CoRR (2021)
Mark Braverman, Dor Minzer
New Separations Results for External Information. CoRR (2021)
Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran
Statistically Near-Optimal Hypothesis Selection. FOCS (2021)
Mark Braverman, Jon Schneider, S. Matthew Weinberg
Prior-free Dynamic Mechanism Design With Limited Liability. CoRR (2021)
Mark Braverman, Subhash Khot, Dor Minzer
On Rich 2-to-1 Games. ITCS (2021)
Mark Braverman, Dor Minzer
Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. Computational Complexity Conference (2021)
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
An Invariance Principle for the Multi-slice, with Applications. FOCS (2021)
Mark Braverman, Dor Minzer
New separations results for external information. STOC (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)
Itai Ashlagi, Mark Braverman, Clayton Thomas, Geng Zhao
Tiered Random Matching Markets: Rank is Proportional to Popularity. CoRR (2020)
Mark Braverman, Dor Minzer
Optimal tiling of the Euclidean space using symmetric bodies. CoRR (2020)
Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang
Calibration, Entropy Rates, and Memory in Language Models. ICML (2020)
Mark Braverman, Sumegha Garg, David P. Woodruff
The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. 27 (2020)
Xiaoqi Chen, Shir Landau Feibish, Mark Braverman, Jennifer Rexford
BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time. SIGCOMM (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)
Mark Braverman, Elad Hazan, Max Simchowitz, Blake E. Woodworth
The Gradient Complexity of Linear Regression. COLT (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)
Itai Ashlagi, Mark Braverman, Yash Kanoria, Peng Shi
Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations. Manag. Sci. 66 (5) (2020)
Mark Braverman, Subhash Khot, Dor Minzer
On Rich $2$-to-$1$ Games. Electron. Colloquium Comput. Complex. 26 (2019)
Mark Braverman, Jieming Mao, Yuval Peres
Sorted Top-k in Rounds. COLT (2019)
Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility. CoRR (2019)
Mark Braverman, Brendan Juba
The Price of Uncertain Priors in Source Coding. IEEE Trans. Inf. Theory 65 (2) (2019)
Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang
Calibration, Entropy Rates, and Memory in Language Models. CoRR (2019)
Mark Braverman, Elad Hazan, Max Simchowitz, Blake E. Woodworth
The gradient complexity of linear regression. CoRR (2019)
Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
Multi-armed Bandit Problems with Strategic Arms. COLT (2019)
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
Reliable communication over highly connected noisy networks. Distributed Comput. 32 (6) (2019)
Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
On the Computational Power of Radio Channels. DISC (2019)
Mark Braverman, Jieming Mao, Yuval Peres
Sorted Top-k in Rounds. CoRR (2019)
Mark Braverman, Cristobal Rojas, Jonathan Schneider
Space-bounded Church-Turing thesis and computational tractability of closed systems. CoRR (2019)
Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
Optimal Short-Circuit Resilient Formulas. Computational Complexity Conference (2019)
Mark Braverman, Young Kun-Ko
Information Value of Two-Prover Games. ITCS (2018)
Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
Optimal Short-Circuit Resilient Formulas. CoRR (2018)
Mark Braverman, Gillat Kol
Interactive compression to external information. STOC (2018)
Mark Braverman, Gil Cohen, Sumegha Garg
Hitting sets with near-optimal error for read-once branching programs. STOC (2018)
Mark Braverman, Jieming Mao, S. Matthew Weinberg
On Simultaneous Two-player Combinatorial Auctions. SODA (2018)
Mark Braverman, Young Kun-Ko
Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. APPROX-RANDOM (2018)
Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
A Candidate for a Strong Separation of Information and Communication. ITCS (2018)
Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
Selling to a No-Regret Buyer. EC (2018)
Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM 65 (1) (2018)
Mark Braverman, Brendan Juba
The Price of Uncertain Priors in Source Coding. CoRR (2018)
Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette
Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness. SIAM J. Comput. 47 (6) (2018)
Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
Multi-armed Bandit Problems with Strategic Arms. CoRR (2017)
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
-Subgraph with Perfect Completeness. SODA (2017)
Itai Ashlagi, Mark Braverman, Yash Kanoria, Peng Shi
Communication Requirements and Informative Signaling in Matching Markets. EC (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)
Maria-Florina Balcan, Mark Braverman
Nash Equilibria in Perturbation-Stable Games. Theory Comput. 13 (1) (2017)
Mark Braverman, Klim Efremenko
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. SIAM J. Comput. 46 (1) (2017)
Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
Coding for Interactive Communication Correcting Insertions and Deletions. IEEE Trans. Inf. Theory 63 (10) (2017)
Mark Braverman, Jieming Mao, S. Matthew Weinberg
On Simultaneous Two-player Combinatorial Auctions. CoRR (2017)
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
Strategyproof Mechanisms for Competitive Influence in Networks. Algorithmica 78 (2) (2017)
Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
Selling to a No-Regret Buyer. CoRR (2017)
Mark Braverman, Young Kun-Ko
Information Value of Two-Prover Games. Electron. Colloquium Comput. Complex. 24 (2017)
Mark Braverman
Interactive Information Complexity. SIAM Rev. 59 (4) (2017)
Mark Braverman, Rotem Oshman
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. FOCS (2017)
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
Communication lower bounds for statistical estimation problems via a distributed data processing inequality. STOC (2016)
Mark Braverman, Omri Weinstein
A Discrepancy Lower Bound for Information Complexity. Algorithmica 76 (3) (2016)
Mark Braverman, Ran Gelles, Michael A. Yitayew
Optimal Resilience for Short-Circuit Noise in Formulas. Electron. Colloquium Comput. Complex. 23 (2016)
Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
Coding for Interactive Communication Correcting Insertions and Deletions. ICALP (2016)
Mark Braverman, Jon Schneider
Information Complexity Is Computable. ICALP (2016)
Mark Braverman, Jieming Mao, S. Matthew Weinberg
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. SODA (2016)
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
Reliable Communication over Highly Connected Noisy Networks. PODC (2016)
Mark Braverman, Jing Chen, Sampath Kannan
Optimal Provision-After-Wait in Healthcare. Math. Oper. Res. 41 (1) (2016)
Mark Braverman, Jieming Mao, S. Matthew Weinberg
Parallel algorithms for select and partition with noisy comparisons. STOC (2016)
Mark Braverman, Sumegha Garg, Ariel Schvartzman
Network coding in undirected graphs is either very helpful or not helpful at all. CoRR (2016)
Mark Braverman, Jieming Mao, S. Matthew Weinberg
Parallel Algorithms for Select and Partition with Noisy Comparisons. CoRR (2016)

Mark Braverman.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mark Braverman