Optimal Unambiguous DNFs and Alon-Saks-Seymour
The research constructs unambiguous Disjunctive Normal Forms (DNFs) with linear width but quadratic zero-certificate complexity, $\Omega(n^2)$. This construction optimally refutes the Alon-Saks-Seymour conjecture and yields improved lower bounds for communication complexity problems like Clique versus Independent Set. The work also establishes a quartic separation between certificate complexity and approximate degree, alongside lower bounds for multiclass sample compression.