Publications (46)
Inapproximability of NP-Complete Variants of Nash Equilibrium
Per Austrin, Mark Braverman, Eden Chlamtac
Computability of Brolin-Lyubich Measure
Ilia Binder, Mark Braverman, Cristobal Rojas +1
Non-computable Julia sets
Mark Braverman, Michael Yampolsky
Selling to a No-Regret Buyer
Mark Braverman, Jieming Mao, Jon Schneider +1
The Price of Uncertain Priors in Source Coding
Mark Braverman, Brendan Juba
Network coding in undirected graphs is either very helpful or not helpful at all
Mark Braverman, Sumegha Garg, Ariel Schvartzman
Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao, S. Matthew Weinberg
Multi-armed Bandit Problems with Strategic Arms
Mark Braverman, Jieming Mao, Jon Schneider +1
Noisy Sorting Without Resampling
Mark Braverman, Elchanan Mossel
On computational complexity of Riemann mapping
Ilia Binder, Mark Braverman, Michael Yampolsky
Simulating Noisy Channel Interaction
Mark Braverman, Jieming Mao
Sorting from Noisy Information
Mark Braverman, Elchanan Mossel
On ad hoc routing with guaranteed delivery
Mark Braverman
On Simultaneous Two-player Combinatorial Auctions
Mark Braverman, Jieming Mao, S. Matthew Weinberg
Contracting Experts With Unknown Cost Structures
Mark Braverman, Gal Oshri
On the Complexity of Real Functions
Mark Braverman
Calibration, Entropy Rates, and Memory in Language Models
Mark Braverman, Xinyi Chen, Sham M. Kakade +3
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, Young Kun Ko +2
Search using queries on indistinguishable items
Mark Braverman, Gal Oshri
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness
Mark Braverman, Young Kun Ko, Aviad Rubinstein +1
The Grothendieck constant is strictly smaller than Krivine's bound
Mark Braverman, Konstantin Makarychev, Yury Makarychev +1
Nash Equilibria in Perturbation Resilient Games
Maria-Florina Balcan, Mark Braverman
Truthful Mechanisms for Competing Submodular Processes
Allan Borodin, Mark Braverman, Brendan Lucier +1
Mafia: A theoretical study of players and coalitions in a partial information environment
Mark Braverman, Omid Etesami, Elchanan Mossel
The rate of convergence of the Walk on Spheres Algorithm
Ilia Binder, Mark Braverman
Computing over the Reals: Foundations for Scientific Computing
Mark Braverman, Stephen Cook
Information complexity is computable
Mark Braverman, Jon Schneider
Information Equals Amortized Communication
Mark Braverman, Anup Rao
Constructing Non-Computable Julia Sets
Mark Braverman, Michael Yampolsky
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Mark Braverman, Ankit Garg, Tengyu Ma +2
On the Convergence of the Hegselmann-Krause System
Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle +1
Thurston equivalence to a rational map is decidable
Sylvain Bonnot, Mark Braverman, Michael Yampolsky
Computability of Julia sets
Mark Braverman, Michael Yampolsky
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions
Mark Braverman, Jieming Mao, S. Matthew Weinberg
Matching with Couples Revisited
Itai Ashlagi, Mark Braverman, Avinatan Hassidim
Sorted Top-k in Rounds
Mark Braverman, Jieming Mao, Yuval Peres
Space-bounded Church-Turing thesis and computational tractability of closed systems
Mark Braverman, Cristobal Rojas, Jonathan Schneider
Optimal Provision-After-Wait in Healthcare
Mark Braverman, Jing Chen, Sampath Kannan
A discrepancy lower bound for information complexity
Mark Braverman, Omri Weinstein
Tight Bounds for Set Disjointness in the Message Passing Model
Mark Braverman, Faith Ellen, Rotem Oshman +2
Tight space-noise tradeoffs in computing the ergodic measure
Mark Braverman, Cristobal Rojas, Jon Schneider
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao +1
Finding Endogenously Formed Communities
Maria-Florina Balcan, Christian Borgs, Mark Braverman +2
On computability of Julia sets: answers to questions of Milnor and Shub
Mark Braverman, Michael Yampolsky
Pebbles and Branching Programs for Tree Evaluation
Stephen Cook, Pierre McKenzie, Dustin Wehr +2
Noise vs computational intractability in dynamics
Mark Braverman, Alexander Grigo, Cristobal Rojas