Next

__
TR22-176
| 1st December 2022
__

Yaroslav Alekseev, Edward Hirsch#### The power of the Binary Value Principle

__
TR22-175
| 16th November 2022
__

Samuel Epstein#### Derandomization Under Different Resource Constraints

Revisions: 1

__
TR22-174
| 23rd November 2022
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

Next

Yaroslav Alekseev, Edward Hirsch

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 >>>

Samuel Epstein

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.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

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