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-237 | 9th October 2026
Quang Dao, Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng

Counterexamples to Beyond-Johnson Proximity Gaps over Binary Fields

Revisions: 1

Many hash-based proof systems check that committed words are close to Reed-Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few ... more >>>


TR26-235 | 8th October 2026
Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng

The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear Codes

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the \emph{proximity-gaps property} up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction (typically at most $\operatorname{poly}(n)/q$) of \emph{exceptional coefficients} ... more >>>


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

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

Revisions: 6

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