We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>