A Monte Carlo Algorithm for a Lottery Problem. - Mark Braverman; Shay Gueron (Monte Carlo Methods Appl., 2001)

Learnability and Automatizability. - Michael Alekhnovich; Mark Braverman; Vitaly Feldman; Adam R. Klivans; Toniann Pitassi (FOCS, 2004)

Non-computable Julia sets - Mark Braverman; Michael Yampolsky (CoRR, 2004)

Hyperbolic Julia Sets are Poly-Time Computable. - Mark Braverman (CCA, 2004)

On the Complexity of Real Functions. - Mark Braverman (FOCS, 2005)

Computing over the Reals: Foundations for Scientific Computing - Mark Braverman; Stephen A. Cook (CoRR, 2005)

On computational complexity of Siegel Julia sets - Ilia Binder; Mark Braverman; Michael Yampolsky (CoRR, 2005)

On computational complexity of Riemann mapping - Ilia Binder; Mark Braverman; Michael Yampolsky (CoRR, 2005)

Termination of Integer Linear Programs. - Mark Braverman (CAV, 2006)

Derandomization of Euclidean Random Walks. - Ilia Binder; Mark Braverman (APPROX-RANDOM, 2007)

Constructing non-computable Julia sets. - Mark Braverman; Michael Yampolsky (STOC, 2007)

Parity Problems in Planar Graphs. - Mark Braverman; Raghav Kulkarni; Sambuddha Roy (Electron. Colloquium Comput. Complex., 2007)

Filled Julia Sets with Empty Interior Are Computable. - Ilia Binder; Mark Braverman; Michael Yampolsky (Found. Comput. Math., 2007)

On ad hoc routing with guaranteed delivery. - Mark Braverman (PODC, 2008)

Noisy sorting without resampling. - Mark Braverman; Elchanan Mossel (SODA, 2008)

The complexity of properly learning simple concept classes. - Michael Alekhnovich; Mark Braverman; Vitaly Feldman; Adam R. Klivans; Toniann Pitassi (J. Comput. Syst. Sci., 2008)

Computability and complexity of Julia sets. - Mark Braverman (2008)

Computability of Julia Sets. - Mark Braverman; Michael Yampolsky (Springer, 2009)

Computability and Complexity of Julia Sets (Invited Talk). - Mark Braverman (CCA, 2009)

Poly-logarithmic Independence Fools AC0 Circuits. - Mark Braverman (CCC, 2009)

Finding Low Error Clusterings. - Maria-Florina Balcan; Mark Braverman (COLT, 2009)

Fractional Pebbling and Thrifty Branching Programs. - Mark Braverman; Stephen A. Cook; Pierre McKenzie; Rahul Santhanam; Dustin Wehr (FSTTCS, 2009)

Branching Programs for Tree Evaluation. - Mark Braverman; Stephen A. Cook; Pierre McKenzie; Rahul Santhanam; Dustin Wehr (MFCS, 2009)

The complexity of simulating Brownian Motion. - Ilia Binder; Mark Braverman (SODA, 2009)

Space-Efficient Counting in Graphs on Surfaces. - Mark Braverman; Raghav Kulkarni; Sambuddha Roy (Comput. Complex., 2009)

Sorting from Noisy Information - Mark Braverman; Elchanan Mossel (CoRR, 2009)

Direct Sums in Randomized Communication Complexity. - Boaz Barak; Mark Braverman; Xi Chen 001; Anup Rao 001 (Electron. Colloquium Comput. Complex., 2009)

Poly-logarithmic independence fools AC0 circuits. - Mark Braverman (Electron. Colloquium Comput. Complex., 2009)

Approximate Nash Equilibria under Stability Conditions - Maria-Florina Balcan; Mark Braverman (CoRR, 2010)

Efficient Communication Using Partial Information. - Mark Braverman; Anup Rao 001 (Electron. Colloquium Comput. Complex., 2010)

Towards Coding for Maximum Errors in Interactive Communication. - Mark Braverman; Anup Rao 001 (Electron. Colloquium Comput. Complex., 2010)

Polylogarithmic independence fools AC0 circuits. - Mark Braverman (J. ACM, 2010)

The Grothendieck Constant is Strictly Smaller than Krivine's Bound. - Mark Braverman; Konstantin Makarychev; Yury Makarychev; Assaf Naor (FOCS, 2011)

