Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext 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 next

ISSN 1433-8092 | Imprint