If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is ... more >>>

In this paper, we obtain new size lower bounds for proofs in the
Polynomial Calculus (PC) proof system, in two different settings.

1. When the Boolean variables are encoded using $\pm 1$ (as opposed
to $0,1$): We establish a lifting theorem using an asymmetric gadget
$G$, showing ... more >>>

In interactive coding, Alice and Bob wish to compute some function $f$ of their individual private inputs $x$ and $y$. They do this by engaging in an interactive protocol to jointly compute $f(x,y)$. The goal is to do this in an error-resilient way, such that even given some fraction of ... more >>>