Leaky Pseudo-Entropy Functions. - Mark Braverman; Avinatan Hassidim; Yael Tauman Kalai (ICS, 2011)

Matching with couples revisited. - Itai Ashlagi; Mark Braverman; Avinatan Hassidim (EC, 2011)

Poly-logarithmic independence fools bounded-depth boolean circuits. - Mark Braverman (Commun. ACM, 2011)

Towards deterministic tree code constructions. - Mark Braverman (Electron. Colloquium Comput. Complex., 2011)

A discrepancy lower bound for information complexity. - Mark Braverman; Omri Weinstein (Electron. Colloquium Comput. Complex., 2011)

Coding for interactive computation: Progress and challenges. - Mark Braverman (Allerton Conference, 2012)

Noise vs computational intractability in dynamics. - Mark Braverman; Alexander Grigo; Cristobal Rojas (ITCS, 2012)

I Like Her more than You: Self-determined Communities - Maria-Florina Balcan; Christian Borgs; Mark Braverman; Jennifer T. Chayes; Shang-Hua Teng (CoRR, 2012)

Truthful Mechanisms for Competing Submodular Processes - Allan Borodin; Mark Braverman; Brendan Lucier; Joel Oren (CoRR, 2012)

From Information to Exact Communication. - Mark Braverman; Ankit Garg; Denis Pankratov; Omri Weinstein (Electron. Colloquium Comput. Complex., 2012)

Information lower bounds via self-reducibility. - Mark Braverman; Ankit Garg; Denis Pankratov; Omri Weinstein (Electron. Colloquium Comput. Complex., 2012)

An Information Complexity Approach to Extended Formulations. - Mark Braverman; Ankur Moitra (Electron. Colloquium Comput. Complex., 2012)

Direct Products in Communication Complexity. - Mark Braverman; Anup Rao 001; Omri Weinstein; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2012)

Pebbles and Branching Programs for Tree Evaluation. - Stephen A. Cook; Pierre McKenzie; Dustin Wehr; Mark Braverman; Rahul Santhanam (ACM Trans. Comput. Theory, 2012)

A hard-to-compress interactive task? - Mark Braverman (Allerton, 2013)

Noise versus Computational Intractability in Dynamics. - Mark Braverman (CiE, 2013)

A Tight Bound for Set Disjointness in the Message-Passing Model. - Mark Braverman; Faith Ellen; Rotem Oshman; Toniann Pitassi; Vinod Vaikuntanathan (FOCS, 2013)

On the convergence of the Hegselmann-Krause system. - Arnab Bhattacharyya 001; Mark Braverman; Bernard Chazelle; Huy L. Nguyen (ITCS, 2013)

Finding Endogenously Formed Communities. - Maria-Florina Balcan; Christian Borgs; Mark Braverman; Jennifer T. Chayes; Shang-Hua Teng (SODA, 2013)

Search using queries on indistinguishable items. - Mark Braverman; Gal Oshri (STACS, 2013)

Computing with real numbers, from Archimedes to Turing and beyond. - Mark Braverman (Commun. ACM, 2013)

Tight Bounds for Set Disjointness in the Message Passing Model - Mark Braverman; Faith Ellen; Rotem Oshman; Toniann Pitassi; Vinod Vaikuntanathan (CoRR, 2013)

Public vs private coin in bounded-round information. - Mark Braverman; Ankit Garg (Electron. Colloquium Comput. Complex., 2013)

Direct product via round-preserving compression. - Mark Braverman; Anup Rao 001; Omri Weinstein; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2013)

Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009). - Maria-Florina Balcan; Mark Braverman; Daniel A. Spielman (SIAM J. Comput., 2013)

How to Compress Interactive Communication. - Boaz Barak; Mark Braverman; Xi Chen 001; Anup Rao 001 (SIAM J. Comput., 2013)

Inapproximability of NP-Complete Variants of Nash Equilibrium. - Per Austrin; Mark Braverman; Eden Chlamtac (Theory Comput., 2013)

Contracting Experts With Unknown Cost Structures. - Mark Braverman; Gal Oshri (CoRR, 2014)

Small value parallel repetition for general games. - Mark Braverman; Ankit Garg (Electron. Colloquium Comput. Complex., 2014)

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. - Mark Braverman; Young Kun-Ko; Omri Weinstein (Electron. Colloquium Comput. Complex., 2014)

