We show that a (stronger) version of random resolution has the feasible disjunction property. This is the first instance of a proof system not known to have feasible interpolation, which nevertheless has the feasible disjunction property.

more >>>

We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $\gamma$ admits a signed decomposition into at most $2^{O(\gamma^4)}$ elementary pieces. In ... more >>>

We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2} \to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group (not necessarily finite), the low-degree ... more >>>