5 papers
Quantum Advantage in Tolerant Junta Testing
Avishay Tal, Weiqiang Yuan
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regi…
Pseudodeterministic Communication Complexity
Mika Göös, Nathaniel Harms, Artur Riazanov +3
We exhibit an -bit partial function with randomized communication complexity but such that any completion of this function into a total one requires randomized commu…
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of circui…
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov +1
We show that for a randomly sampled unsatisfiable -CNF over variables the randomized two-party communication cost of finding a clause falsified by the given variable…
Direct Sums for Parity Decision Trees
Tyler Besselman, Mika Göös, Siyao Guo +2
Direct sum theorems state that the cost of solving instances of a problem is at least times the cost of solving a single instance. We prove the first such results in th…