We show that the nearest-codeword and minimum-distance problems for linear codes over every fixed finite field are W[1]-hard to approximate within any constant factor under deterministic fixed-parameter many-one reductions. This gives unconditional deterministic parameterized inapproximability for minimum distance, including the binary problem usually called Even Set. The reduction starts from ... more >>>

In a recent breakthrough, Williams (STOC 2025) showed that any decision problem solvable in time $t$ by a multitape Turing machine can be solved in space $\tilde{O}(\sqrt{t})$ and time $2^{\tilde{O}(\sqrt{t})}$. The immediate question is whether this result is an anomaly, or an inherent feature of computation more generally.

In this ... more >>>

Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to ... more >>>