Selected recent publications

  • 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
    [ECCC]
  • Information lower bounds via self-reducibility
    Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
    CSR'13; [ECCC]
  • 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]
  • Direct products in communication complexity
    Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
    [ECCC]
  • 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; [ECCC]
  • 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]