Mark Braverman

250 papers A* 64A 23B 1C 3Misc 1Journal 142Unranked 13

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Stronger core results with multidimensional prices. CoRR Mark Braverman, Jingyi Liu, Eric Xue, Chenghan Zhou
2025	J	`jnl`	A New Benchmark for Online Learning with Budget-Balancing Constraints. CoRR Mark Braverman, Jingyi Liu, Jieming Mao, Jon Schneider, Eric Xue
2025	J	`jnl`	An Analytical Approach to Parallel Repetition via CSP Inverse Theorems. CoRR Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
2025	J	`jnl`	An Analytical Approach to Parallel Repetition via CSP Inverse Theorems. Electron. Colloquium Comput. Complex. Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
2025	A*	`conf`	New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. SODA Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc
2025	A*	`conf`	Optimality of Frequency Moment Estimation. STOC Mark Braverman, Or Zamir
2025	A*	`conf`	Parallel Repetition for 3-Player XOR Games. STOC Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2025	J	`jnl`	Parallel Repetition for 3-Player XOR Games. Electron. Colloquium Comput. Complex. Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2025	—	`conf`	Practical Secure Delegated Linear Algebra with Trapdoored Matrices. TCC (1) Mark Braverman, Stephen Newman
2025	A	`conf`	Round-Vs-Resilience Tradeoffs for Binary Feedback Channels. ITCS Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2025	J	`jnl`	Sublinear-Overhead Secure Linear Algebra on a Dishonest Server. CoRR Mark Braverman, Stephen Newman
2025	J	`jnl`	Tight Analyses of Ordered and Unordered Linear Probing. CoRR Mark Braverman, William Kuszmaul
2025	A*	`conf`	Undirected Multicast Network Coding Gaps via Locally Decodable Codes. FOCS Mark Braverman, Zhongtian He
2025	J	`jnl`	Undirected Multicast Network Coding Gaps via Locally Decodable Codes. CoRR Mark Braverman, Zhongtian He
2024	A*	`conf`	A New Information Complexity Measure for Multi-pass Streaming with Applications. STOC Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024	J	`jnl`	A New Information Complexity Measure for Multi-pass Streaming with Applications. CoRR Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
2024	A*	`conf`	Multi-Party Set Disjointness and Intersection with Bounded Dependence. PODC Mark Braverman, Rotem Oshman, Tal Roth
2024	J	`jnl`	New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. CoRR Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc
2024	J	`jnl`	Optimality of Frequency Moment Estimation. CoRR Mark Braverman, Or Zamir
2024	J	`jnl`	Optimality of Frequency Moment Estimation. Electron. Colloquium Comput. Complex. Mark Braverman, Or Zamir
2024	J	`jnl`	Parallel Repetition for 3-Player XOR Games. CoRR Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2024	A	`conf`	Parallel Repetition of k-Player Projection Games. APPROX/RANDOM Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2024	A*	`conf`	Tight Analyses of Ordered and Unordered Linear Probing. FOCS Mark Braverman, William Kuszmaul
2023	A	`conf`	Improved Monotonicity Testers via Hypercube Embeddings. ITCS Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2023	A*	`conf`	Parallel Repetition for the GHZ Game: Exponential Decay. FOCS Mark Braverman, Subhash Khot, Dor Minzer
2023	J	`jnl`	Parallel Repetition of k-Player Projection Games. CoRR Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2023	J	`jnl`	Parallel Repetition of k-Player Projection Games. Electron. Colloquium Comput. Complex. Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
2023	—	`ch.`	Pebbles and Branching Programs for Tree Evaluation. Logic, Automata, and Computational Complexity Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2023	A	`conf`	Rounding via Low Dimensional Embeddings. ITCS Mark Braverman, Dor Minzer
2023	A*	`conf`	Understanding Influence Functions and Datamodels via Harmonic Analysis. ICLR Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora
2023	A*	`conf`	Welfare Distribution in Two-sided Random Matching Markets. EC Itai Ashlagi, Mark Braverman, Geng Zhao
2023	J	`jnl`	Welfare Distribution in Two-sided Random Matching Markets. CoRR Itai Ashlagi, Mark Braverman, Geng Zhao
2022	A	`ed.`	13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Berkeley, CA, USA, January 31 - February 3, 2022 ITCS Mark Braverman
2022	J	`jnl`	Empirical Characteristics of Affordable Care Act Risk Transfer Payments. CoRR Grace Guan, Mark Braverman
2022	J	`jnl`	Improved Monotonicity Testers via Hypercube Embeddings. CoRR Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer
2022	A*	`conf`	Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. EC Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett
2022	J	`jnl`	Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. CoRR Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett
2022	J	`jnl`	Optimal Short-Circuit Resilient Formulas. J. ACM Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
2022	J	`jnl`	Parallel Repetition for the GHZ Game: Exponential Decay. CoRR Mark Braverman, Subhash Khot, Dor Minzer
2022	J	`jnl`	Parallel Repetition for the GHZ Game: Exponential Decay. Electron. Colloquium Comput. Complex. Mark Braverman, Subhash Khot, Dor Minzer
2022	J	`jnl`	Round-vs-Resilience Tradeoffs for Binary Feedback Channels. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2022	J	`jnl`	Rounding via Low Dimensional Embeddings. CoRR Mark Braverman, Dor Minzer
2022	—	`conf`	Unbiased Delay Measurement in the Data Plane. APOCS Yufei Zheng, Xiaoqi Chen, Mark Braverman, Jennifer Rexford
2022	J	`jnl`	Understanding Influence Functions and Datamodels via Harmonic Analysis. CoRR Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora
2021	A*	`conf`	An Invariance Principle for the Multi-slice, with Applications. FOCS Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
2021	J	`jnl`	An Invariance Principle for the Multi-slice, with Applications. CoRR Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer
2021	A*	`conf`	Near Optimal Distributed Learning of Halfspaces with Two Parties. COLT Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
2021	J	`jnl`	New Separations Results for External Information. CoRR Mark Braverman, Dor Minzer
2021	A*	`conf`	New separations results for external information. STOC Mark Braverman, Dor Minzer
2021	A	`conf`	On Rich 2-to-1 Games. ITCS Mark Braverman, Subhash Khot, Dor Minzer
2021	A	`conf`	Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. CCC Mark Braverman, Dor Minzer
2021	J	`jnl`	Optimization-friendly generic mechanisms without money. CoRR Mark Braverman
2021	A*	`conf`	Prior-free Dynamic Mechanism Design With Limited Liability. EC Mark Braverman, Jon Schneider, S. Matthew Weinberg
2021	J	`jnl`	Prior-free Dynamic Mechanism Design With Limited Liability. CoRR Mark Braverman, Jon Schneider, S. Matthew Weinberg
2021	A*	`conf`	Statistically Near-Optimal Hypothesis Selection. FOCS Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran
2021	J	`jnl`	Statistically Near-Optimal Hypothesis Selection. CoRR Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, Shay Moran
2021	A	`conf`	Tiered Random Matching Markets: Rank Is Proportional to Popularity. ITCS Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao
2021	A*	`conf`	Tight Space Complexity of the Coin Problem. FOCS Mark Braverman, Sumegha Garg, Or Zamir
2021	J	`jnl`	Tight Space Complexity of the Coin Problem. Electron. Colloquium Comput. Complex. Mark Braverman, Sumegha Garg, Or Zamir
2020	A*	`conf`	BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time. SIGCOMM Xiaoqi Chen, Shir Landau Feibish, Mark Braverman, Jennifer Rexford
2020	A*	`conf`	Calibration, Entropy Rates, and Memory in Language Models. ICML Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang
2020	J	`jnl`	Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations. Manag. Sci. Itai Ashlagi, Mark Braverman, Yash Kanoria, Peng Shi
2020	J	`jnl`	Optimal tiling of the Euclidean space using symmetric bodies. CoRR Mark Braverman, Dor Minzer
2020	J	`jnl`	Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs. SIAM J. Comput. Mark Braverman, Gil Cohen, Sumegha Garg
2020	A*	`conf`	The Coin Problem with Applications to Data Streams. FOCS Mark Braverman, Sumegha Garg, David P. Woodruff
2020	J	`jnl`	The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. Mark Braverman, Sumegha Garg, David P. Woodruff
2020	A*	`conf`	The Gradient Complexity of Linear Regression. COLT Mark Braverman, Elad Hazan, Max Simchowitz, Blake E. Woodworth
2020	—	`conf`	The Role of Randomness and Noise in Strategic Classification. FORC Mark Braverman, Sumegha Garg
2020	J	`jnl`	The Role of Randomness and Noise in Strategic Classification. CoRR Mark Braverman, Sumegha Garg
2020	J	`jnl`	Tiered Random Matching Markets: Rank is Proportional to Popularity. CoRR Itai Ashlagi, Mark Braverman, Clayton Thomas, Geng Zhao
2019	J	`jnl`	Calibration, Entropy Rates, and Memory in Language Models. CoRR Mark Braverman, Xinyi Chen, Sham M. Kakade, Karthik Narasimhan, Cyril Zhang, Yi Zhang
2019	J	`jnl`	Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility. CoRR Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
2019	A*	`conf`	Multi-armed Bandit Problems with Strategic Arms. COLT Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
2019	J	`jnl`	On Rich $2$-to-$1$ Games. Electron. Colloquium Comput. Complex. Mark Braverman, Subhash Khot, Dor Minzer
2019	A	`conf`	On the Computational Power of Radio Channels. DISC Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
2019	A	`conf`	Optimal Short-Circuit Resilient Formulas. CCC Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
2019	J	`jnl`	Reliable communication over highly connected noisy networks. Distributed Comput. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2019	A*	`conf`	Sorted Top-k in Rounds. COLT Mark Braverman, Jieming Mao, Yuval Peres
2019	J	`jnl`	Sorted Top-k in Rounds. CoRR Mark Braverman, Jieming Mao, Yuval Peres
2019	J	`jnl`	Space-bounded Church-Turing thesis and computational tractability of closed systems. CoRR Mark Braverman, Cristobal Rojas, Jonathan Schneider
2019	J	`jnl`	The Price of Uncertain Priors in Source Coding. IEEE Trans. Inf. Theory Mark Braverman, Brendan Juba
2019	J	`jnl`	The gradient complexity of linear regression. CoRR Mark Braverman, Elad Hazan, Max Simchowitz, Blake E. Woodworth
2018	A	`conf`	A Candidate for a Strong Separation of Information and Communication. ITCS Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
2018	J	`jnl`	Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2018	A*	`conf`	Hitting sets with near-optimal error for read-once branching programs. STOC Mark Braverman, Gil Cohen, Sumegha Garg
2018	A	`conf`	Information Value of Two-Prover Games. ITCS Mark Braverman, Young Kun-Ko
2018	A*	`conf`	Interactive compression to external information. STOC Mark Braverman, Gillat Kol
2018	J	`jnl`	Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness. SIAM J. Comput. Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette
2018	A*	`conf`	On Simultaneous Two-player Combinatorial Auctions. SODA Mark Braverman, Jieming Mao, S. Matthew Weinberg
2018	J	`jnl`	Optimal Short-Circuit Resilient Formulas. CoRR Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew
2018	A*	`conf`	Selling to a No-Regret Buyer. EC Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
2018	—	`conf`	Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. APPROX-RANDOM Mark Braverman, Young Kun-Ko
2018	J	`jnl`	The Price of Uncertain Priors in Source Coding. CoRR Mark Braverman, Brendan Juba
2017	A*	`conf`	A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. FOCS Mark Braverman, Rotem Oshman
2017	J	`jnl`	Coding for Interactive Communication Correcting Insertions and Deletions. IEEE Trans. Inf. Theory Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
2017	A	`conf`	Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All. ITCS Mark Braverman, Sumegha Garg, Ariel Schvartzman
2017	A*	`conf`	Communication Requirements and Informative Signaling in Matching Markets. EC Itai Ashlagi, Mark Braverman, Yash Kanoria, Peng Shi
2017	A*	`conf`	ETH Hardness for Densest- SODA Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2017	J	`jnl`	Hitting Sets with Near-Optimal Error for Read-Once Branching Programs. Electron. Colloquium Comput. Complex. Mark Braverman, Gil Cohen, Sumegha Garg
2017	J	`jnl`	Information Value of Two-Prover Games. Electron. Colloquium Comput. Complex. Mark Braverman, Young Kun-Ko
2017	J	`jnl`	Interactive Information Complexity. SIAM Rev. Mark Braverman
2017	J	`jnl`	List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. SIAM J. Comput. Mark Braverman, Klim Efremenko
2017	J	`jnl`	Multi-armed Bandit Problems with Strategic Arms. CoRR Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
2017	J	`jnl`	Nash Equilibria in Perturbation-Stable Games. Theory Comput. Maria-Florina Balcan, Mark Braverman
2017	J	`jnl`	On Simultaneous Two-player Combinatorial Auctions. CoRR Mark Braverman, Jieming Mao, S. Matthew Weinberg
2017	J	`jnl`	Selling to a No-Regret Buyer. CoRR Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg
2017	J	`jnl`	Strategyproof Mechanisms for Competitive Influence in Networks. Algorithmica Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
2016	J	`jnl`	A Discrepancy Lower Bound for Information Complexity. Algorithmica Mark Braverman, Omri Weinstein
2016	A*	`conf`	Coding for Interactive Communication Correcting Insertions and Deletions. ICALP Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
2016	A*	`conf`	Communication lower bounds for statistical estimation problems via a distributed data processing inequality. STOC Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
2016	A*	`conf`	Constant-rate coding for multiparty interactive communication is impossible. STOC Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	J	`jnl`	Guest Editorial for Information Complexity and Applications. Algorithmica Mark Braverman, David P. Woodruff
2016	A*	`conf`	Information Complexity Is Computable. ICALP Mark Braverman, Jon Schneider
2016	J	`jnl`	Information Lower Bounds via Self-Reducibility. Theory Comput. Syst. Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2016	A*	`conf`	Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. SODA Mark Braverman, Jieming Mao, S. Matthew Weinberg
2016	J	`jnl`	Network coding in undirected graphs is either very helpful or not helpful at all. CoRR Mark Braverman, Sumegha Garg, Ariel Schvartzman
2016	J	`jnl`	Optimal Provision-After-Wait in Healthcare. Math. Oper. Res. Mark Braverman, Jing Chen, Sampath Kannan
2016	J	`jnl`	Optimal Resilience for Short-Circuit Noise in Formulas. Electron. Colloquium Comput. Complex. Mark Braverman, Ran Gelles, Michael A. Yitayew
2016	J	`jnl`	Parallel Algorithms for Select and Partition with Noisy Comparisons. CoRR Mark Braverman, Jieming Mao, S. Matthew Weinberg
2016	A*	`conf`	Parallel algorithms for select and partition with noisy comparisons. STOC Mark Braverman, Jieming Mao, S. Matthew Weinberg
2016	A*	`conf`	Reliable Communication over Highly Connected Noisy Networks. PODC Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	A*	`conf`	An Interactive Information Odometer and Applications. STOC Mark Braverman, Omri Weinstein
2015	A*	`conf`	Approximating the best Nash Equilibrium in SODA Mark Braverman, Young Kun-Ko, Omri Weinstein
2015	J	`jnl`	Coding for interactive communication correcting insertions and deletions. CoRR Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
2015	J	`jnl`	Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality. CoRR Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
2015	J	`jnl`	Constant-rate coding for multiparty interactive communication is impossible. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	J	`jnl`	ETH Hardness for Densest- Electron. Colloquium Comput. Complex. Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2015	J	`jnl`	ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. CoRR Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2015	J	`jnl`	Information complexity is computable. CoRR Mark Braverman, Jon Schneider
2015	J	`jnl`	Information complexity is computable. Electron. Colloquium Comput. Complex. Mark Braverman, Jon Schneider
2015	J	`jnl`	Interactive Information Complexity. SIAM J. Comput. Mark Braverman
2015	J	`jnl`	Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. CoRR Mark Braverman, Jieming Mao, S. Matthew Weinberg
2015	A*	`conf`	Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. FOCS Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette
2015	J	`jnl`	Near-optimal bounds on bounded-round quantum communication complexity of disjointness. CoRR Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette
2015	J	`jnl`	Near-optimal bounds on bounded-round quantum communication complexity of disjointness. Electron. Colloquium Comput. Complex. Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette
2015	A*	`conf`	On Information Complexity in the Broadcast Model. PODC Mark Braverman, Rotem Oshman
2015	J	`jnl`	Reliable Communication over Highly Connected Noisy Networks. Electron. Colloquium Comput. Complex. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	A	`conf`	Simulating Noisy Channel Interaction. ITCS Mark Braverman, Jieming Mao
2015	A*	`conf`	Small Value Parallel Repetition for General Games. STOC Mark Braverman, Ankit Garg
2015	J	`jnl`	The Communication Complexity of Number-In-Hand Set Disjointness with No Promise. Electron. Colloquium Comput. Complex. Mark Braverman, Rotem Oshman
2015	—	`conf`	The price of uncertainty in communication. Allerton Mark Braverman, Brendan Juba
2015	J	`jnl`	Tight space-noise tradeoffs in computing the ergodic measure. CoRR Mark Braverman, Cristobal Rojas, Jon Schneider
2014	J	`jnl`	An Interactive Information Odometer with Applications. Electron. Colloquium Comput. Complex. Mark Braverman, Omri Weinstein
2014	J	`jnl`	Approximating the best Nash Equilibrium in n Electron. Colloquium Comput. Complex. Mark Braverman, Young Kun-Ko, Omri Weinstein
2014	J	`jnl`	Contracting Experts With Unknown Cost Structures. CoRR Mark Braverman, Gal Oshri
2014	J	`jnl`	Information Equals Amortized Communication. IEEE Trans. Inf. Theory Mark Braverman, Anup Rao
2014	A*	`conf`	List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. FOCS Mark Braverman, Klim Efremenko
2014	J	`jnl`	List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko
2014	A	`conf`	Optimal provision-after-wait in healthcare. ITCS Mark Braverman, Jing Chen, Sampath Kannan
2014	J	`jnl`	Pseudorandom Generators for Regular Branching Programs. SIAM J. Comput. Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2014	—	`conf`	Public vs Private Coin in Bounded-Round Information. ICALP (1) Mark Braverman, Ankit Garg
2014	J	`jnl`	Simulating Noisy Channel Interaction. CoRR Mark Braverman, Jieming Mao
2014	J	`jnl`	Simulating Noisy Channel Interaction. Electron. Colloquium Comput. Complex. Mark Braverman, Jieming Mao
2014	J	`jnl`	Small value parallel repetition for general games. Electron. Colloquium Comput. Complex. Mark Braverman, Ankit Garg
2014	J	`jnl`	Stability in Large Matching Markets with Complementarities. Oper. Res. Itai Ashlagi, Mark Braverman, Avinatan Hassidim
2014	A	`conf`	The computational hardness of pricing compound options. ITCS Mark Braverman, Kanika Pasricha
2014	J	`jnl`	The computational hardness of pricing compound options. Electron. Colloquium Comput. Complex. Mark Braverman, Kanika Pasricha
2014	J	`jnl`	Toward Coding for Maximum Errors in Interactive Communication. IEEE Trans. Inf. Theory Mark Braverman, Anup Rao
2013	A*	`conf`	A Tight Bound for Set Disjointness in the Message-Passing Model. FOCS Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
2013	—	`conf`	A hard-to-compress interactive task? Allerton Mark Braverman
2013	A*	`conf`	An information complexity approach to extended formulations. STOC Mark Braverman, Ankur Moitra
2013	J	`jnl`	Computing with real numbers, from Archimedes to Turing and beyond. Commun. ACM Mark Braverman
2013	—	`conf`	Direct Product via Round-Preserving Compression. ICALP (1) Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013	A*	`conf`	Direct Products in Communication Complexity. FOCS Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013	J	`jnl`	Direct product via round-preserving compression. Electron. Colloquium Comput. Complex. Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013	A*	`conf`	Finding Endogenously Formed Communities. SODA Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, Shang-Hua Teng
2013	A*	`conf`	From information to exact communication. STOC Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2013	J	`jnl`	How to Compress Interactive Communication. SIAM J. Comput. Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2013	J	`jnl`	Inapproximability of NP-Complete Variants of Nash Equilibrium. Theory Comput. Per Austrin, Mark Braverman, Eden Chlamtac
2013	Misc	`conf`	Information Lower Bounds via Self-reducibility. CSR Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2013	C	`conf`	Noise versus Computational Intractability in Dynamics. CiE Mark Braverman
2013	A	`conf`	On the convergence of the Hegselmann-Krause system. ITCS Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy L. Nguyen
2013	J	`jnl`	Optimal Provision-After-Wait in Healthcare. CoRR Mark Braverman, Jing Chen, Sampath Kannan
2013	J	`jnl`	Public vs private coin in bounded-round information. Electron. Colloquium Comput. Complex. Mark Braverman, Ankit Garg
2013	J	`jnl`	Search using queries on indistinguishable items CoRR Mark Braverman, Gal Oshri
2013	A	`conf`	Search using queries on indistinguishable items. STACS Mark Braverman, Gal Oshri
2013	J	`jnl`	Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009). SIAM J. Comput. Maria-Florina Balcan, Mark Braverman, Daniel A. Spielman
2013	A*	`conf`	Strategyproof mechanisms for competitive influence in networks. WWW Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
2013	J	`jnl`	Tight Bounds for Set Disjointness in the Message Passing Model CoRR Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
2012	—	`conf`	A Discrepancy Lower Bound for Information Complexity. APPROX-RANDOM Mark Braverman, Omri Weinstein
2012	J	`jnl`	An Information Complexity Approach to Extended Formulations. Electron. Colloquium Comput. Complex. Mark Braverman, Ankur Moitra
2012	—	`conf`	Coding for interactive computation: Progress and challenges. Allerton Conference Mark Braverman
2012	J	`jnl`	Direct Products in Communication Complexity. Electron. Colloquium Comput. Complex. Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2012	J	`jnl`	From Information to Exact Communication. Electron. Colloquium Comput. Complex. Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2012	J	`jnl`	I Like Her more than You: Self-determined Communities CoRR Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, Shang-Hua Teng
2012	J	`jnl`	Information lower bounds via self-reducibility. Electron. Colloquium Comput. Complex. Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
2012	A*	`conf`	Interactive information complexity. STOC Mark Braverman
2012	J	`jnl`	Noise vs computational intractability in dynamics CoRR Mark Braverman, Alexander Grigo, Cristobal Rojas
2012	A	`conf`	Noise vs computational intractability in dynamics. ITCS Mark Braverman, Alexander Grigo, Cristobal Rojas
2012	J	`jnl`	On the Convergence of the Hegselmann-Krause System CoRR Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy L. Nguyen
2012	J	`jnl`	Pebbles and Branching Programs for Tree Evaluation. ACM Trans. Comput. Theory Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2012	A	`conf`	Towards deterministic tree code constructions. ITCS Mark Braverman
2012	J	`jnl`	Truthful Mechanisms for Competing Submodular Processes CoRR Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
2011	J	`jnl`	A discrepancy lower bound for information complexity CoRR Mark Braverman, Omri Weinstein
2011	J	`jnl`	A discrepancy lower bound for information complexity. Electron. Colloquium Comput. Complex. Mark Braverman, Omri Weinstein
2011	J	`jnl`	Inapproximability of NP-Complete Variants of Nash Equilibrium CoRR Per Austrin, Mark Braverman, Eden Chlamtac
2011	—	`conf`	Inapproximability of NP-Complete Variants of Nash Equilibrium. APPROX-RANDOM Per Austrin, Mark Braverman, Eden Chlamtac
2011	J	`jnl`	Information Equals Amortized Communication CoRR Mark Braverman, Anup Rao
2011	A*	`conf`	Information Equals Amortized Communication. FOCS Mark Braverman, Anup Rao
2011	J	`jnl`	Interactive information complexity. Electron. Colloquium Comput. Complex. Mark Braverman
2011	A	`conf`	Leaky Pseudo-Entropy Functions. ICS Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai
2011	A*	`conf`	Matching with couples revisited. EC Itai Ashlagi, Mark Braverman, Avinatan Hassidim
2011	J	`jnl`	Poly-logarithmic independence fools bounded-depth boolean circuits. Commun. ACM Mark Braverman
2011	A*	`conf`	The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2011	J	`jnl`	The Grothendieck constant is strictly smaller than Krivine's bound. CoRR Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2011	A*	`conf`	Towards coding for maximum errors in interactive communication. STOC Mark Braverman, Anup Rao
2011	J	`jnl`	Towards deterministic tree code constructions. Electron. Colloquium Comput. Complex. Mark Braverman
2010	J	`jnl`	Approximate Nash Equilibria under Stability Conditions CoRR Maria-Florina Balcan, Mark Braverman
2010	J	`jnl`	Efficient Communication Using Partial Information. Electron. Colloquium Comput. Complex. Mark Braverman, Anup Rao
2010	A*	`conf`	How to compress interactive communication. STOC Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2010	J	`jnl`	Matching with Couples Revisited CoRR Itai Ashlagi, Mark Braverman, Avinatan Hassidim
2010	J	`jnl`	Pebbles and Branching Programs for Tree Evaluation CoRR Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2010	J	`jnl`	Polylogarithmic independence fools J. ACM Mark Braverman
2010	A*	`conf`	Pseudorandom Generators for Regular Branching Programs. FOCS Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010	J	`jnl`	Pseudorandom Generators for Regular Branching Programs. Electron. Colloquium Comput. Complex. Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010	J	`jnl`	Towards Coding for Maximum Errors in Interactive Communication. Electron. Colloquium Comput. Complex. Mark Braverman, Anup Rao
2009	B	`conf`	Branching Programs for Tree Evaluation. MFCS Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009	C	`conf`	Computability and Complexity of Julia Sets (Invited Talk). CCA Mark Braverman
2009	—	`book`	Computability of Julia Sets. Mark Braverman, Michael Yampolsky
2009	J	`jnl`	Direct Sums in Randomized Communication Complexity. Electron. Colloquium Comput. Complex. Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2009	A*	`conf`	Finding Low Error Clusterings. COLT Maria-Florina Balcan, Mark Braverman
2009	—	`conf`	Fractional Pebbling and Thrifty Branching Programs. FSTTCS Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009	A	`conf`	Poly-logarithmic Independence Fools AC CCC Mark Braverman
2009	J	`jnl`	Poly-logarithmic independence fools AC0 circuits. Electron. Colloquium Comput. Complex. Mark Braverman
2009	J	`jnl`	Sorting from Noisy Information CoRR Mark Braverman, Elchanan Mossel
2009	J	`jnl`	Space-Efficient Counting in Graphs on Surfaces. Comput. Complex. Mark Braverman, Raghav Kulkarni, Sambuddha Roy
2009	A*	`conf`	The complexity of simulating Brownian Motion. SODA Ilia Binder, Mark Braverman
2008	—	`—`	Computability and complexity of Julia sets. Mark Braverman
2008	A*	`conf`	Noisy sorting without resampling. SODA Mark Braverman, Elchanan Mossel
2008	J	`jnl`	On ad hoc routing with guaranteed delivery CoRR Mark Braverman
2008	A*	`conf`	On ad hoc routing with guaranteed delivery. PODC Mark Braverman
2008	J	`jnl`	The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi
2007	A*	`conf`	Constructing non-computable Julia sets. STOC Mark Braverman, Michael Yampolsky
2007	—	`conf`	Derandomization of Euclidean Random Walks. APPROX-RANDOM Ilia Binder, Mark Braverman
2007	J	`jnl`	Filled Julia Sets with Empty Interior Are Computable. Found. Comput. Math. Ilia Binder, Mark Braverman, Michael Yampolsky
2007	J	`jnl`	Noisy Sorting Without Resampling CoRR Mark Braverman, Elchanan Mossel
2007	A	`conf`	Parity Problems in Planar Graphs. CCC Mark Braverman, Raghav Kulkarni, Sambuddha Roy
2007	J	`jnl`	Parity Problems in Planar Graphs. Electron. Colloquium Comput. Complex. Mark Braverman, Raghav Kulkarni, Sambuddha Roy
2006	J	`jnl`	Constructing Non-Computable Julia Sets CoRR Mark Braverman, Michael Yampolsky
2006	A*	`conf`	Termination of Integer Linear Programs. CAV Mark Braverman
2005	J	`jnl`	Computing over the Reals: Foundations for Scientific Computing CoRR Mark Braverman, Stephen A. Cook
2005	J	`jnl`	On computational complexity of Riemann mapping CoRR Ilia Binder, Mark Braverman, Michael Yampolsky
2005	J	`jnl`	On computational complexity of Siegel Julia sets CoRR Ilia Binder, Mark Braverman, Michael Yampolsky
2005	J	`jnl`	On the Complexity of Real Functions CoRR Mark Braverman
2005	A*	`conf`	On the Complexity of Real Functions. FOCS Mark Braverman
2004	J	`jnl`	Filled Julia sets with empty interior are computable CoRR Ilia Binder, Mark Braverman, Michael Yampolsky
2004	C	`conf`	Hyperbolic Julia Sets are Poly-Time Computable. CCA Mark Braverman
2004	A*	`conf`	Learnability and Automatizability. FOCS Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi
2004	J	`jnl`	Non-computable Julia sets CoRR Mark Braverman, Michael Yampolsky
2001	J	`jnl`	A Monte Carlo Algorithm for a Lottery Problem. Monte Carlo Methods Appl. Mark Braverman, Shay Gueron