Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-082 | 23rd June 2025
Per Austrin, Johan Håstad, Björn Martinsson

On the usefulness of Promises

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 >>>


TR25-081 | 20th June 2025
Guangxu Yang, Jiapeng Zhang

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication

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 >>>


TR25-080 | 20th June 2025
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret

Lower Bounds against the Ideal Proof System in Finite Fields

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 >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint