All reports by Author Anat Ganor:

__
TR17-061
| 3rd April 2017
__

Anat Ganor, Karthik C. S.#### Communication Complexity of Correlated Equilibrium in Two-Player Games

__
TR15-088
| 31st May 2015
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Communication and External Information

__
TR14-113
| 27th August 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication for Boolean Functions

__
TR14-049
| 11th April 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication

Revisions: 1

__
TR14-023
| 19th February 2014
__

Gil Cohen, Anat Ganor, Ran Raz#### Two Sides of the Coin Problem

Revisions: 1

__
TR13-064
| 22nd April 2013
__

Anat Ganor, Ran Raz#### Space Pseudorandom Generators by Communication Complexity Lower Bounds

Revisions: 1

__
TR12-174
| 12th December 2012
__

Anat Ganor, Ilan Komargodski, Ran Raz#### The Spectrum of Small DeMorgan Formulas

Revisions: 1

Anat Ganor, Karthik C. S.

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>

Gil Cohen, Anat Ganor, Ran Raz

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>

Anat Ganor, Ran Raz

In 1989, Babai, Nisan and Szegedy [BNS92] gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was $2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>>

Anat Ganor, Ilan Komargodski, Ran Raz

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to ... more >>>