Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdos-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implicit" means that the collection is represented ... more >>>

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to ... more >>>

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk.

At about ... more >>>