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^\pi \neq NP^\pi \cap coNP^\pi$ relative to a random permutation $Pi$. Whether $P^A = NP^A \cap coNP^A$ holds relative to a random oracle $A$ remains ... more >>>

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 ... more >>>

Let $\mathcal{G}$ be a $k$-player game with value $<1$, whose query distribution is such that no marginal on $k-1$ players admits a non-trivial Abelian embedding. We show that for every $n\geq N$, the value of the $n$-fold parallel repetition of $\mathcal{G}$ is $$ \text{val}(\mathcal{G}^{\otimes n}) \leq \frac{1}{\underbrace{\log\log\cdots\log}_{C\text{ times}} n}, $$ ... more >>>