Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Mark Braverman:

TR16-166 | 1st November 2016
Mark Braverman, Ran Gelles, Michael A. Yitayew

Optimal Resilience for Short-Circuit Noise in Formulas

Revisions: 1

We show an efficient method for converting a logic circuit of gates with fan-out 1 into an equivalent circuit that works even if some fraction of its gates are short-circuited, i.e., their output is short-circuited to one of their inputs. Our conversion can be applied to any circuit with fan-in ... more >>>

TR15-197 | 7th December 2015
Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Constant-rate coding for multiparty interactive communication is impossible

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our ... more >>>

TR15-081 | 12th May 2015
Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

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 $\tilde{\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 ... more >>>

TR15-074 | 29th April 2015
Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>

TR15-014 | 18th January 2015
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Reliable Communication over Highly Connected Noisy Networks

We consider the task of multiparty computation performed over networks in
the presence of random noise. Given an $n$-party protocol that takes $R$
rounds assuming noiseless communication, the goal is to find a coding
scheme that takes $R'$ rounds and computes the same function with high
probability even when the ... more >>>

TR14-119 | 15th September 2014
Mark Braverman, Jieming Mao

Simulating Noisy Channel Interaction

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

TR14-095 | 24th July 2014
Mark Braverman, Ankit Garg

Small value parallel repetition for general games

Revisions: 1

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>

TR14-047 | 8th April 2014
Mark Braverman, Omri Weinstein

An Interactive Information Odometer with Applications

Revisions: 1

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-theoretically secure computation.

As a first corollary, ... more >>>

TR13-035 | 6th March 2013
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Direct product via round-preserving compression

Revisions: 1

We obtain a strong direct product theorem for two-party bounded round communication complexity.
Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses
at most C bits of communication in computing f(x,y) when (x,y)~\mu.
Jain et al. [JPY12] have recently showed that if
more >>>

TR12-177 | 19th December 2012
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

Information lower bounds via self-reducibility

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform ... more >>>

TR12-143 | 5th November 2012
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Direct Products in Communication Complexity

Revisions: 2

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 f(x,y) with C bits of communication, when the inputs (x,y) are ... more >>>

TR11-164 | 9th December 2011
Mark Braverman, Omri Weinstein

A discrepancy lower bound for information complexity

This paper provides the first general technique for proving information lower bounds on two-party
unbounded-rounds communication problems. We show that the discrepancy lower bound, which
applies to randomized communication complexity, also applies to information complexity. More
precisely, if the discrepancy of a two-party function $f$ with respect ... more >>>

ISSN 1433-8092 | Imprint