Samuel H. McGuire

collaborators

2 papers

cs.CC2020

Comparing computational entropies below majority (or: When is the dense model theorem false?)

Russell Impagliazzo, Sam McGuire

Computational pseudorandomness studies the extent to which a random variable $Z$ looks like the uniform distribution according to a class of tests $F$ . Computational ent…

cs.CC2020

Log-rank and lifting for AND-functions

Alexander Knop, Shachar Lovett, Sam McGuire +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…