Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss ... more >>>

We introduce the entangled quantum polynomial hierarchy $QEPH$ as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entangled with each other. We prove $QEPH$ collapses to its second level. In fact, we show that a polynomial number of alternations collapses to just two. ... more >>>