Quantum versus classical separation plays a central role in understanding the advantages of quantum computation. In this paper, we present the first exponential separation between quantum and bounded-error randomized communication complexity in a variant of the Number-on-Forehead (NOF) model. Namely, the three-player Simultaneous Number-on-Forehead model. Specifically, we introduce the Gadgeted ... more >>>

Lower bounds against strong algebraic proof systems and specifically fragments of the Ideal Proof System (IPS), have been obtained in an ongoing line of work. All of these bounds, however, are proved only over large (or characteristic 0) fields,1 yet finite fields are the more natural setting for propositional proof ... more >>>

In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM 2018). Our results extend the works of Forbes, Shpilka, Tzameret, and Wigderson (Theory of Computing 2021) ... more >>>