


default search action
Mark Braverman
Person information
- affiliation: Princeton University, USA
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
- [c100]Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang:
Round-Vs-Resilience Tradeoffs for Binary Feedback Channels. ITCS 2025: 22:1-22:23 - [c99]Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc:
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. SODA 2025: 3029-3068 - 2024
- [c98]Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition of k-Player Projection Games. APPROX/RANDOM 2024: 54:1-54:16 - [c97]Mark Braverman, William Kuszmaul:
Tight Analyses of Ordered and Unordered Linear Probing. FOCS 2024: 606-635 - [c96]Mark Braverman
, Rotem Oshman
, Tal Roth
:
Multi-Party Set Disjointness and Intersection with Bounded Dependence. PODC 2024: 332-342 - [c95]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: 1781-1792 - [i102]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 abs/2403.20283 (2024) - [i101]Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc:
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. CoRR abs/2407.15285 (2024) - [i100]Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition for 3-Player XOR Games. CoRR abs/2408.09352 (2024) - [i99]Mark Braverman, Or Zamir:
Optimality of Frequency Moment Estimation. CoRR abs/2411.02148 (2024) - [i98]Mark Braverman, Or Zamir:
Optimality of Frequency Moment Estimation. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c94]Mark Braverman, Subhash Khot, Dor Minzer:
Parallel Repetition for the GHZ Game: Exponential Decay. FOCS 2023: 1337-1341 - [c93]Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora:
Understanding Influence Functions and Datamodels via Harmonic Analysis. ICLR 2023 - [c92]Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer:
Improved Monotonicity Testers via Hypercube Embeddings. ITCS 2023: 25:1-25:24 - [c91]Mark Braverman, Dor Minzer:
Rounding via Low Dimensional Embeddings. ITCS 2023: 26:1-26:30 - [c90]Itai Ashlagi
, Mark Braverman
, Geng Zhao
:
Welfare Distribution in Two-sided Random Matching Markets. EC 2023: 122 - [p1]Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. Logic, Automata, and Computational Complexity 2023: 261-318 - [i97]Itai Ashlagi, Mark Braverman, Geng Zhao:
Welfare Distribution in Two-sided Random Matching Markets. CoRR abs/2302.08599 (2023) - [i96]Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition of k-Player Projection Games. CoRR abs/2312.04783 (2023) - [i95]Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition of k-Player Projection Games. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j32]Mark Braverman
, Klim Efremenko
, Ran Gelles
, Michael A. Yitayew
:
Optimal Short-Circuit Resilient Formulas. J. ACM 69(4): 26:1-26:37 (2022) - [c89]Yufei Zheng, Xiaoqi Chen, Mark Braverman, Jennifer Rexford:
Unbiased Delay Measurement in the Data Plane. APOCS 2022: 15-30 - [c88]Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett:
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. EC 2022: 967-985 - [e1]Mark Braverman:
13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA. LIPIcs 215, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-217-4 [contents] - [i94]Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett:
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. CoRR abs/2206.01270 (2022) - [i93]Grace Guan, Mark Braverman:
Empirical Characteristics of Affordable Care Act Risk Transfer Payments. CoRR abs/2208.02372 (2022) - [i92]Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora:
Understanding Influence Functions and Datamodels via Harmonic Analysis. CoRR abs/2210.01072 (2022) - [i91]Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer:
Improved Monotonicity Testers via Hypercube Embeddings. CoRR abs/2211.09229 (2022) - [i90]Mark Braverman, Dor Minzer:
Rounding via Low Dimensional Embeddings. CoRR abs/2211.09729 (2022) - [i89]Mark Braverman, Subhash Khot, Dor Minzer:
Parallel Repetition for the GHZ Game: Exponential Decay. CoRR abs/2211.13741 (2022) - [i88]Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
Round-vs-Resilience Tradeoffs for Binary Feedback Channels. Electron. Colloquium Comput. Complex. TR22 (2022) - [i87]Mark Braverman, Subhash Khot, Dor Minzer:
Parallel Repetition for the GHZ Game: Exponential Decay. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c87]Mark Braverman, Dor Minzer:
Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. CCC 2021: 5:1-5:48 - [c86]Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena:
Near Optimal Distributed Learning of Halfspaces with Two Parties. COLT 2021: 724-758 - [c85]Mark Braverman, Subhash Khot, Noam Lifshitz
, Dor Minzer:
An Invariance Principle for the Multi-slice, with Applications. FOCS 2021: 228-236 - [c84]Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko
, Shay Moran:
Statistically Near-Optimal Hypothesis Selection. FOCS 2021: 909-919 - [c83]Mark Braverman, Sumegha Garg, Or Zamir:
Tight Space Complexity of the Coin Problem. FOCS 2021: 1068-1079 - [c82]Mark Braverman, Subhash Khot, Dor Minzer:
On Rich 2-to-1 Games. ITCS 2021: 27:1-27:20 - [c81]Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao:
Tiered Random Matching Markets: Rank Is Proportional to Popularity. ITCS 2021: 46:1-46:16 - [c80]Mark Braverman, Jon Schneider, S. Matthew Weinberg
:
Prior-free Dynamic Mechanism Design With Limited Liability. EC 2021: 204-223 - [c79]Mark Braverman, Dor Minzer:
New separations results for external information. STOC 2021: 248-258 - [i86]Mark Braverman, Jon Schneider, S. Matthew Weinberg:
Prior-free Dynamic Mechanism Design With Limited Liability. CoRR abs/2103.01868 (2021) - [i85]Mark Braverman, Dor Minzer:
New Separations Results for External Information. CoRR abs/2103.04049 (2021) - [i84]Mark Braverman:
Optimization-friendly generic mechanisms without money. CoRR abs/2106.07752 (2021) - [i83]Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran:
Statistically Near-Optimal Hypothesis Selection. CoRR abs/2108.07880 (2021) - [i82]Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer:
An Invariance Principle for the Multi-slice, with Applications. CoRR abs/2110.10725 (2021) - [i81]Mark Braverman, Sumegha Garg, Or Zamir:
Tight Space Complexity of the Coin Problem. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j31]Itai Ashlagi
, Mark Braverman, Yash Kanoria
, Peng Shi
:
Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations. Manag. Sci. 66(5): 2163-2193 (2020) - [j30]Mark Braverman, Gil Cohen, Sumegha Garg:
Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs. SIAM J. Comput. 49(5) (2020) - [c78]Mark Braverman, Elad Hazan, Max Simchowitz, Blake E. Woodworth:
The Gradient Complexity of Linear Regression. COLT 2020: 627-647 - [c77]Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. FOCS 2020: 318-329 - [c76]Mark Braverman, Sumegha Garg:
The Role of Randomness and Noise in Strategic Classification. FORC 2020: 9:1-9:20 - [c75]Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang:
Calibration, Entropy Rates, and Memory in Language Models. ICML 2020: 1089-1099 - [c74]Xiaoqi Chen, Shir Landau Feibish, Mark Braverman, Jennifer Rexford
:
BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time. SIGCOMM 2020: 226-239 - [i80]Mark Braverman, Sumegha Garg:
The Role of Randomness and Noise in Strategic Classification. CoRR abs/2005.08377 (2020) - [i79]Itai Ashlagi, Mark Braverman, Clayton Thomas, Geng Zhao:
Tiered Random Matching Markets: Rank is Proportional to Popularity. CoRR abs/2009.05124 (2020) - [i78]Mark Braverman, Dor Minzer:
Optimal tiling of the Euclidean space using symmetric bodies. CoRR abs/2011.04071 (2020) - [i77]Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j29]Noga Alon, Mark Braverman, Klim Efremenko
, Ran Gelles
, Bernhard Haeupler:
Reliable communication over highly connected noisy networks. Distributed Comput. 32(6): 505-515 (2019) - [j28]Mark Braverman, Brendan Juba
:
The Price of Uncertain Priors in Source Coding. IEEE Trans. Inf. Theory 65(2): 1165-1171 (2019) - [c73]Mark Braverman, Klim Efremenko
, Ran Gelles
, Michael A. Yitayew:
Optimal Short-Circuit Resilient Formulas. CCC 2019: 10:1-10:22 - [c72]Mark Braverman, Jieming Mao, Yuval Peres:
Sorted Top-k in Rounds. COLT 2019: 342-382 - [c71]Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
:
Multi-armed Bandit Problems with Strategic Arms. COLT 2019: 383-416 - [c70]Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal:
On the Computational Power of Radio Channels. DISC 2019: 8:1-8:17 - [i76]Mark Braverman, Cristobal Rojas, Jonathan Schneider:
Space-bounded Church-Turing thesis and computational tractability of closed systems. CoRR abs/1905.03610 (2019) - [i75]Mark Braverman, Jieming Mao, Yuval Peres:
Sorted Top-k in Rounds. CoRR abs/1906.05208 (2019) - [i74]Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang:
Calibration, Entropy Rates, and Memory in Language Models. CoRR abs/1906.05664 (2019) - [i73]Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena:
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility. CoRR abs/1909.03547 (2019) - [i72]Mark Braverman, Elad Hazan, Max Simchowitz, Blake E. Woodworth:
The gradient complexity of linear regression. CoRR abs/1911.02212 (2019) - [i71]Mark Braverman, Subhash Khot, Dor Minzer:
On Rich $2$-to-$1$ Games. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j27]Mark Braverman, Klim Efremenko
, Ran Gelles, Bernhard Haeupler
:
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM 65(1): 4:1-4:41 (2018) - [j26]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): 2277-2314 (2018) - [c69]Mark Braverman, Young Kun-Ko:
Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. APPROX-RANDOM 2018: 6:1-6:17 - [c68]Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
:
A Candidate for a Strong Separation of Information and Communication. ITCS 2018: 11:1-11:13 - [c67]Mark Braverman, Young Kun-Ko:
Information Value of Two-Prover Games. ITCS 2018: 12:1-12:15 - [c66]Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
:
Selling to a No-Regret Buyer. EC 2018: 523-538 - [c65]Mark Braverman, Jieming Mao, S. Matthew Weinberg
:
On Simultaneous Two-player Combinatorial Auctions. SODA 2018: 2256-2273 - [c64]Mark Braverman, Gil Cohen, Sumegha Garg:
Hitting sets with near-optimal error for read-once branching programs. STOC 2018: 353-362 - [c63]Mark Braverman, Gillat Kol:
Interactive compression to external information. STOC 2018: 964-977 - [i70]Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew:
Optimal Short-Circuit Resilient Formulas. CoRR abs/1807.05014 (2018) - [i69]Mark Braverman, Brendan Juba:
The Price of Uncertain Priors in Source Coding. CoRR abs/1811.08976 (2018) - 2017
- [j25]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Strategyproof Mechanisms for Competitive Influence in Networks. Algorithmica 78(2): 425-452 (2017) - [j24]Mark Braverman, Klim Efremenko
:
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. SIAM J. Comput. 46(1): 388-428 (2017) - [j23]Mark Braverman:
Interactive Information Complexity. SIAM Rev. 59(4): 803-846 (2017) - [j22]Mark Braverman, Ran Gelles
, Jieming Mao
, Rafail Ostrovsky:
Coding for Interactive Communication Correcting Insertions and Deletions. IEEE Trans. Inf. Theory 63(10): 6256-6270 (2017) - [j21]Maria-Florina Balcan, Mark Braverman:
Nash Equilibria in Perturbation-Stable Games. Theory Comput. 13(1): 1-31 (2017) - [c62]Mark Braverman, Rotem Oshman:
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. FOCS 2017: 144-155 - [c61]Mark Braverman, Sumegha Garg, Ariel Schvartzman:
Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. ITCS 2017: 18:1-18:18 - [c60]Itai Ashlagi, Mark Braverman, Yash Kanoria, Peng Shi:
Communication Requirements and Informative Signaling in Matching Markets. EC 2017: 263 - [c59]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-k-Subgraph with Perfect Completeness. SODA 2017: 1326-1341 - [i68]Mark Braverman, Jieming Mao, S. Matthew Weinberg:
On Simultaneous Two-player Combinatorial Auctions. CoRR abs/1704.03547 (2017) - [i67]Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg:
Multi-armed Bandit Problems with Strategic Arms. CoRR abs/1706.09060 (2017) - [i66]Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg:
Selling to a No-Regret Buyer. CoRR abs/1711.09176 (2017) - [i65]Mark Braverman, Gil Cohen, Sumegha Garg:
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs. Electron. Colloquium Comput. Complex. TR17 (2017) - [i64]Mark Braverman, Young Kun-Ko:
Information Value of Two-Prover Games. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j20]Mark Braverman, David P. Woodruff:
Guest Editorial for Information Complexity and Applications. Algorithmica 76(3): 595-596 (2016) - [j19]Mark Braverman, Omri Weinstein:
A Discrepancy Lower Bound for Information Complexity. Algorithmica 76(3): 846-864 (2016) - [j18]Mark Braverman, Jing Chen, Sampath Kannan:
Optimal Provision-After-Wait in Healthcare. Math. Oper. Res. 41(1): 352-376 (2016) - [j17]Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information Lower Bounds via Self-Reducibility. Theory Comput. Syst. 59(2): 377-396 (2016) - [c58]Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky:
Coding for Interactive Communication Correcting Insertions and Deletions. ICALP 2016: 61:1-61:14 - [c57]Mark Braverman, Jon Schneider:
Information Complexity Is Computable. ICALP 2016: 87:1-87:10 - [c56]Noga Alon, Mark Braverman, Klim Efremenko
, Ran Gelles, Bernhard Haeupler
:
Reliable Communication over Highly Connected Noisy Networks. PODC 2016: 165-173 - [c55]Mark Braverman, Jieming Mao, S. Matthew Weinberg
:
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. SODA 2016: 1444-1457 - [c54]Mark Braverman, Jieming Mao, S. Matthew Weinberg
:
Parallel algorithms for select and partition with noisy comparisons. STOC 2016: 851-862 - [c53]Mark Braverman, Klim Efremenko
, Ran Gelles, Bernhard Haeupler
:
Constant-rate coding for multiparty interactive communication is impossible. STOC 2016: 999-1010 - [c52]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: 1011-1020 - [i63]Mark Braverman, Jieming Mao, S. Matthew Weinberg:
Parallel Algorithms for Select and Partition with Noisy Comparisons. CoRR abs/1603.04941 (2016) - [i62]Mark Braverman, Sumegha Garg, Ariel Schvartzman:
Network coding in undirected graphs is either very helpful or not helpful at all. CoRR abs/1608.06545 (2016) - [i61]Mark Braverman, Ran Gelles, Michael A. Yitayew:
Optimal Resilience for Short-Circuit Noise in Formulas. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j16]Mark Braverman:
Interactive Information Complexity. SIAM J. Comput. 44(6): 1698-1739 (2015) - [c51]Mark Braverman, Brendan Juba:
The price of uncertainty in communication. Allerton 2015: 924-927 - [c50]Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette:
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. FOCS 2015: 773-791 - [c49]Mark Braverman, Jieming Mao:
Simulating Noisy Channel Interaction. ITCS 2015: 21-30 - [c48]Mark Braverman, Rotem Oshman:
On Information Complexity in the Broadcast Model. PODC 2015: 355-364 - [c47]Mark Braverman, Young Kun-Ko, Omri Weinstein:
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. SODA 2015: 970-982 - [c46]Mark Braverman, Ankit Garg:
Small Value Parallel Repetition for General Games. STOC 2015: 335-340 - [c45]Mark Braverman, Omri Weinstein:
An Interactive Information Odometer and Applications. STOC 2015: 341-350 - [i60]Mark Braverman, Jon Schneider:
Information complexity is computable. CoRR abs/1502.02971 (2015) - [i59]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. CoRR abs/1504.08352 (2015) - [i58]Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette:
Near-optimal bounds on bounded-round quantum communication complexity of disjointness. CoRR abs/1505.03110 (2015) - [i57]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. CoRR abs/1506.07216 (2015) - [i56]Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky:
Coding for interactive communication correcting insertions and deletions. CoRR abs/1508.00514 (2015) - [i55]Mark Braverman, Cristobal Rojas, Jon Schneider:
Tight space-noise tradeoffs in computing the ergodic measure. CoRR abs/1508.05372 (2015) - [i54]Mark Braverman, Jieming Mao, S. Matthew Weinberg:
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. CoRR abs/1511.02831 (2015) - [i53]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable Communication over Highly Connected Noisy Networks. Electron. Colloquium Comput. Complex. TR15 (2015) - [i52]Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Constant-rate coding for multiparty interactive communication is impossible. Electron. Colloquium Comput. Complex. TR15 (2015) - [i51]