Next

__
TR17-093
| 22nd May 2017
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Coding Over the Noisy Broadcast Channel

__
TR17-092
| 10th May 2017
__

Shuichi Hirahara#### A Duality Between Depth-Three Formulas and Approximation by Depth-Two

__
TR17-091
| 17th May 2017
__

Andrej Bogdanov#### Small bias requires large formulas

Next

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

A set of $n$ players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player ... more >>>

Shuichi Hirahara

We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation ... more >>>

Andrej Bogdanov

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

Next