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]