Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR20-155 | 18th October 2020
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

Log-rank and lifting for AND-functions

Revisions: 1

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

ISSN 1433-8092 | Imprint