We show that algebraic formulas and constant-depth circuits are \emph{closed} under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas ... more >>>

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do ... more >>>

A Boolean predicate $A$ is defined to be promise-useful if $PCSP(A,B)$ is tractable for some non-trivial $B$ and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming $\text{P} \ne \text{NP}$). While we do not obtain a complete characterization, our ... more >>>