We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program.

more >>>

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to ... more >>>

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>