Simulating Noisy Channel Interaction. - Mark Braverman; Jieming Mao (Electron. Colloquium Comput. Complex., 2014)

The computational hardness of pricing compound options. - Mark Braverman; Kanika Pasricha (Electron. Colloquium Comput. Complex., 2014)

An Interactive Information Odometer with Applications. - Mark Braverman; Omri Weinstein (Electron. Colloquium Comput. Complex., 2014)

Stability in Large Matching Markets with Complementarities. - Itai Ashlagi; Mark Braverman; Avinatan Hassidim (Oper. Res., 2014)

Pseudorandom Generators for Regular Branching Programs. - Mark Braverman; Anup Rao 001; Ran Raz; Amir Yehudayoff (SIAM J. Comput., 2014)

Information Equals Amortized Communication. - Mark Braverman; Anup Rao 001 (IEEE Trans. Inf. Theory, 2014)

Toward Coding for Maximum Errors in Interactive Communication. - Mark Braverman; Anup Rao 001 (IEEE Trans. Inf. Theory, 2014)

The price of uncertainty in communication. - Mark Braverman; Brendan Juba (Allerton, 2015)

On Information Complexity in the Broadcast Model. - Mark Braverman; Rotem Oshman (PODC, 2015)

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. - Mark Braverman; Young Kun-Ko; Omri Weinstein (SODA, 2015)

An Interactive Information Odometer and Applications. - Mark Braverman; Omri Weinstein (STOC, 2015)

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. - Mark Braverman; Young Kun-Ko; Aviad Rubinstein; Omri Weinstein (CoRR, 2015)

Tight space-noise tradeoffs in computing the ergodic measure. - Mark Braverman; Cristobal Rojas; Jon Schneider (CoRR, 2015)

Constant-rate coding for multiparty interactive communication is impossible. - Mark Braverman; Klim Efremenko; Ran Gelles; Bernhard Haeupler (Electron. Colloquium Comput. Complex., 2015)

ETH Hardness for Densest-k-Subgraph with Perfect Completeness. - Mark Braverman; Young Kun-Ko; Aviad Rubinstein; Omri Weinstein (Electron. Colloquium Comput. Complex., 2015)

The Communication Complexity of Number-In-Hand Set Disjointness with No Promise. - Mark Braverman; Rotem Oshman (Electron. Colloquium Comput. Complex., 2015)

Information complexity is computable. - Mark Braverman; Jon Schneider (Electron. Colloquium Comput. Complex., 2015)

Interactive Information Complexity. - Mark Braverman (SIAM J. Comput., 2015)

Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. - Mark Braverman; Jieming Mao; S. Matthew Weinberg (SODA, 2016)

Communication lower bounds for statistical estimation problems via a distributed data processing inequality. - Mark Braverman; Ankit Garg; Tengyu Ma 001; Huy L. Nguyen; David P. Woodruff (STOC, 2016)

Parallel algorithms for select and partition with noisy comparisons. - Mark Braverman; Jieming Mao; S. Matthew Weinberg (STOC, 2016)

Guest Editorial for Information Complexity and Applications. - Mark Braverman; David P. Woodruff (Algorithmica, 2016)

Network coding in undirected graphs is either very helpful or not helpful at all. - Mark Braverman; Sumegha Garg; Ariel Schvartzman (CoRR, 2016)

Optimal Resilience for Short-Circuit Noise in Formulas. - Mark Braverman; Ran Gelles; Michael A. Yitayew (Electron. Colloquium Comput. Complex., 2016)

Optimal Provision-After-Wait in Healthcare. - Mark Braverman; Jing Chen 017; Sampath Kannan (Math. Oper. Res., 2016)

A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. - Mark Braverman; Rotem Oshman (FOCS, 2017)

Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. - Mark Braverman; Sumegha Garg; Ariel Schvartzman (ITCS, 2017)

Communication Requirements and Informative Signaling in Matching Markets. - Itai Ashlagi; Mark Braverman; Yash Kanoria; Peng Shi 002 (EC, 2017)

Strategyproof Mechanisms for Competitive Influence in Networks. - Allan Borodin; Mark Braverman; Brendan Lucier; Joel Oren (Algorithmica, 2017)

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs. - Mark Braverman; Gil Cohen; Sumegha Garg (Electron. Colloquium Comput. Complex., 2017)

