Mark Braverman
#77,169
Most Influential Person Now
Israeli mathematician and computer scientist
Mark Braverman 's AcademicInfluence.com Rankings
Mark Braverman computer-science Degrees
Computer Science
#3445
World Rank
#3615
Historical Rank
Theoretical Computer Science
#74
World Rank
#74
Historical Rank
Mark Braverman mathematics Degrees
Mathematics
#5567
World Rank
#7825
Historical Rank
Complexity Theory
#17
World Rank
#17
Historical Rank
Algebraic Geometry
#183
World Rank
#191
Historical Rank
Geometry
#195
World Rank
#271
Historical Rank
Download Badge
Computer Science Mathematics
Why Is Mark Braverman Influential?
(Suggest an Edit or Addition)According to Wikipedia, Mark Braverman is an Israeli mathematician and theoretical computer scientist. He was awarded an EMS Prize in 2016 as well as Presburger Award in the same year. In 2019, he was awarded the Alan T. Waterman Award. In 2022 he won the IMU Abacus Medal.
Mark Braverman 's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- How to compress interactive communication (2010) (236)
- Information Equals Amortized Communication (2011) (202)
- Affect comprehension in children with pervasive developmental disorders (1989) (190)
- Noisy sorting without resampling (2007) (189)
- Interactive information complexity (2012) (180)
- Communication lower bounds for statistical estimation problems via a distributed data processing inequality (2015) (147)
- Termination of Integer Linear Programs (2006) (136)
- Toward Coding for Maximum Errors in Interactive Communication (2011) (117)
- Computing over the Reals: Foundations for Scientific Computing (2005) (108)
- Data-Driven Decisions for Reducing Readmissions for Heart Failure: General Methodology and Case Study (2014) (106)
- Poly-logarithmic Independence Fools AC^0 Circuits (2009) (105)
- An information complexity approach to extended formulations (2013) (101)
- Stability in Large Matching Markets with Complementarities (2014) (96)
- Monotonicity and Implementability (2010) (96)
- The Grothendieck Constant is Strictly Smaller than Krivine's Bound (2011) (88)
- Non-computable Julia sets (2004) (81)
- On the convergence of the Hegselmann-Krause system (2012) (77)
- From information to exact communication (2013) (75)
- A Tight Bound for Set Disjointness in the Message-Passing Model (2013) (74)
- Pseudorandom Generators for Regular Branching Programs (2010) (74)
- Position Auctions with Budgets: Existence and Uniqueness (2010) (73)
- Direct Products in Communication Complexity (2013) (72)
- Sorting from Noisy Information (2009) (71)
- Towards deterministic tree code constructions (2012) (68)
- Computability of Julia Sets (2006) (68)
- List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise (2014) (67)
- On the complexity of real functions (2005) (58)
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis (2015) (58)
- Public vs Private Coin in Bounded-Round Information (2014) (53)
- Finding Endogenously Formed Communities (2012) (49)
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness (2015) (48)
- Coding for Interactive Communication Correcting Insertions and Deletions (2015) (48)
- Parallel algorithms for select and partition with noisy comparisons (2016) (47)
- Learnability and automatizability (2004) (46)
- BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time (2020) (46)
- The complexity of properly learning simple concept classes (2008) (45)
- A Discrepancy Lower Bound for Information Complexity (2011) (43)
- Small Value Parallel Repetition for General Games (2015) (39)
- Selling to a No-Regret Buyer (2017) (38)
- Mafia: A theoretical study of players and coalitions in a partial information environment (2006) (37)
- Direct Product via Round-Preserving Compression (2013) (35)
- Finding Low Error Clusterings (2009) (35)
- Poly-logarithmic independence fools bounded-depth boolean circuits (2011) (35)
- Inapproximability of NP-Complete Variants of Nash Equilibrium (2011) (33)
- On the computational complexity of the Riemann mapping (2005) (32)
- Coding for interactive computation: Progress and challenges (2012) (32)
- Parabolic Julia sets are polynomial time computable (2005) (31)
- Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations (2018) (31)
- Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable (2004) (31)
- Reliable communication over highly connected noisy networks (2016) (30)
- Strategyproof Mechanisms for Competitive Influence in Networks (2013) (30)
- Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness (2015) (28)
- An Interactive Information Odometer and Applications (2015) (28)
- Filled Julia Sets with Empty Interior Are Computable (2004) (28)
- Constant-Rate Coding for Multiparty Interactive Communication Is Impossible (2017) (27)
- Pebbles and Branching Programs for Tree Evaluation (2010) (26)
- An algorithm to improve the computational efficiency of genetic linkage analysis. (1985) (26)
- Matching with couples revisited (2010) (26)
- Hyperbolic Julia Sets are Poly-Time Computable (2005) (26)
- The Role of Randomness and Noise in Strategic Classification (2020) (26)
- On Computational Complexity of Siegel Julia Sets (2005) (24)
- Computability of Brolin-Lyubich Measure (2010) (21)
- Information Lower Bounds via Self-Reducibility (2013) (21)
- Calibration, Entropy Rates, and Memory in Language Models (2019) (20)
- Leaky Pseudo-Entropy Functions (2011) (19)
- The gradient complexity of linear regression (2019) (18)
- The rate of convergence of the Walk on Spheres Algorithm (2008) (17)
- Thurston equivalence to a rational map is decidable (2010) (17)
- Multi-armed Bandit Problems with Strategic Arms (2017) (17)
- Hitting sets with near-optimal error for read-once branching programs (2018) (16)
- On Simultaneous Two-player Combinatorial Auctions (2017) (15)
- A hard-to-compress interactive task? (2013) (15)
- On Information Complexity in the Broadcast Model (2015) (15)
- Analysis of Medicare Pay-for-Performance Contracts (2016) (15)
- Noise vs computational intractability in dynamics (2012) (14)
- Constructing Locally Connected Non-Computable Julia Sets (2009) (14)
- Optimal provision-after-wait in healthcare (2013) (14)
- Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs (2020) (13)
- Constructing non-computable Julia sets (2006) (13)
- The Coin Problem with Applications to Data Streams (2020) (12)
- An Invariance Principle for the Multi-slice, with Applications (2021) (12)
- A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness (2017) (12)
- An Interactive Information Odometer with Applications (2014) (12)
- Communication Requirements and Informative Signaling in Matching Markets (2017) (11)
- Approximate Nash Equilibria under Stability Conditions (2010) (11)
- Information Complexity Is Computable (2015) (10)
- The computational hardness of pricing compound options (2014) (10)
- On ad hoc routing with guaranteed delivery (2008) (10)
- I Like Her more than You: Self-determined Communities (2012) (10)
- Nash Equilibria in Perturbation-Stable Games (2017) (10)
- Interactive information and coding theory (2014) (10)
- On Rich $2$-to-$1$ Games (2019) (9)
- Derandomization of Euclidean Random Walks (2007) (9)
- Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions (2015) (9)
- Branching Programs for Tree Evaluation (2009) (9)
- Mathematical Foundations of Computer Science 2009 (2009) (8)
- Parity Problems in Planar Graphs (2007) (8)
- Space-bounded Church-Turing thesis and computational tractability of closed systems (2015) (8)
- Direct Sums in Randomized Communication Complexity (2009) (7)
- Constant-rate coding for multiparty interactive communication is impossible (2016) (7)
- Phylogenetic Reconstruction with Insertions and Deletions (2009) (7)
- Network coding in undirected graphs is either very helpful or not helpful at all (2016) (7)
- Sorted Top-k in Rounds (2019) (6)
- Space-Efficient Counting in Graphs on Surfaces (2009) (6)
- Efficient Communication Using Partial Information (2010) (6)
- Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark (2022) (6)
- Randomized Primitives For Linear Algebra and Applications (2013) (6)
- Interactive compression to external information (2018) (6)
- Fractional Pebbling and Thrifty Branching Programs (2009) (6)
- Tight Space Complexity of the Coin Problem (2022) (6)
- Simulating Noisy Channel Interaction (2014) (6)
- The complexity of simulating Brownian Motion (2009) (5)
- Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility (2019) (5)
- Tiered Random Matching Markets: Rank is Proportional to Popularity (2020) (4)
- The Communication Complexity of Number-In-Hand Set Disjointness with No Promise (2015) (4)
- Optimal tiling of the euclidean space using permutation-symmetric bodies (2021) (4)
- BeauCoup (2020) (4)
- Understanding Influence Functions and Datamodels via Harmonic Analysis (2022) (4)
- Computing with real numbers, from Archimedes to Turing and beyond (2013) (4)
- A Candidate for a Strong Separation of Information and Communication (2018) (4)
- Data-Driven Incentive Alignment in Capitation Schemes (2015) (3)
- The Price of Uncertain Priors in Source Coding (2018) (2)
- Information complexity and applications (2019) (2)
- Unbiased Delay Measurement in the Data Plane (2022) (2)
- Nash Equilibria in Perturbation Resilient Games (2010) (2)
- Prior-free Dynamic Mechanism Design With Limited Liability (2021) (2)
- Near Optimal Distributed Learning of Halfspaces with Two Parties (2021) (2)
- Tight space-noise tradeoffs in computing the ergodic measure (2015) (2)
- Improved Monotonicity Testers via Hypercube Embeddings (2022) (2)
- Guest Editorial for Information Complexity and Applications (2016) (1)
- Optimal short-circuit resilient formulas (2018) (1)
- On computability of Julia sets: answers to questions of Milnor and Shub (2006) (1)
- Information Value of the Game (2017) (1)
- Information Value of Two-Prover Games (2017) (1)
- Information Lower Bounds via Self-Reducibility (2015) (1)
- Statistically Near-Optimal Hypothesis Selection (2021) (1)
- Reliable communication over highly connected noisy networks (2017) (1)
- Truthful Mechanisms for Competing Submodular Processes (2012) (1)
- Optimization-friendly generic mechanisms without money (2021) (1)
- Semi-Direct Sum Theorem and Nearest Neighbor under l_infty (2018) (1)
- Strategyproof Mechanisms for Competitive Influence in Networks (2016) (1)
- Optimal tiling of the Euclidean space using symmetric bodies (2020) (1)
- Optimal Short-Circuit Resilient Formulas (2022) (0)
- Contracting Experts With Unknown Cost Structures (2014) (0)
- Phylogenetic Reconstruction with Insertions and Deletions [ Full Version ] (2014) (0)
- Welfare Distribution in Two-sided Random Matching Markets (2023) (0)
- Matching Markets with Couples Revisited (2010) (0)
- Empirical Characteristics of Affordable Care Act Risk Transfer Payments (2022) (0)
- Title: Graph Gauge Theory and Vector Diffusion Maps Title: a Random Walk on Image Patches Title: Dimension Reduction, Coarse-graining and Data Assimilation in High-dimensional Dynamical Systems Title: Geometry and Topology in Dimension Reduction Title: Optimal Phase Transitions in Compressed Sensing (0)
- Computability and Complexity of Julia Sets (Invited Talk) (2009) (0)
- Information complexity and applications (2019) (0)
- Chebyshev systems and estimation theory for discrete distributions (2002) (0)
- 10 : 2 Optimal Short-Circuit Resilient Formulas 1 (2019) (0)
- On the Computational Power of Radio Channels (2019) (0)
- Parallel Repetition for the GHZ Game: Exponential Decay (2022) (0)
- Round-vs-Resilience Tradeoffs for Binary Feedback Channels (2022) (0)
- New separations results for external information (2021) (0)
- Optimal Waiting Times and Assignments in Healthcare Provision ∗ (2013) (0)
- The rate of convergence of the Walk on Spheres Algorithm (2012) (0)
- Information complexity and exact communication bounds (2013) (0)
- Computability in Geometry and Analysis (2015) (0)
- Noise versus Computational Intractability in Dynamics (2013) (0)
- Guest Editorial for Information Complexity and Applications (2016) (0)
- A Discrepancy Lower Bound for Information Complexity (2015) (0)
- Optimal Resilience for Short-Circuit Noise in Formulas (2016) (0)
- Theology in the Shadow of the Holocaust: Revisiting Bonhoeffer and the Jews (2022) (0)
- The price of uncertainty in communication (2015) (0)
- SUNY College at Old Westbury Promotional Video (1990) (0)
- Communication and information complexity (2022) (0)
- Abacus Medal : Mark Braverman (2022) (0)
- Computability of Julia Sets - ReadingSample (2015) (0)
- 2 2 Ju n 20 05 Parabolic Julia Sets are Polynomial Time Computable (2008) (0)
- Supplementary Material for Monotonicity and Implementability (2010) (0)
- Search using queries on indistinguishable items (2013) (0)
- A Monte Carlo Algorithm for a Lottery Problem (2001) (0)
- Computability and complexity of Julia sets (2008) (0)
- Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009) (2013) (0)
- Rounding via Low Dimensional Embeddings (2022) (0)
- Explorer Fractional Pebbling and Thrifty Branching Programs (2015) (0)
- Leibniz International Proceedings in Informatics Fractional Pebbling and Thrifty Branching Programs (2009) (0)
- 2022 Abacus Medal: Mark Braverman (2022) (0)
- The Tree Evaluation Problem : Towards Separating P from NL Lecture # 6 : 26 February 2014 (2014) (0)
This paper list is powered by the following services:
Other Resources About Mark Braverman
What Schools Are Affiliated With Mark Braverman ?
Mark Braverman is affiliated with the following schools:
