Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or ... more >>>

It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mABPs). The best lower bounds in this setting are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the “min-partition rank” method introduced by ... more >>>

We study the power of negation in the Boolean and algebraic settings and show the following results.

* We construct a family of polynomials $P_n$ in $n$ variables, all of whose monomials have positive coefficients, such that $P_n$ can be computed by a depth three circuit of polynomial size ... more >>>