Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR22-176 | 1st December 2022
Yaroslav Alekseev, Edward Hirsch

#### The power of the Binary Value Principle

The (extended) Binary Value Principle (eBVP, the equation $\sum x_i 2^{i-1} = -k$ for $k > 0$
and in the presence of $x_i^2=x_i$) has received a lot of attention recently, several lower
bounds have been proved for it [Alekseev et al 20, Alekseev 21, Part and Tzameret 21].
Also ... more >>>

TR22-175 | 16th November 2022
Samuel Epstein

#### Derandomization Under Different Resource Constraints

Revisions: 1

We provide another proof to the EL Theorem. We show the tradeoff between compressibility of codebooks and their communication capacity. A resource bounded version of the EL Theorem is proven. This is used to prove three instances of resource bounded derandomization.

more >>>

TR22-174 | 23rd November 2022
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... more >>>

Next

ISSN 1433-8092 | Imprint