Information Value of Two-Prover Games. - Mark Braverman; Young Kun-Ko (Electron. Colloquium Comput. Complex., 2017)

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. - Mark Braverman; Klim Efremenko (SIAM J. Comput., 2017)

Coding for Interactive Communication Correcting Insertions and Deletions. - Mark Braverman; Ran Gelles; Jieming Mao; Rafail Ostrovsky (IEEE Trans. Inf. Theory, 2017)

Nash Equilibria in Perturbation-Stable Games. - Maria-Florina Balcan; Mark Braverman (Theory Comput., 2017)

Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. - Mark Braverman; Young Kun-Ko (APPROX-RANDOM, 2018)

A Candidate for a Strong Separation of Information and Communication. - Mark Braverman; Anat Ganor; Gillat Kol; Ran Raz (ITCS, 2018)

Selling to a No-Regret Buyer. - Mark Braverman; Jieming Mao; Jon Schneider; S. Matthew Weinberg (EC, 2018)

On Simultaneous Two-player Combinatorial Auctions. - Mark Braverman; Jieming Mao; S. Matthew Weinberg (SODA, 2018)

Interactive compression to external information. - Mark Braverman; Gillat Kol (STOC, 2018)

Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness. - Mark Braverman; Ankit Garg; Young Kun-Ko; Jieming Mao; Dave Touchette (SIAM J. Comput., 2018)

Sorted Top-k in Rounds. - Mark Braverman; Jieming Mao; Yuval Peres (COLT, 2019)

Multi-armed Bandit Problems with Strategic Arms. - Mark Braverman; Jieming Mao; Jon Schneider; S. Matthew Weinberg (COLT, 2019)

On the Computational Power of Radio Channels. - Mark Braverman; Gillat Kol; Rotem Oshman; Avishay Tal (DISC, 2019)

Space-bounded Church-Turing thesis and computational tractability of closed systems. - Mark Braverman; Cristobal Rojas; Jonathan Schneider (CoRR, 2019)

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility. - Mark Braverman; Gillat Kol; Shay Moran; Raghuvansh R. Saxena (CoRR, 2019)

Reliable communication over highly connected noisy networks. - Noga Alon; Mark Braverman; Klim Efremenko; Ran Gelles; Bernhard Haeupler (Distributed Comput., 2019)

On Rich $2$-to-$1$ Games. - Mark Braverman; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2019)

The Price of Uncertain Priors in Source Coding. - Mark Braverman; Brendan Juba (IEEE Trans. Inf. Theory, 2019)

The Gradient Complexity of Linear Regression. - Mark Braverman; Elad Hazan; Max Simchowitz; Blake E. Woodworth (COLT, 2020)

The Role of Randomness and Noise in Strategic Classification. - Mark Braverman; Sumegha Garg (FORC, 2020)

Calibration, Entropy Rates, and Memory in Language Models. - Mark Braverman; Xinyi Chen; Sham M. Kakade; Karthik Narasimhan; Cyril Zhang; Yi Zhang (ICML, 2020)

BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time. - Xiaoqi Chen; Shir Landau Feibish; Mark Braverman; Jennifer Rexford (SIGCOMM, 2020)

Tiered Random Matching Markets: Rank is Proportional to Popularity. - Itai Ashlagi; Mark Braverman; Clayton Thomas; Geng Zhao 002 (CoRR, 2020)

Optimal tiling of the Euclidean space using symmetric bodies. - Mark Braverman; Dor Minzer (CoRR, 2020)

The Coin Problem with Applications to Data Streams. - Mark Braverman; Sumegha Garg; David P. Woodruff (Electron. Colloquium Comput. Complex., 2020)

Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations. - Itai Ashlagi; Mark Braverman; Yash Kanoria; Peng Shi 002 (Manag. Sci., 2020)

Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs. - Mark Braverman; Gil Cohen; Sumegha Garg (SIAM J. Comput., 2020)

Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. - Mark Braverman; Dor Minzer (CCC, 2021)

Near Optimal Distributed Learning of Halfspaces with Two Parties. - Mark Braverman; Gillat Kol; Shay Moran; Raghuvansh R. Saxena (COLT, 2021)

