Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INTERACTIVE PROTOCOLS:
Reports tagged with interactive protocols:
TR14-173 | 13th December 2014
Igor Carboni Oliveira, Rahul Santhanam

#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

ISSN 1433-8092 | Imprint