Arrow Research search

Author name cluster

Mark Braverman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

45 papers
1 author row

Possible papers

45

FOCS Conference 2025 Conference Paper

Undirected Multicast Network Coding Gaps via Locally Decodable Codes

  • Mark Braverman
  • Zhongtian He

The network coding problem asks whether data throughput in a network can be increased using coding (compared to treating bits as commodities in a flow). While it is well-known that a network coding advantage exists in directed graphs, the situation in undirected graphs is much less understood – in particular, despite significant effort, it is not even known whether network coding is helpful at all for unicast sessions. In this paper we study the multi-source multicast network coding problem in undirected graphs. There are k sources broadcasting each to a subset of nodes in a graph of size n. The corresponding combinatorial problem is a version of the Steiner tree packing problem, and the network coding question asks whether the multicast coding rate exceeds the tree-packing rate. We give the first super–constant bound to this problem, demonstrating an example with a coding advantage of $\Omega(\log k)$. In terms of graph size, we obtain a lower bound of $2^{\tilde{\Omega}(\sqrt{\log \log n})}$. We also obtain an upper bound of $O(\log n)$ on the gap. Our main technical contribution is a new reduction that converts locally-decodable codes in the low-error regime into multicast coding instances. This gives rise to a new family of explicitly constructed graphs, which may have other applications.

Details

STOC Conference 2024 Conference Paper

A New Information Complexity Measure for Multi-pass Streaming with Applications

  • Mark Braverman
  • Sumegha Garg
  • Qian Li 0012
  • Shuo Wang
  • David P. Woodruff
  • Jiapeng Zhang

We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one sees a stream of n i.i.d. uniformly random bits and one would like to compute the majority with constant advantage. We show that any constant-pass algorithm must use Ω(log n ) bits of memory, significantly extending an earlier Ω(log n ) bit lower bound for single-pass algorithms of Braverman-Garg-Woodruff (FOCS, 2020). This also gives the first Ω(log n ) bit lower bound for the problem of approximating a counter up to a constant factor in worst-case turnstile streams for more than one pass. In the needle problem, one either sees a stream of n i.i.d. uniform samples from a domain [ t ], or there is a randomly chosen needle α ∈[ t ] for which each item independently is chosen to equal α with probability p , and is otherwise uniformly random in [ t ]. The problem of distinguishing these two cases is central to understanding the space complexity of the frequency moment estimation problem in random order streams. We show tight multi-pass space bounds for this problem for every p < 1/√ n log 3 n , resolving an open question of Lovett and Zhang (FOCS, 2023); even for 1-pass our bounds are new. To show optimality, we improve both lower and upper bounds from existing results. Our information complexity framework significantly extends the toolkit for proving multi-pass streaming lower bounds, and we give a wide number of additional streaming applications of our lower bound techniques, including multi-pass lower bounds for ℓ p -norm estimation, ℓ p -point query and heavy hitters, and compressed sensing problems.

Details

FOCS Conference 2024 Conference Paper

Tight Analyses of Ordered and Unordered Linear Probing

  • Mark Braverman
  • William Kuszmaul

