Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SCOTT DUKE KOMINERS:
All reports by Author Scott Duke Kominers:

TR26-147 | 13th August 2026
Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng

Improved Soundness for the Line--versus--Point Test

The line--versus--point test asks the following local-to-global question. Suppose a function $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ is, on average over a random affine line $L$, correlated with some degree-$d$ polynomial on $L$. Must $f$ then be globally correlated with a single multivariate polynomial of degree at most $d$? Beyond being a natural combinatorial question, ... more >>>




ISSN 1433-8092 | Imprint