MB
Mark Braverman
cs.CCcs.DScs.GTcs.LGcs.ITmath.ITmath.DSstat.MLcs.DMcs.AI
On Valency
published · living versionsW_avtqbapj·v1 · currentpublished
Matching Random Point Sets with Minimum Distortion
with Itai Benjamini, Elad Tzalik, Georgii Zakharov
1 version
Preprints & journals
77 papers in the corpus · 2002–2026Optimally Pacing Budget Spending and Learning2610.11074v1 · Mark Braverman, Jingyi Liu, Jieming Mao et al.2026 · 0 citationsarXiv
The Multiple Unicast Conjecture is False2610.10108v1 · Mark Braverman, Zhongtian He2026 · 0 citationsarXiv
Parity and Pattern Detection in Permutation Streams2609.09064v1 · Mark Braverman, Or Zamir2026 · 0 citationsarXiv
Measuring Intelligence Beyond Human Scale2607.07040v2 · Jerry Han, Rafael Moschopoulos, Ella Colby et al.2026 · 0 citationsarXiv
Hardness of Approximate Hylland-Zeckhauser Equilibria2606.00951v2 · Mark Braverman, Jingyi Liu, Eric Xue et al.2026 · 0 citationsarXiv
RubiConv -- Efficient Boundary-Respecting Convolutions2605.08451v1 · Linda Friso, Annie Marsden, Xinyi Chen et al.2026 · 0 citationsarXiv
AI Alignment via Incentives and Correction2605.01643v3 · Rohit Agarwal, Joshua Lin, Mark Braverman et al.2026 · 0 citationsarXiv
Learning from Equivalence Queries, Revisited2604.04535v2 · Mark Braverman, Roi Livni, Yishay Mansour et al.2026 · 0 citationsarXiv
Stronger core results with multidimensional prices2603.17862v1 · Mark Braverman, Jingyi Liu, Eric Xue et al.2026 · 0 citationsarXiv
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems2511.03083v1 · Amey Bhangale, Mark Braverman, Subhash Khot et al.2025 · 0 citationsarXiv
Undirected Multicast Network Coding Gaps via Locally Decodable Codes2510.18737v1 · Mark Braverman, Zhongtian He2025 · 0 citationsarXiv
A New Benchmark for Online Learning with Budget-Balancing Constraints2503.14796v1 · Mark Braverman, Jingyi Liu, Jieming Mao et al.2025 · 0 citationsarXiv
Practical Secure Delegated Linear Algebra with Trapdoored Matrices2502.13060v3 · Mark Braverman, Stephen Newman2025 · 3 citationsarXiv
Tight Analyses of Ordered and Unordered Linear Probing2501.11582v1 · Mark Braverman, William Kuszmaul2025 · 1 citationarXiv
Optimality of Frequency Moment Estimation2411.02148v2 · Mark Braverman, Or Zamir2024 · 1 citationarXiv
Parallel Repetition for -Player XOR Games2408.09352v1 · Amey Bhangale, Mark Braverman, Subhash Khot et al.2024 · 0 citationsarXiv
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling2407.15285v1 · Mark Braverman, Mahsa Derakhshan, Tristan Pollner et al.2024 · 3 citationsarXiv
A New Information Complexity Measure for Multi-pass Streaming with Applications2403.20283v1 · Mark Braverman, Sumegha Garg, Qian Li et al.2024 · 1 citationarXiv
Parallel Repetition of k-Player Projection Games2312.04783v1 · Amey Bhangale, Mark Braverman, Subhash Khot et al.2023 · 0 citationsarXiv
Welfare Distribution in Two-sided Random Matching Markets2302.08599v1 · Itai Ashlagi, Mark Braverman, Geng Zhao2023 · 0 citationsarXiv
Parallel Repetition for the GHZ Game: Exponential Decay2211.13741v1 · Mark Braverman, Subhash Khot, Dor Minzer2022 · 3 citationsarXiv
Improved Monotonicity Testers via Hypercube Embeddings2211.09229v1 · Mark Braverman, Subhash Khot, Guy Kindler et al.2022 · 2 citationsarXiv
Understanding Influence Functions and Datamodels via Harmonic Analysis2210.01072v1 · Nikunj Saunshi, Arushi Gupta, Mark Braverman et al.2022 · 2 citationsarXiv
Empirical Characteristics of Affordable Care Act Risk Transfer Payments2208.02372v1 · Grace Guan, Mark Braverman2022 · 0 citationsarXiv
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark2206.01270v1 · Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett2022 · 13 citationsarXiv
An Invariance Principle for the Multi-slice, with Applications2110.10725v2 · Mark Braverman, Subhash Khot, Noam Lifshitz et al.2021 · 29 citationsarXiv
Statistically Near-Optimal Hypothesis Selection2108.07880v1 · Olivier Bousquet, Mark Braverman, Klim Efremenko et al.2021 · 0 citationsarXiv
Optimization-friendly generic mechanisms without money2106.07752v1 · Mark Braverman2021 · 1 citationarXiv
New Separations Results for External Information2103.04049v1 · Mark Braverman, Dor Minzer2021 · 1 citationarXiv
Prior-free Dynamic Mechanism Design With Limited Liability2103.01868v1 · Mark Braverman, Jon Schneider, S. Matthew Weinberg2021 · 0 citationsarXiv
Optimal tiling of the Euclidean space using symmetric bodies2011.04071v1 · Mark Braverman, Dor Minzer2020 · 2 citationsarXiv
Tiered Random Matching Markets: Rank is Proportional to Popularity2009.05124v2 · Itai Ashlagi, Mark Braverman, Amin Saberi et al.2020 · 2 citationsarXiv
The Role of Randomness and Noise in Strategic Classification2005.08377v1 · Mark Braverman, Sumegha Garg2020 · 16 citationsarXiv
The gradient complexity of linear regression1911.02212v3 · Mark Braverman, Elad Hazan, Max Simchowitz et al.2019 · 15 citationsarXiv
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility1909.03547v1 · Mark Braverman, Gillat Kol, Shay Moran et al.2019 · 2 citationsarXiv
Sorted Top-k in Rounds1906.05208v1 · Mark Braverman, Jieming Mao, Yuval Peres2019 · 0 citationsarXiv
Calibration, Entropy Rates, and Memory in Language Models1906.05664v1 · Mark Braverman, Xinyi Chen, Sham M. Kakade et al.2019 · 15 citationsarXiv
The Price of Uncertain Priors in Source Coding1811.08976v1 · Mark Braverman, Brendan Juba2018 · 3 citationsarXiv
Optimal Short-Circuit Resilient Formulas1807.05014v2 · Mark Braverman, Klim Efremenko, Ran Gelles et al.2018 · 0 citationsarXiv
Selling to a No-Regret Buyer1711.09176v1 · Mark Braverman, Jieming Mao, Jon Schneider et al.2017 · 41 citationsarXiv
Multi-armed Bandit Problems with Strategic Arms1706.09060v1 · Mark Braverman, Jieming Mao, Jon Schneider et al.2017 · 8 citationsarXiv
On Simultaneous Two-player Combinatorial Auctions1704.03547v1 · Mark Braverman, Jieming Mao, S. Matthew Weinberg2017 · 14 citationsarXiv
Network coding in undirected graphs is either very helpful or not helpful at all1608.06545v1 · Mark Braverman, Sumegha Garg, Ariel Schvartzman2016 · 1 citationarXiv
Parallel Algorithms for Select and Partition with Noisy Comparisons1603.04941v1 · Mark Braverman, Jieming Mao, S. Matthew Weinberg2016 · 38 citationsarXiv
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions1511.02831v1 · Mark Braverman, Jieming Mao, S.Matthew Weinberg2015 · 7 citationsarXiv
Space-Bounded Church-Turing Thesis and Computational Tractability of Closed Systems.26371687 · Braverman, Mark, Schneider, Jonathan, Rojas, Cristóbal2015 · 12 citationsPhysical review letters. 2015;115(9):098701
Tight space-noise tradeoffs in computing the ergodic measure1508.05372v1 · Mark Braverman, Cristobal Rojas, Jon Schneider2015 · 5 citationsarXiv
Coding for interactive communication correcting insertions and deletions1508.00514v2 · Mark Braverman, Ran Gelles, Jieming Mao et al.2015 · 40 citationsarXiv
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality1506.07216v3 · Mark Braverman, Ankit Garg, Tengyu Ma et al.2015 · 132 citationsarXiv
Near-optimal bounds on bounded-round quantum communication complexity of disjointness1505.03110v1 · Mark Braverman, Ankit Garg, Young Kun Ko et al.2015 · 25 citationsarXiv
Career total: 232 works. 77 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.