Selected recent publications

  • Network coding in undirected graphs is either very helpful or not helpful at all
    Mark Braverman, Sumegha Garg, Ariel Schvartzman
    [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]
  • Constant-rate coding for multiparty interactive communication is impossible
    Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
    STOC'16; [ECCC]
  • Data-driven incentive alignment in capitation schemes
    Mark Braverman, Sylvain Chassang
    Preprint; [pdf]
  • 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]
  • Tight space-noise tradeoffs in computing the ergodic measure
    Mark Braverman, Cristobal Rojas, Jon Schneider
    [arXiv]
  • Coding for interactive communication correcting insertions and deletions
    Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
    ICALP'16; [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
    FOCS'15; [ECCC]
  • ETH hardness for Densest-k-Subgraph with perfect completeness
    Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein
    [ECCC]
  • Information complexity is computable
    Mark Braverman, Jon Schneider
    ICALP'16; [ECCC]
    Video of talk given at the Simons Institute [youtube]
  • Reliable communication over highly connected noisy networks
    Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
    PODC'16; [ECCC]
  • 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]
  • Interactive information and coding theory
    Mark Braverman
    A survey accompanying an invited lecture at ICM'14 in Seoul [pdf]
    Video of the talk [youtube]
  • 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]
  • List and unique coding for interactive communication in the presence of adversarial noise
    Mark Braverman, Klim Efremenko
    FOCS'14; [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]
  • Optimal Provision-After-Wait in healthcare
    Mark Braverman, Jing Chen, Sampath Kannan
    working paper; ITCS'14; [pdf]
  • 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]
  • A discrepancy lower bound for information complexity
    Mark Braverman, Omri Weinstein
    RANDOM'12; [arXiv]
  • Interactive information complexity
    Mark Braverman
    STOC'12; [ECCC]
  • The Grothendieck constant is strictly smaller than Krivine's bound
    Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
    FOCS'11; [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]

Other publications

  • 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.
  • Approximate Nash equilibria in perturbation resilient games
    Nina Balcan, Mark Braverman
    Working paper; [arXiv]
  • Pseudorandom Generators for Regular Branching Programs
    Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
    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 Analysis, to appear; [pdf]
  • Thurston equivalence to a rational map is decidable
    Sylvain Bonnot, Mark Braverman, Michael Yampolsky
    Moscow Math. Journal, to appear; [arXiv]
  • How to compress interactive communication
    Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
    STOC'10 [pdf]
    Previous version [ECCC]
  • Stability in large matching markets with complementarities
    Itai Ashalgi, Mark Braverman, Avinatan Hassidim
    Working paper; [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
    Submitted; [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]