3 papers
cs.CC2026
Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
JarosÅaw BÅasiok, Paul Lou, Alon Rosen +1
In the noisy -XOR problem, one is given and must distinguish between uniform and , where is the adjacency matrix of a -left-regula…
quant-ph2025
Quantum Advantage via Solving Multivariate Polynomials
Pierre Briaud, Itai Dinur, Riddhi Ghosal +3
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case search problem of finding a solution t…
quant-ph2024
Quantum Advantage via Solving Multivariate Quadratics
Pierre Briaud, Riddhi Ghosal, Aayush Jain +2
In this work, we propose a new way to (non-interactively, verifiably) demonstrate Quantum Advantage by solving the average-case search problem of finding a solution t…