Linear-probing hash tables have been classically believed to support insertions in time $\Theta(x^{2})$, where $1-1/x$ is the load factor of the hash table. Recent work by Bender, Kuszmaul, and Kuszmaul (FOCS'21), however, has added a new twist to this story: in some versions of linear probing, if the maximum load factor is at most $1-1/x$, then the amortized expected time per insertion will never exceed $x\ \text{polylog}\ x$ (even in workloads that operate continuously at a load factor of $1-1/x$ ). Determining the exact asymptotic value for the amortized insertion time remains open. In this paper, we settle the amortized complexity with matching upper and lower bounds of $\Theta(x\log^{1. 5}x)$. Along the way, we also obtain tight bounds for the so-called path surplus problem, a problem in combinatorial geometry that has been shown to be closely related to linear probing. We also show how to extend Bender et al. 's bounds to say something not just about ordered linear probing (the version they study) but also about classical linear probing, in the form that is most widely implemented in practice.

Details

FOCS Conference 2023 Conference Paper

Parallel Repetition for the GHZ Game: Exponential Decay

  • Mark Braverman
  • Subhash Khot
  • Dor Minzer

We show that the value of the n-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

Details

ICLR Conference 2023 Conference Paper

Understanding Influence Functions and Datamodels via Harmonic Analysis

  • Nikunj Saunshi
  • Arushi Gupta
  • Mark Braverman
  • Sanjeev Arora

Influence functions estimate effect of individual data points on predictions of the model on test data and were adapted to deep learning in \cite{koh2017understanding}. They have been used for detecting data poisoning, detecting helpful and harmful examples, influence of groups of datapoints, etc. Recently, \cite{ilyas2022datamodels} introduced a linear regression method they termed {\em datamodels} to predict the effect of training points on outputs on test data. The current paper seeks to provide a better theoretical understanding of such interesting empirical phenomena. The primary tool is harmonic analysis and the idea of {\em noise stability}. Contributions include: (a) Exact characterization of the learnt datamodel in terms of Fourier coefficients. (b) An efficient method to estimate the residual error and quality of the optimum linear datamodel without having to train the datamodel. (c) New insights into when influences of groups of datapoints may or may not add up linearly.

Details

FOCS Conference 2021 Conference Paper

An Invariance Principle for the Multi-slice, with Applications

  • Mark Braverman
  • Subhash Khot
  • Noam Lifshitz
  • Dor Minzer

Given an alphabet size $m\in\mathbb{N}$ thought of as a constant, and $\vec{k}=(k_{1}, \ldots, k_{m})$ whose entries sum of up $n$, the $\vec{k}$ -multi-slice is the set of vectors $x\in[m]^{n}$ in which each symbol $i\in[m]$ appears precisely $k_{i}$ times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ( $[m]^{n}, \mu^{n}$ ) in which $\mu(i)=k_{i}/n$. This answers a question raised by [21]. As applications of the invariance principle, we show: 1)An analogue of the “dictatorship test implies computational hardness” paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an $r$ -ary CSP $\mathcal{P}_{r}$ for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most $\frac{2r+1}{2^{r}}+o(1)$ satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size $o(1)$. 2)A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3)In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs $H$ called $\zeta$ -forests, which is a natural extension of the well-studied case of matchings.

Details

FOCS Conference 2021 Conference Paper

