All reports by Author Sam McGuire:

__
TR20-171
| 12th November 2020
__

Russell Impagliazzo, Sam McGuire#### Comparing computational entropies below majority (or: When is the dense model theorem false?)

__
TR20-155
| 18th October 2020
__

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan#### Log-rank and lifting for AND-functions

Revisions: 1

Russell Impagliazzo, Sam McGuire

Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy ... more >>>

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is ... more >>>