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

__
TR15-197
| 7th December 2015
__

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Constant-rate coding for multiparty interactive communication is impossible

__
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

__
TR15-074
| 29th April 2015
__

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein#### ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

__
TR15-014
| 18th January 2015
__

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Reliable Communication over Highly Connected Noisy Networks

__
TR14-119
| 15th September 2014
__

Mark Braverman, Jieming Mao#### Simulating Noisy Channel Interaction

__
TR14-095
| 24th July 2014
__

Mark Braverman, Ankit Garg#### Small value parallel repetition for general games

Revisions: 1

__
TR14-047
| 8th April 2014
__

Mark Braverman, Omri Weinstein#### An Interactive Information Odometer with Applications

Revisions: 1

__
TR13-035
| 6th March 2013
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct product via round-preserving compression

Revisions: 1

__
TR12-177
| 19th December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### Information lower bounds via self-reducibility

__
TR12-143
| 5th November 2012
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct Products in Communication Complexity

Revisions: 2

__
TR11-164
| 9th December 2011
__

Mark Braverman, Omri Weinstein#### A discrepancy lower bound for information complexity

Mark Braverman, Ran Gelles, Michael A. Yitayew

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 >>>

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

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 >>>

Mark Braverman, Ankit Garg, 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 $\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 >>>

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

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 >>>

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

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 >>>

Mark Braverman, Jieming Mao

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 >>>

Mark Braverman, Ankit Garg

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 >>>

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

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

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

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 >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

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 >>>

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

Mark Braverman, Omri Weinstein

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 >>>