We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth ... more >>>

Raz proposed a program to prove arithmetic circuit lower bounds through the explicit construction of elusive functions. These are polynomial maps from a low dimensional space to a high dimensional ambient space whose image is contained in no subvariety of low complexity. Here, complexity is prescribed in terms of the ... more >>>

In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code.
More formally, given a code $C \subseteq \Sigma^n$ and input lists $S_1, \hdots, S_n \subseteq \Sigma$ of size at most $\ell$, list recoverability requires that there are at most $L$ codewords ... more >>>