Statistically Near-Optimal Hypothesis Selection. - Olivier Bousquet; Mark Braverman; Gillat Kol; Klim Efremenko; Shay Moran (FOCS, 2021)

An Invariance Principle for the Multi-slice, with Applications. - Mark Braverman; Subhash Khot; Noam Lifshitz; Dor Minzer (FOCS, 2021)

Tiered Random Matching Markets: Rank Is Proportional to Popularity. - Itai Ashlagi; Mark Braverman; Amin Saberi; Clayton Thomas; Geng Zhao 002 (ITCS, 2021)

Prior-free Dynamic Mechanism Design With Limited Liability. - Mark Braverman; Jon Schneider; S. Matthew Weinberg (EC, 2021)

New separations results for external information. - Mark Braverman; Dor Minzer (STOC, 2021)

Optimization-friendly generic mechanisms without money. - Mark Braverman (CoRR, 2021)

Tight Space Complexity of the Coin Problem. - Mark Braverman; Sumegha Garg; Or Zamir (Electron. Colloquium Comput. Complex., 2021)

Unbiased Delay Measurement in the Data Plane. - Yufei Zheng; Xiaoqi Chen; Mark Braverman; Jennifer Rexford (APOCS, 2022)

Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. - Mark Braverman; Mahsa Derakhshan; Antonio Molina Lovett (EC, 2022)

Empirical Characteristics of Affordable Care Act Risk Transfer Payments. - Grace Guan; Mark Braverman (CoRR, 2022)

Round-vs-Resilience Tradeoffs for Binary Feedback Channels. - Mark Braverman; Klim Efremenko; Gillat Kol; Raghuvansh Saxena; Zhijun Zhang 007 (Electron. Colloquium Comput. Complex., 2022)

Parallel Repetition for the GHZ Game: Exponential Decay. - Mark Braverman; Subhash Khot; Dor Minzer (Electron. Colloquium Comput. Complex., 2022)

Optimal Short-Circuit Resilient Formulas. - Mark Braverman; Klim Efremenko; Ran Gelles; Michael A. Yitayew (J. ACM, 2022)

Pebbles and Branching Programs for Tree Evaluation. - Stephen A. Cook; Pierre McKenzie; Dustin Wehr; Mark Braverman; Rahul Santhanam (Logic, Automata, and Computational Complexity, 2023)

Understanding Influence Functions and Datamodels via Harmonic Analysis. - Nikunj Saunshi; Arushi Gupta; Mark Braverman; Sanjeev Arora (ICLR, 2023)

Improved Monotonicity Testers via Hypercube Embeddings. - Mark Braverman; Subhash Khot; Guy Kindler; Dor Minzer (ITCS, 2023)

Rounding via Low Dimensional Embeddings. - Mark Braverman; Dor Minzer (ITCS, 2023)

Welfare Distribution in Two-sided Random Matching Markets. - Itai Ashlagi; Mark Braverman; Geng Zhao 002 (EC, 2023)

Parallel Repetition of k-Player Projection Games. - Amey Bhangale; Mark Braverman; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2023)

Tight Analyses of Ordered and Unordered Linear Probing. - Mark Braverman; William Kuszmaul (FOCS, 2024)

Multi-Party Set Disjointness and Intersection with Bounded Dependence. - Mark Braverman; Rotem Oshman; Tal Roth (PODC, 2024)

A New Information Complexity Measure for Multi-pass Streaming with Applications. - Mark Braverman; Sumegha Garg; Qian Li 012; Shuo Wang; David P. Woodruff; Jiapeng Zhang (STOC, 2024)

Optimality of Frequency Moment Estimation. - Mark Braverman; Or Zamir (Electron. Colloquium Comput. Complex., 2024)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. - Mark Braverman; Mahsa Derakhshan; Tristan Pollner; Amin Saberi; David Wajc (SODA, 2025)

Parallel Repetition for 3-Player XOR Games. - Amey Bhangale; Mark Braverman; Subhash Khot; Yang P. Liu; Dor Minzer (Electron. Colloquium Comput. Complex., 2025)

Sublinear-Overhead Secure Linear Algebra on a Dishonest Server. - Mark Braverman; Stephen Newman (CoRR, 2025)

A New Benchmark for Online Learning with Budget-Balancing Constraints. - Mark Braverman; Jingyi Liu; Jieming Mao; Jon Schneider; Eric Xue 001 (CoRR, 2025)