2025-11-13 | | Total: 3
One of the oldest problems in coding theory is to match the Gilbert-Varshamov bound with explicit binary codes. Over larger-yet still constant-sized-fields, algebraic-geometry codes are known to beat the GV bound. In this work, we leverage this phenomenon by taking traces of AG codes. Our hope is that the margin by which AG codes exceed the GV bound will withstand the parameter loss incurred by taking the trace from a constant field extension to the binary field. In contrast to concatenation, the usual alphabet-reduction method, our analysis of trace-of-AG (TAG) codes uses the AG codes' algebraic structure throughout - including in the alphabet-reduction step. Our main technical contribution is a Hasse-Weil-type theorem that is well-suited for the analysis of TAG codes. The classical theorem (and its Grothendieck trace-formula extension) are inadequate in this setting. Although we do not obtain improved constructions, we show that a constant-factor strengthening of our bound would suffice. We also analyze the limitations of TAG codes under our bound and prove that, in the high-distance regime, they are inferior to code concatenation. Our Hasse-Weil-type theorem holds in far greater generality than is needed for analyzing TAG codes. In particular, we derive new estimates for exponential sums.
Classical results of Bennett and Gill (1981) show that with probability 1, $P^A \neq NP^A$ relative to a random oracle $A$, and with probability 1, $P^π\neq NP^π\cap coNP^π$ relative to a random permutation $π$. Whether $P^A = NP^A \cap coNP^A$ holds relative to a random oracle $A$ remains open. While the random oracle separation has been extended to specific individually random oracles--such as Martin-Löf random or resource-bounded random oracles--no analogous result is known for individually random permutations. We introduce a new resource-bounded measure framework for analyzing individually random permutations. We define permutation martingales and permutation betting games that characterize measure-zero sets in the space of permutations, enabling formal definitions of resource-bounded random permutations. Our main result shows that $P^π\neq NP^π\cap coNP^π$ for every polynomial-time betting-game random permutation $π$. This is the first separation result relative to individually random permutations, rather than an almost-everywhere separation. We also strengthen a quantum separation of Bennett, Bernstein, Brassard, and Vazirani (1997) by showing that $NP^π\cap coNP^π\not\subseteq BQP^π$ for every polynomial-space random permutation $π$. We investigate the relationship between random permutations and random oracles. We prove that random oracles are polynomial-time reducible from random permutations. The converse--whether every random permutation is reducible from a random oracle--remains open. We show that if $NP \cap coNP$ is not a measurable subset of $EXP$, then $P^A \neq NP^A \cap coNP^A$ holds with probability 1 relative to a random oracle $A$. Conversely, establishing this random oracle separation with time-bounded measure would imply $BPP$ is a measure 0 subset of $EXP$.
An automata network is a graph of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network's graph. It is freezing if there is an order on the states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. Previous works have established that, under the hypothesis that the network graph is of bounded treewidth, many problems that can be captured by trace specifications at individual nodes admit efficient algorithms. In this paper we study the even more restricted case of a network of bounded pathwidth and show two hardness results that somehow illustrate the complexity of freezing dynamics under such a strong graph constraint. First, we show that the trace specification checking problem is NL-complete. Second, we show that deciding first order properties of the orbits augmented with a reachability predicate is NP-hard.