Statistically Near-Optimal Hypothesis Selection

  • Olivier Bousquet
  • Mark Braverman
  • Gillat Kol
  • Klim Efremenko
  • Shay Moran

Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class $\mathcal{Q}=\{q_{1}, \ldots, q_{n}\}$ of distributions, and a sampling access to an unknown target distribution $p$, the goal is to output a distribution $q$ such that $\mathsf{TV}(p, q)$ is close to opt, where $\mathsf{opt}=\min\nolimits_{i}\{\mathsf{TV}(p, q_{i})\}$ and TV (. ,.) denotes the total-variation distance. Despite the fact that this problem has been studied since the 19th century, its complexity in terms of basic resources, such as number of samples and approximation guarantees, remains unsettled (this is discussed, e. g. , in the charming book by Devroye and Lugosi '00). This is in stark contrast with other (younger) learning settings, such as PAC learning, for which these complexities are well understood. We derive an optimal 2-approximation learning strategy for the Hypothesis Selection problem, outputting $q$ such that, $\mathsf{TV}(p, q)\leq 2\cdot\text{opt}+\varepsilon$, with a (nearly) optimal sample complexity of $\tilde{O}(\log n/\varepsilon^{2})$. This is the first algorithm that simultaneously achieves the best approximation factor and sample complexity: previously, Bousquet, Kane, and Moran (COLT ‘19) gave a learner achieving the optimal 2-approximation, but with an exponentially worse sample complexity of $\tilde{O}(\sqrt{n}/\varepsilon^{2. 5})$, and Yatracos (Annals of Statistics '85) gave a learner with optimal sample complexity of $O(\log n/\varepsilon^{2})$ but with a sub-optimal approximation factor of 3. We mention that many works in the Density Estimation (a. k. a. , Distribution Learning) literature use Hypothesis Selection as a black box subroutine. Our result therefore implies an improvement on the approximation factors obtained by these works, while keeping their sample complexity intact. For example, our result improves the approximation factor of the algorithm of Ashtiani, Ben-David, Harvey, Liaw, and Mehrabian (JACM '20) for agnostic learning of mixtures of gaussians from 9 to 6, while maintaining its nearly-tight sample complexity.

Details

FOCS Conference 2021 Conference Paper

Tight Space Complexity of the Coin Problem

  • Mark Braverman
  • Sumegha Garg
  • Or Zamir

In the coin problem we are asked to distinguish, with probability at least 2/3, between $n\ i. i. d$. coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once branching program solving the problem. The coin problem becomes more difficult as $\beta$ becomes smaller. Statistically, it can be solved whenever $\beta= \Omega(n^{-1/2})$, using counting. It has been previously shown that for $\beta=O(n^{-1/2})$, counting is essentially optimal (equivalently, width $poly (n)$ is necessary [Braverman-Garg-Woodruff FOCS'20]). On the other hand, the coin problem only requires $O(\log n)$ width for $\beta > n^{-c}$ for any constant $c > \log_{2}(\sqrt{5}-1)\approx 0. 306$ (following low-width simulation of AND-OR tree of [Valiant Journal of Algorithms'84]). In this paper, we close the gap between the bounds, showing a tight threshold between the values of $\beta=n^{-c}$ where $O(\log n)$ width suffices and the regime where $poly (n)$ width is needed, with a transition at $c=1/3$. This gives a complete characterization (up to constant factors) of the memory complexity of solving the coin problem, for all values of bias $\beta$. We introduce new techniques in both bounds. For the upper bound, we give a construction based on recursive majority that does not require a memory stack of size $\log n$ bits. For the lower bound, we introduce new combinatorial techniques for analyzing progression of the success probabilities in read-once branching programs.

Details

ICML Conference 2020 Conference Paper

Calibration, Entropy Rates, and Memory in Language Models

  • Mark Braverman
  • Xinyi Chen
  • Sham M. Kakade
  • Karthik Narasimhan
  • Cyril Zhang
  • Yi Zhang

Building accurate language models that capture meaningful long-term dependencies is a core challenge in natural language processing. Towards this end, we present a calibration-based approach to measure long-term discrepancies between a generative sequence model and the true distribution, and use these discrepancies to improve the model. Empirically, we show that state-of-the-art language models, including LSTMs and Transformers, are miscalibrated: the entropy rates of their generations drift dramatically upward over time. We then provide provable methods to mitigate this phenomenon. Furthermore, we show how this calibration-based approach can also be used to measure the amount of memory that language models use for prediction.

Details

FOCS Conference 2020 Conference Paper

The Coin Problem with Applications to Data Streams

  • Mark Braverman
  • Sumegha Garg
  • David P. Woodruff

Consider the problem of computing the majority of a stream of n i. i. d. uniformly random bits. This problem, known as the coin problem, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant advantage must use Ω(log n) bits of space. We extend our lower bound to proving tight lower bounds for solving multiple, randomly interleaved copies of the coin problem, as well as for solving the OR of multiple copies of a variant of the coin problem. Our proofs involve new measures of information complexity that are well-suited for data streams. We use these lower bounds to obtain a number of new results for data streams. In each case there is an underlying d dimensional vector x with additive updates to its coordinates given in a stream of length m. The input streams arising from our coin lower bound have nice distributional properties, and consequently for many problems for which we only had lower bounds in general turnstile streams, we now obtain the same lower bounds in more natural models, such as the bounded deletion model, in which ||x|| 2 never drops by a constant fraction of what it was earlier, or in the random order model, in which the updates are ordered randomly. In particular, in the bounded deletion model, we obtain nearly tight lower bounds for approximating ||x|| ∞ up to additive error [1/(√k)]||x|| 2, approximating ||x|| 2 up to a multiplicative ( 1+ε) factor (resolving a question of Jayaram and Woodruff in PODS 2018), and solving the Point Query and ℓ 2 -Heavy Hitters Problems. In the random order model, we also obtain new lower bounds for the Point Query and ℓ 2 -Heavy Hitters Problems. We also give new algorithms complementing our lower bounds and illustrating the tightness of the models we consider, including an algorithm for approximating ||x|| ∞ up to additive error [1/(√k)]||x||2 in turnstile streams (resolving a question of Cormode in a 2006 IITK Workshop), and an algorithm for finding ℓ 2 -heavy hitters in randomly ordered insertion streams (which for random order streams, resolves a question of Nelson in a 2018 Warwick Workshop).

Details

STOC Conference 2018 Conference Paper

Hitting sets with near-optimal error for read-once branching programs

  • Mark Braverman
  • Gil Cohen
  • Sumegha Garg

Nisan (Combinatorica’92) constructed a pseudorandom generator for length n , width n read-once branching programs (ROBPs) with error ε and seed length O (log 2 n + log n · log(1/ε)). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O (log n +log(1/ε)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL , respectively. In contrast to a successful line of work in restricted settings, no progress has been made for general, unrestricted, ROBPs. Indeed, Nisan’s construction is the best pseudorandom generator and, prior to this work, also the best hitting set for unrestricted ROBPs. In this work, we make the first improvement for the general case by constructing a hitting set with seed length O (log 2 n +log(1/ε)). That is, we decouple ε and n , and obtain near-optimal dependence on the former. The regime of parameters in which our construction strictly improves upon prior works, namely, log(1/ε) ≫ log n , is well-motivated by the work of Saks and Zhou (J.CSS’99) who use pseudorandom generators with error ε = 2 −(log n ) 2 in their proof for BPL ⊆ L 3/2 . We further suggest a research program towards proving that BPL ⊆ L 4/3 in which our result achieves one step. As our main technical tool, we introduce and construct a new type of primitive we call pseudorandom pseudo-distributions. Informally, this is a generalization of pseudorandom generators in which one may assign negative and unbounded weights to paths as opposed to working with probability distributions. We show that such a primitive yields hitting sets and, for derandomization purposes, can be used to derandomize two-sided error algorithms.

Details

STOC Conference 2018 Conference Paper

Interactive compression to external information

  • Mark Braverman
  • Gillat Kol

We describe a new way of compressing two-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the participants’ private inputs to an observer that watches the communication, can be simulated by a new protocol that communicates at most poly ( I ) · loglog( C ) bits. Our result is tight up to polynomial factors, as it matches the recent work separating communication complexity from external information cost.

Details

SODA Conference 2018 Conference Paper

On Simultaneous Two-player Combinatorial Auctions

  • Mark Braverman
  • Jieming Mao
  • S. Matthew Weinberg

We consider the following communication problem: Alice and Bob each have some valuation functions υ 1 (·) and υ 2 (·) over subsets of m items, and their goal is to partition the items into S, in a way that maximizes the welfare, . We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whether or not there exists a partition guaranteeing certain welfare, for binary XOS valuations. For interactive protocols with poly( m ) communication, a tight 3/4-approximation is known for both [29, 23]. For interactive protocols, the allocation problem is provably harder than the decision problem: any solution to the allocation problem implies a solution to the decision problem with one additional round and log m additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: • There exists a simultaneous, randomized protocol with polynomial communication that selects a partition whose expected welfare is at least 3/4 of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. • For all ε > 0, any simultaneous, randomized protocol that decides whether the welfare of the optimal partition is ≥ 1 or ≤ 3/4 – 1/108 + ε correctly with probability > 1/2 + 1/poly( m ) requires exponential communication. This provides a separation between the attainable approximation guarantees via interactive (3/4) versus simultaneous (≤ 3/4 – 1/108) protocols with polynomial communication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication. We further discuss the implications of our results for the design of truthful combinatorial auctions in general, and extensions to general XOS valuations. In particular, our protocol for the allocation problem implies a new style of truthful mechanisms.

Details

FOCS Conference 2017 Conference Paper

A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness

  • Mark Braverman
  • Rotem Oshman

In the set disjointess problem, we have k players, each with a private input X i ⊆ [n], and the goal is for the players to determine whether or not their sets have a global intersection. The players communicate over a shared blackboard, and we charge them for each bit that they write on the board. We study the trade-off between the number of interaction rounds we allow the players, and the total number of bits they must send to solve set disjointness. We show that if R rounds of interaction are allowed, the communication cost is Ω̃(nk 1/R /R 4 ), which is nearly tight. We also leverage our proof to show that wellfare maximization with unit demand bidders cannot be solved efficiently in a small number of rounds: here, we have k players bidding on n items, and the goal is to find a matching between items and player that bid on them which approximately maximizes the total number of items assigned. It was previously shown by Alon et. al. that Ω(log log k) rounds of interaction are required to find an assignment which achieves a constant approximation to the maximum-wellfare assignment, even if each player is allowed to write n ϵ(R) bits on the board in each round, where ϵ(R) = exp(-R). We improve this lower bound to Ω(log k/log log k), which is known to be tight up to a log log k factor.

Details

STOC Conference 2015 Conference Paper

An Interactive Information Odometer and Applications

  • Mark Braverman
  • Omri Weinstein

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretic privacy. As a first corollary, we prove a strong direct product theorem for communication complexity in terms of information complexity: If I bits of information are required for solving a single copy of f under μ with probability 2/3, then any protocol attempting to solve n independent copies of f under μ n using o(n • I) communication, will succeed with probability 2 -Ω(n) . This is tight, as Braverman and Rao [BR11] previously showed that O(n • I) communication suffice to succeed with probability ~(2/3) n . We then show how the information odometer can be used to achieve the best possible information-theoretic privacy between two untrusted parties: If the players' goal is to compute a function f(x,y), and f admits a protocol with information cost is I and communication cost C, then our odometer can be used to produce a "robust" protocol which: (i) Assuming both players are honest, computes f with high probability, and (ii) Even if one party is malicious, then for any k∈N, the probability that the honest player reveals more than O(k • (I+log C)) bits of information to the other player is at most 2 -Ω(k) . Finally, we outline an approach which uses the odometer as a proxy for breaking state of the art interactive compression results: We show that our odometer allows to reduce interactive compression to the regime where I=O(log C), thereby opening a potential avenue for improving the compression result of [BBCR10] and to new direct sum and product theorems in communication complexity.

Details

SODA Conference 2015 Conference Paper

Approximating the best Nash Equilibrium in n o (log n ) -time breaks the Exponential Time Hypothesis

  • Mark Braverman
  • Young Kun-Ko
  • Omri Weinstein

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an ε-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an ε-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size O (log n ) in the random graph ( n, 1/2). We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi, confirming the recent conjecture by Aaronson, Impagliazzo and Moshkovitz. Specifically, it would imply a 2 Õ ( n 1/2) algorithm for SAT. Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem. Our key tool is a reduction from the PCP machinery to finding Nash equilibrium via free games, the framework introduced in the recent work by Aaronson, Impagliazzo and Moshkovitz. Techniques developed in the process may be useful for replacing planted clique hardness with ETH-hardness in other applications.

Details

FOCS Conference 2015 Conference Paper

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

  • Mark Braverman
  • Ankit Garg 0001
  • Young Kun-Ko
  • Jieming Mao
  • Dave Touchette

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Omega(n/r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r̂ 2 ) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2 ̂O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

Details

FOCS Conference 2014 Conference Paper

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

  • Mark Braverman
  • Klim Efremenko

In this paper we extend the notion of list-decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2 -- ε, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α Alice's communication and up to a fraction β of Bob's communication. We use list-decoding in order to fully characterize the region RU of pairs (α β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-differentiable curve with infinitely many pieces. We show that outside this region, the rate must be exponential. This suggests that in some error regimes, list-decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α β) for which one-sided unique decoding is possible in a way that Alice will output the correct answer.

Details

FOCS Conference 2013 Conference Paper

A Tight Bound for Set Disjointness in the Message-Passing Model

  • Mark Braverman
  • Faith Ellen
  • Rotem Oshman
  • Toniann Pitassi
  • Vinod Vaikuntanathan

In a multiparty message-passing model of communication, there are k players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in secure multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work [25], [29], [30], strong lower bounds of the form Ω(n·k) were obtained for several functions in the message-passing model; however, a lower bound on the classical set disjointness problem remained elusive. In this paper, we prove a tight lower bound of Ω(n · k) for the set disjointness problem in the message passing model. Our bound is obtained by developing information complexity tools for the message-passing model and proving an information complexity lower bound for set disjointness.

Details

STOC Conference 2013 Conference Paper

An information complexity approach to extended formulations

  • Mark Braverman
  • Ankur Moitra

We prove an unconditional lower bound that any linear program that achieves an O(n 1-ε ) approximation for clique has size 2 Ω(n ε ) . There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al. proved that there is no polynomial sized linear program for traveling salesman. Braun et al. proved that there is no polynomial sized O(n 1/2 - ε )-approximate linear program for clique. Here we prove an optimal and unconditional lower bound against linear programs for clique that matches Hastad's celebrated hardness result. Interestingly, the techniques used to prove such lower bounds have closely followed the progression of techniques used in communication complexity. Here we develop an information theoretic framework to approach these questions, and we use it to prove our main result. Also we resolve a related question: How many bits of communication are needed to get ε-advantage over random guessing for disjointness? Kalyanasundaram and Schnitger proved that a protocol that gets constant advantage requires Ω(n) bits of communication. This result in conjunction with amplification implies that any protocol that gets ε-advantage requires Ω(ε 2 n) bits of communication. Here we improve this bound to Ω(ε n), which is optimal for any ε > 0.

Details

FOCS Conference 2013 Conference Paper

Direct Products in Communication Complexity

  • Mark Braverman
  • Anup Rao 0001
  • Omri Weinstein
  • Amir Yehudayoff

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f, C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μ n be the product distribution on n inputs and f n denote the function that computes n copies of f on these inputs. We prove that if T log 3/2 T ≪ (C - 1)√n and suc(μ, f, C) n, f n, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log 2 T ≪ Cn, we must have suc(μ n, f n, T) ≤ exp(-Ω(n)).

Details

FOCS Conference 2011 Conference Paper

Information Equals Amortized Communication

  • Mark Braverman
  • Anup Rao 0001

We show how to efficiently simulate the sending of a message to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver who has some information about the message. This is a generalization and strengthening of the Slepian Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that the message is a deterministic function of an input. A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost(namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. Our work implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible.

Details

FOCS Conference 2011 Conference Paper

The Grothendieck Constant is Strictly Smaller than Krivine's Bound

  • Mark Braverman
  • Konstantin Makarychev
  • Yury Makarychev
  • Assaf Naor

The classical Grothendieck constant, denoted K G, is equal to the integrality gap of the natural semidefinite relaxation of the problem of computing max {Σ i-1 m Σ j=1 n a ij ε i δ j: {ε i } i=1 m, {δ j } j=1 n ⊆{-1, 1} } a generic and well-studied optimization problem with many applications. Krivine proved in 1977 that KG ≤ 2log (1+√2)/π and conjectured that his estimate is sharp. We obtain a sharper Grothendieck inequality, showing that KG o >; 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ 2 in order to round the projected vectors, beat the random hyperplane technique, contrary to Krivine's long-standing conjecture.

Details

STOC Conference 2010 Conference Paper

How to compress interactive communication

  • Boaz Barak
  • Mark Braverman
  • Xi Chen 0001
  • Anup Rao 0001

We describe new ways to simulate 2-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most ~O(√CI) bits of communication. If the protocol reveals I bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with ~O(I) bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst case computation, computing n copies of a function requires √n times the communication required for computing one copy of the function. For average case complexity, given any distribution μ on inputs, computing n copies of the function on n inputs sampled independently according to μ requires √n times the communication for computing one copy. If μ is a product distribution, computing n copies on n independent inputs sampled according to μ requires n times the communication required for computing the function. We also study the complexity of computing the sum (or parity) of n evaluations of f, and obtain results analogous to those above.

Details

FOCS Conference 2010 Conference Paper

Pseudorandom Generators for Regular Branching Programs

  • Mark Braverman
  • Anup Rao 0001
  • Ran Raz
  • Amir Yehudayoff

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ϵ)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ϵ. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ϵ/γ 2.

Details

MFCS Conference 2009 Conference Paper

Branching Programs for Tree Evaluation

  • Mark Braverman
  • Stephen A. Cook
  • Pierre McKenzie
  • Rahul Santhanam
  • Dustin Wehr

Abstract The problem \(FT^{h}_{d}(k)\) consists in computing the value in [ k ] = {1, .. ., k } taken by the root of a balanced d -ary tree of height h whose internal nodes are labelled with d -ary functions on [ k ] and whose leaves are labelled with elements of [ k ]. We propose \({FT^{h}_{d}(k)}\) as a good candidate for witnessing \({\mathbf{L}} \subsetneq{\mathbf{LogDCFL}}\). We observe that the latter would follow from a proof that k -way branching programs solving \({FT^{h}_{d}(k)}\) require \(\Omega(k^{\mbox{\scriptsize unbounded function}(h)})\) size. We introduce a “state sequence” method that can match the size lower bounds on \(FT^{h}_{d}(k)\) obtained by the Nec̆iporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ( k 3 ) and Θ( k 5/2 ) for deterministic and nondeterministic branching programs solving \(FT^{3}_{2}(k)\) respectively. We propose as a challenge to break the quadratic barrier inherent in the Nec̆iporuk method by adapting the state sequence method to handle \(FT^{4}_{d}(k)\).

Details

STOC Conference 2007 Conference Paper

Constructing non-computable Julia sets

  • Mark Braverman
  • Michael Yampolsky

While most polynomial Julia sets are computable, it has been recently shown [12] that there exist non-computable Julia sets. The proof was non-constructive, and indeed there were doubts as to whether specific examples of parameters with non-computable Julia sets could be constructed. It was also unknown whether the non-computability proof can be extended to the filled Julia sets. In this paper we give an answer to both of these questions, which were the main open problems concerning the computability of polynomial Julia sets. We show how to construct a specific polynomial with a non-computable Julia set. In fact, in the case of Julia sets of quadratic polynomials we give a precise characterization of Juliasets with computable parameters. Moreover, assuming a widely believed conjecture in Complex Dynamics, we give a poly-time algorithm forcomputing a number c such that the Julia set J z 2 +c z is non-computable. In contrast with these results, we show that the filled Julia set of a polynomial is always computable.

Details

FOCS Conference 2005 Conference Paper

On the Complexity of Real Functions

  • Mark Braverman

We establish a new connection between the two most common traditions in the theory of real computation, the Blum-Shub-Smale model and the computable analysis approach. We then use the connection to develop a notion of computability and complexity of functions over the reals that can be viewed as an extension of both models. We argue that this notion is very natural when one tries to determine just how difficult a certain function is for a very rich class of functions.

Details

FOCS Conference 2004 Conference Paper

Learnability and Automatizability

  • Michael Alekhnovich
  • Mark Braverman
  • Vitaly Feldman
  • Adam R. Klivans
  • Toniann Pitassi

We consider the complexity of properly learning concept classes, i. e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following upper and lower bounds on well-known concept classes: 1) We show that unless NP = RP, there is no polynomial-time PAC learning algorithm for DNF formulae where the hypothesis is an OR-of-thresholds. Note that as special cases, we show that neither DNF nor OR-of-thresholds are properly learnable unless NP = RP. Previous hardness results have required strong restrictions on the size of the output DNF formula. We also prove that it is NP-hard to learn the intersection of /spl lscr/ /spl ges/ 2 halfspaces by the intersection of k halfspaces for any constant k > 0. Previous work held for the case when k = /spl lscr/; 2) Assuming that NP /spl nsube/ DTIME(2/sup n/spl epsi//) for a certain constant /spl epsiv/ < 1 we show that it is not possible to learn size s decision trees by size s/sup k/ decision trees for any k /spl ges/ 0. Previous hardness results for learning decision trees held for k /spl les/ 2; 3) We present the first nontrivial upper bounds on properly learning DNF formulae and decision trees. In particular we show how to learn size s DNF by DNF in time 2/sup O~/(/spl radic/(n log s)), and how to learn size s decision trees by decision trees in time n/sup O(log s)/. The hardness results for DNF formulae and intersections of halfspaces are obtained via specialized graph products for amplifying the hardness of approximating the chromatic number as well as applying work on the hardness of approximate hypergraph coloring. The hardness results for decision trees, as well as the upper bounds, are obtained by developing a connection between automatizability in proof complexity and learnability, which may have other applications.

Details