Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BIT PIGEONHOLE PRINCIPLE:
Reports tagged with bit pigeonhole principle:
TR20-184 | 10th December 2020
Dmitry Itsykson, Artur Riazanov

#### Proof complexity of natural formulas via communication arguments

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>

ISSN 1433-8092 | Imprint