All Papers

Selected recent publications and preprints

Optimization-friendly generic mechanisms without money
Mark Braverman
[arXiv] [talk]
Statistically near-optimal hypothesis selection
Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran
FOCS'21; [arXiv]
Tight space complexity of the coin problem
Mark Braverman, Sumegha Garg, Or Zamir
FOCS'21; [ECCC]
Data-driven incentive alignment in capitation schemes
Mark Braverman, Sylvain Chassang
[NBER preprint] [Journal of Public Economics 207, 2022]
BeauCoup: Answering many network traffic queries, one memory update at a time
Xiaoqi Chen, Shir Landau-Feibish, Mark Braverman, Jennifer Rexford
[SIGCOMM'20]; [APNIC post]
The role of randomness and noise in strategic classification
Mark Braverman, Sumegha Garg
FORC'20; [arXiv]; [youtube talk]
Space-Bounded Church-Turing Thesis and computational tractability of closed systems
Mark Braverman, Cristobal Rojas, Jon Schneider
Phys. Rev. Lett. 115, 098701; [link] [phys.org article]
Interactive information and coding theory
Mark Braverman
A survey accompanying an invited lecture at ICM'14 in Seoul [pdf]
Video of the talk [youtube]
Interactive information complexity
Mark Braverman
STOC'12; [ECCC]; [SICOMP 64(6)]; [SIAM Review 59(4)]
The Grothendieck constant is strictly smaller than Krivine’s bound
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
FOCS'11; [arXiv] [Forum of Mathematics, Pi version]

Other publications

Unbiased delay measurement in the data plane
Yufei Zheng, Xiaoqi Chen, Mark Braverman, Jennifer Rexford
[APOCS'22]
An invariance principle for the multi-slice, with applications
Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
FOCS'21; [arXiv]; [youtube talk]
Near-optimal distributed learning of halfspaces with two parties
Mark Braverman , Gillat Kol , Shay Moran , Raghuvansh R. Saxena
[COLT'21]
New separations results for external information
Mark Braverman, Dor Minzer
STOC'21; [arXiv]; [youtube talk]
Optimal tiling of the Euclidean space using permutation-symmetric bodies
Mark Braverman, Dor Minzer
[Complexity'21]; [public talk related to this paper]
Prior-free dynamic mechanism design with limited liability
Mark Braverman, Jon Schneider, Matt Weinberg
EC'21; [arXiv]
Tiered random matching markets: rank is proportional to popularity
Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao
[ITCS'21]; [youtube talk]
On rich $2$-to-$1$ games
Mark Braverman, Subhash Khot, Dor Minzer
[ITCS'21]; [youtube talk]
Clearing matching markets efficiently: informative signals and match recommendations
Itai Ashlagi, Mark Braverman, Yash Kanoria, Peng Shi
Management Science 66(5), 2020 (earlier version in EC'17)
[Management Science]; [SSRN]; [youtube talk]
The coin problem with applications to data streams
Mark Braverman, Sumegha Garg, David Woodruff
FOCS'20; [ECCC]; [youtube talk]
Calibration, entropy rates, and memory in language models
Mark Braverman, Xinyi Chen, Sham Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang
[ICML'20]
The gradient complexity of linear regression
Mark Braverman, Elad Hazan, Max Simchowitz, Blake Woodworth
[COLT'20]
Optimal short-circuit resilient formulas
Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
[Complexity'19]
On the computational power of radio channels
Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
[DISC'19]
Multi-armed bandit problems with strategic arms
Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
[COLT'19]
Sorted Top-k in rounds
Mark Braverman, Jieming Mao, Yuval Peres
[COLT'19]
Reliable communication over highly connected noisy networks
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
Distributed Computing, 32(6), 2019; also PODC'16
[ECCC]; [Distributed Computing]
The price of uncertain priors in source coding
Mark Braverman, Brendan Juba
IEEE Transactions on Information Theory, 65(2), 2019
[Transactions on Information Theory]; [arXiv]
Information complexity and applications
Mark Braverman Japanese Journal of Mathematics 1(14), 2019
[JJM]
Hitting sets with near-optimal error for read-once branching programs
Mark Braverman, Gil Cohen, Sumegha Garg
STOC'18, [ECCC], [SICOMP version]
Interactive compression to external information
Mark Braverman, Gillat Kol
[STOC'18];
Selling to a no-regret buyer
Mark Braverman, Jieming Mao, Jon Schneider, Matt Weinberg
EC'18; [arXiv]; Best Full Paper award
Semi-direct sum theorem and nearest neighbor under $\ell_\infty$
Mark Braverman, Young Kun Ko
[APPROX'18]
A candidate for a strong separation of information and communication
Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
[ITCS'18]
Information value of two-prover games
Mark Braverman, Young Kun Ko
[ITCS'18]
On simultaneous two-player combinatorial auctions
Mark Braverman, Jieming Mao, Matt Weinberg
SODA'18; [arXiv]
Constant-rate coding for multiparty interactive communication is impossible
Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
Journal of the ACM 65(1):4, 2018; (also STOC'16)
[ECCC]; [JACM]
Nash equilibria in perturbation-stable games
Maria-Florina Balcan, Mark Braverman
Theory of Computing, 13(13), 2017
[ToC]
A rounds vs. communication tradeoff for multi-party set disjointness
Mark Braverman, Rotem Oshman
[FOCS'17]
Network coding in undirected graphs is either very helpful or not helpful at all
Mark Braverman, Sumegha Garg, Ariel Schvartzman
ITCS'17; [arXiv]
A discrepancy lower bound for information complexity
Mark Braverman, Omri Weinstein
Algorithmica 76(3), 2016; RANDOM'12; [Algorithmica]; [arXiv]
List and unique coding for interactive communication in the presence of adversarial noise
Mark Braverman, Klim Efremenko
SICOMP 46(1) (special issue for FOCS'14)
[SICOMP] [ECCC]
Tight space-noise tradeoffs in computing the ergodic measure
Mark Braverman, Cristobal Rojas, Jon Schneider
Matematicheskii Sbornik, 208(12), 2017 (Special 150th anniversary issue)
[Sbornik] [arXiv]
Parallel algorithms for select and partition with noisy comparisons
Mark Braverman, Jieming Mao, Matt Weinberg
STOC'16; [arXiv]
Interpolating between truthful and non-truthful mechanisms for combinatorial auctions
Mark Braverman, Jieming Mao, Matt Weinberg
SODA'16; [arXiv]
Optimal Provision-After-Wait in healthcare
Mark Braverman, Jing Chen, Sampath Kannan
Mathematics of Operations Research 41(1), 2016; ITCS'14; [pdf]; [MOR]
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
IEEE Transactions on Information Theory, 63(10), 2017 ; ICALP'16;
[Transactions on Information Theory]; [arXiv]
Communication lower bounds for statistical estimation problems via a distributed data processing inequality
Mark Braverman, Ankit Garg, Tengyu Ma, Huy Nguyen, David Woodruff
STOC'16; [arXiv]
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette
SIAM Journal on Computing 47(6), 2018 (special issue for FOCS'15)
[ECCC]; [SICOMP]
ETH hardness for Densest-k-Subgraph with perfect completeness
Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein
SODA'17; [ECCC]
Information complexity is computable
Mark Braverman, Jon Schneider
ICALP'16; [ECCC]
Video of talk given at the Simons Institute [youtube]
The communication complexity of Number-In-Hand Set Disjointness with no promise
Mark Braverman, Rotem Oshman
PODC'15; [ECCC]
Simulating noisy channel interaction
Mark Braverman, Jieming Mao
ITCS'15; [ECCC]
Small value parallel repetition for general games
Mark Braverman, Ankit Garg
STOC'15; [ECCC]
Approximating the best Nash equilibrium in $n^{o(logn)}$ -time breaks the Exponential Time Hypothesis
Mark Braverman, Young Kun Ko, Omri Weinstein
SODA'15; [ECCC]
An interactive information odometer with applications
Mark Braverman, Omri Weinstein
STOC'15; [ECCC]
The computational hardness of pricing compound options
Mark Braverman, Kanika Pasricha
working paper; ITCS'14; [ECCC]
A hard-to-compress interactive task?
Mark Braverman
Allerton'13; [pdf]
Public vs private coin in bounded-round information
Mark Braverman, Ankit Garg
ICALP'14; [ECCC]
Tight bounds for set disjointness in the message passing model
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
FOCS'13; [arXiv]
Direct products in communication complexity
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
FOCS'13; [ECCC]
From information to exact communication
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
STOC'13; [ECCC]
Direct product via round-preserving compression
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
ICALP'13; [ECCC]
Information lower bounds via self-reducibility
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
CSR'13; [ECCC]
Journal of Computing Systems [Springer]
Search using queries on indistinguishable items
Mark Braverman, Gal Oshri
STACS'13; [arXiv]
On the convergence of the Hegselmann-Krause system
Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy Nguyen
ITCS'13; [arXiv]
An information complexity approach to extended formulations
Mark Braverman, Ankur Moitra
STOC'13; [ECCC]
Coding for interactive computation: progress and challenges
Mark Braverman
Allerton'12; [pdf]
Towards deterministic tree code constructions
Mark Braverman
ITCS'12; [ECCC]
Noise vs computational intractability in dynamics
Mark Braverman, Alexander Grigo, Cristobal Rojas
ITCS'12; [arXiv]
Towards coding for maximum errors in interactive communication
Mark Braverman, Anup Rao
STOC'11; [ECCC] [video by Anup]
Information equals amortized communication
Mark Braverman, Anup Rao
FOCS'11; [ECCC]
IEEE Transactions on Information Theory, 60(10), 2014 [[IEEE](https://ieeexplore.ieee.org/document/6877708)
Leaky pseudo-entropy functions
Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai
In ITCS'11; [pdf]
Finding endogenously formed communities
Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, Shang-Hua Teng
SODA'13; [arXiv]
Truthful mechanisms for competing submodular processes
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
WWW'13; [arXiv]
Inapproximability of NP-complete variants of Nash equilibrium
Per Austrin, Mark Braverman, Eden Chlamtac
in APPROX'11; [arXiv]
Theory of Computing, 9(3), 2013.
Pseudorandom Generators for Regular Branching Programs
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
[SICOMP 43(3)], 2014;
Earlier version in FOCS'10; [ECCC] [video by Anup]
Computability of Brolin-Lyubich measure
Ilia Binder, Mark Braverman, Cristobal Rojas, Michael Yampolsky
In Comm. in Math. Phys.; [arXiv]
The rate of convergence of the Walk on Spheres Algorithm
Ilia Binder, Mark Braverman
Geometric and Functional Analysis22 (2012); [pdf]; [GAFA]
Thurston equivalence to a rational map is decidable
Sylvain Bonnot, Mark Braverman, Michael Yampolsky
Moscow Math. Journal 12(4), 2012; [arXiv]; [MMJ]
How to compress interactive communication
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
[SICOMP 42(3)], 2013 (special issue for STOC'10);
STOC'10 [pdf]; [ECCC]
Stability in large matching markets with complementarities
Itai Ashalgi, Mark Braverman, Avinatan Hassidim
Operations Research 62(4), 2014; [OR]; [pdf]
Phylogenetic Reconstruction with Insertions and Deletions
Alex Andoni, Mark Braverman, Avinatan Hassidim
Working paper [pdf]
Monotonicity and Implementability
Itai Ashalgi, Mark Braverman, Avinatan Hassidim, Dov Monderer
Econometrica 78(5), 2010; [pdf] [Supplementary material]
Sorting from Noisy Information
Mark Braverman, Elchanan Mossel
[arXiv]
Ascending unit demand auctions with budget limits
Itai Ashalgi, Mark Braverman, Avinatan Hassidim
Working paper; [pdf]
Position Auctions with Budgets: Existence and Uniqueness
Itai Ashalgi, Mark Braverman, Avinatan Hassidim, Ron Lavi, Moshe Tennenholtz
The B.E. Journal of Theoretical Economics (Advances), 10(1), Article 20, 2010; [pdf].
Poly-logarithmic independence fools AC0 circuits
Mark Braverman
Complexity'09; [ECCC]
Journal of the ACM 57(5), 2010
Communications of the ACM, research highlight, 54(4), 2011
Lecture video from the 2011 METRIC workshop (audio quality not great): [video]
Finding low error clusterings
Nina Balcan, Mark Braverman
COLT'2009; [pdf]
The complexity of simulating Brownian Motion
Ilia Binder, Mark Braverman
SODA'09; [pdf]
Constructing Locally Connected Non-Computable Julia Sets
Mark Braverman, Michael Yampolsky
Commun. Math. Physics, 291(2), 2009; [pdf]
Space-Efficient Counting in Graphs on Surfaces
Mark Braverman, Raghav Kulkarni, Sambuddha Roy
Computational Complexity 18(4), 2009; [pdf]
Pebbles and branching programs for tree evaluation
Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
ACM Transactions on Computation Theory (TOCT) 3(2), 2012; [arXiv]
Preliminary version: MFCS'09 and FSTTCS'09
Slides from Steve Cook’s talk with a \$100 prize offer [pdf]
Book: Computability of Julia Sets
Mark Braverman, Michael Yampolsky
Springer, 2009.
Noisy Sorting Without Resampling
Mark Braverman, Elchanan Mossel
SODA'08.
Mafia : a theoretical study of players and coalitions in a partial information environment
Mark Braverman, Omid Etesami, Elchanan Mossel
Annals of Appl. Prob. 18(3), 2008; [arXiv]
On ad hoc routing with guaranteed delivery
Mark Braverman
Brief announcement, PODC'08; [arXiv]
The complexity of properly learning simple concept classes
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi
Journal of Computer and System Sciences, 74(1), 2008; [pdf]
Computability of Julia Sets
Mark Braverman, Michael Yampolsky
Moscow Math. Journal 8(2), 2008; arXiv
Derandomizing Euclidean random walks
Ilia Binder, Mark Braverman
RANDOM'07; [pdf]
Constructing Non-Computable Julia Sets
Mark Braverman, Michael Yampolsky
STOC'07; [pdf]
Parity Problems in Planar Graphs
Mark Braverman, Raghav Kulkarni, Sambuddha Roy
Complexity'07; [pdf]
Filled Julia sets with empty interior are computable
Ilia Binder, Mark Braverman, Michael Yampolsky
Journal of Found. of Comp. Math. 7(4), 2007; [arXiv]
On computational complexity of Riemann mapping
Ilia Binder, Mark Braverman, Michael Yampolsky
Arkiv for Matematik, 45(2), 2007; [arXiv]
Termination of Integer Linear Programs
Mark Braverman
CAV'06 (Computer-Aided Verification); [pdf]
Non-Computable Julia Sets
Mark Braverman, Michael Yampolsky
Journ. Amer. Math. Soc. 19(3), 2006; [arXiv]
Computing over the Reals: Foundations for Scientific Computing
Mark Braverman, Stephen Cook
Notices of the AMS, 53(3), March 2006; [arXiv]
Parabolic Julia Sets are Polynomial Time Computable
Mark Braverman
Nonlinearity 19, 2006; [arXiv]
On computational complexity of Siegel Julia sets
Ilia Binder, Mark Braverman, Michael Yampolsky
Commun. Math. Physics, 264(2), 2006; [arXiv]
On the Complexity of Real Functions
Mark Braverman
FOCS'05 [pdf]
Full version [arXiv]
Learnability and Automatizability
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi
FOCS'04; [pdf]
Hyperbolic Julia sets are poly-time computable
Mark Braverman
CCA'04 (Computability and Complexity in Analysis), ENTCS 120; [pdf]

Other Manuscripts

Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable
Mark Braverman
MSc Thesis [pdf]
Computability and complexity of Julia sets
Mark Braverman
PhD Thesis
Health care policy development and execution
Mohsen Bayati, Mark Braverman, Eric Horvitz, Michael Gillam
US patent application 20120004925; [USPTO]
Dispensing digital objects to an electronic wallet
Philipp Hertel, Alex Hertel, John Graham, Mark Braverman
US patent application 20110145049; [USPTO]
Secured electronic transaction system
Philipp Hertel, Alex Hertel, John Graham, Mark Braverman
US patent application 20090288012 [USPTO]
Predicting web advertisement click success by using head-to-head ratings
Mohsen Bayati, Mark Braverman, Satyen Kale, Yury Makarychev
US patent application 20100198685; [USPTO]
Method of registering and aligning multiple images
Vyacheslav Zavadsky, Jason Abt, Mark Braverman, Edward Keyes, Vladimir Martincevic
Semiconductor Insights Inc.
US patent 7,693,348 [USPTO]