All reports by Author Mark Braverman:

__
TR15-023
| 10th February 2015
__

Mark Braverman, Jon Schneider#### Information complexity is computable

__
TR15-002
| 2nd January 2015
__

Mark Braverman, Rotem Oshman#### The Communication Complexity of Number-In-Hand Set Disjointness with No Promise

__
TR14-092
| 22nd July 2014
__

Mark Braverman, Young Kun Ko, Omri Weinstein#### Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis

__
TR14-013
| 30th January 2014
__

Mark Braverman, Kanika Pasricha#### The computational hardness of pricing compound options

__
TR14-007
| 17th January 2014
__

Mark Braverman, Klim Efremenko#### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

__
TR13-130
| 17th September 2013
__

Mark Braverman, Ankit Garg#### Public vs private coin in bounded-round information

Revisions: 1

__
TR12-171
| 3rd December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### From Information to Exact Communication

__
TR12-131
| 18th October 2012
__

Mark Braverman, Ankur Moitra#### An Information Complexity Approach to Extended Formulations

Revisions: 1

__
TR11-123
| 15th September 2011
__

Mark Braverman#### Interactive information complexity

__
TR11-064
| 23rd April 2011
__

Mark Braverman#### Towards deterministic tree code constructions

__
TR10-166
| 5th November 2010
__

Mark Braverman, Anup Rao#### Towards Coding for Maximum Errors in Interactive Communication

__
TR10-083
| 13th May 2010
__

Mark Braverman, Anup Rao#### Efficient Communication Using Partial Information

Revisions: 1

__
TR10-035
| 7th March 2010
__

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff#### Pseudorandom Generators for Regular Branching Programs

__
TR09-044
| 6th May 2009
__

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao#### Direct Sums in Randomized Communication Complexity

__
TR09-011
| 31st January 2009
__

Mark Braverman#### Poly-logarithmic independence fools AC0 circuits

__
TR07-035
| 3rd April 2007
__

Mark Braverman, Raghav Kulkarni, Sambuddha Roy#### Parity Problems in Planar Graphs

Mark Braverman, Jon Schneider

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $\alpha>0$, thus resolving an ... more >>>

Mark Braverman, Rotem Oshman

Set disjointness is one of the most fundamental problems in communication complexity. In the multi-party number-in-hand version of set disjointness, $k$ players receive private inputs $X_1,\ldots,X_k\subseteq \{1,\ldots,n\}$, and their goal is to determine whether or not $\bigcap_{i = 1}^k X_i = \emptyset$. In this paper we prove a tight lower ... more >>>

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 \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

Mark Braverman, Kanika Pasricha

It is generally assumed that you can make a financial asset out of any underlying event or combination thereof, and then sell a security. We show that while this is theoretically true from the financial engineering perspective, compound securities might be intractable to price. Even given no information asymmetries, or ... more >>>

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-\varepsilon$, ...
more >>>

Mark Braverman, Ankit Garg

We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing $I$ bits of information, the transmission can be ... more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We develop a new local characterization of the zero-error information complexity function for two party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: $IC(AND,0) = C_{\wedge}\approx 1.4923$ bits, and $IC^{ext}(AND,0) = \log_2 3 \approx 1.5839$ bits. This leads to ... more >>>

Mark Braverman, Ankur Moitra

We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. 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. ... more >>>

Mark Braverman

The primary goal of this paper is to define and study the interactive information complexity of functions. Let $f(x,y)$ be a function, and suppose Alice is given $x$ and Bob is given $y$. Informally, the interactive information complexity $IC(f)$ of $f$ is the least amount of information Alice and Bob ... more >>>

Mark Braverman

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>

Mark Braverman, Anup Rao

We show that it is possible to encode any communication protocol

between two parties so that the protocol succeeds even if a $(1/4 -

\epsilon)$ fraction of all symbols transmitted by the parties are

corrupted adversarially, at a cost of increasing the communication in

the protocol by a constant factor ...
more >>>

Mark Braverman, Anup Rao

We show how to efficiently simulate the sending of a message M 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.

We ... more >>>

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.

A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.

For every width $d$ and length $n$,

our pseudorandom generator uses a seed of length $O((\log d + \log\log n ...
more >>>

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>

Mark Braverman

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... more >>>

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. ... more >>>