Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G \setminus \{0\}$ such that $(x, y)$, $(x+d, y)$, $(x, y+d) \in A$. We prove that
$|A| \le |G|^2 ... more >>>

Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of such codes has remained a notorious challenge. While the construction of asymptotically-good explicit tree codes continues to be elusive, a work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, ... more >>>

Let $\mathcal{C}$ be a complexity class and $A$ be a language. The statement ``$A \not\in \mathcal{C}$'' is a separation of $A$ from $\mathcal{C}$. A separation is constructive if there is an efficient algorithm called a refuter that prints counterexamples to the statement ``$M$ decides $A$'' for every $\mathcal{C}$-algorithm $M$. Concretely, ... more >>>