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

We prove that every De Morgan formula with $n$ leaves has a pointwise $1/3$-approximating real polynomial of degree $O(\sqrt n)$ and coefficient $\ell_1$-norm $2^{O(\sqrt n)}$. The standard approximate-degree theorem for formulas gives the same degree bound, but only yields the weaker coefficient estimate $2^{O(\sqrt n\log n)}$.

Our proof constructs, for ... more >>>