A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof ${\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle {q},({x} \| {\pi})\rangle$ jointly to ${x}$ and ${\pi}$. A DPP can ... more >>>

This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.

1. We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let ... more >>>

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability $\epsilon>0$ independently, with only a $1+\mathcal{O}(\sqrt{\H(\epsilon)})$ blowup to the communication. In particular, this ... more >>>