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…
cs.CC2024
Improved PIR Schemes using Matching Vectors and Derivatives
Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely…
cs.CC2023
An Improved Line-Point Low-Degree Test
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi +1
We prove that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. Specifically we consider the ``loc…