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

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when ... more >>>