Propositional proof complexity is an area of complexity theory that addresses the question of whether the class NP is closed under complement, and also provides a theoretical framework for studying practical applications such as SAT solving.
Some of the most well-studied contradictions are random $k$-CNF formulas where each clause of ... more >>>

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>