We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A distribution $X\in\{0,1\}^n$ $\varepsilon$-fools these tests if, for
every $a\in\mathbb{Z}_M^n$, the distribution of
\[
\sum_{i=1}^n a_iX_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding distribution
under independent uniform bits.

Lovett, Reingold, Trevisan, ... more >>>

We prove new exponential monotone circuit lower bounds for detecting perfect matchings. We show that $\exp(\widetilde{\Omega}(n^{1/2}))$ gates are required to detect bipartite perfect matchings in $n$-vertex graphs. Our lower bounds are based on a new spread matching lemma.

more >>>

We show the following hardness results for monotone learning and approximation of monotone circuit size:

1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires time $n^{\Omega(\log n)}$ to PAC-learn monotone formulas with $n$ input bits and size $s(n) = n$ by monotone circuits of size $n^{(\log n)^{1-\epsilon}}$, for every $\epsilon ... more >>>