(#025) Unambiguous DNFs from Hex - Siddhartha Jain
Date and Time: 13-03-2021, 19:30 - 21:00 IST
Abstract
I'll be talking about my work done in collaboration Mika Göös, Shalev Ben-David & Robin Kothari. We exhibit an unambiguous k-DNF formula that requires CNF width \tOmega(k^{1.5}). Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of 1.22. Our result is known to imply several other improved separations in query and communication complexity.
Prerequisites
Some exposure to basic complexity theory/theory of computation
Resources
- "Boolean Function Complexity" by Stasys Jukna.
- Unambiguous DNFs from Hex
- A recent improvement that acheives quadratic separation
Note: The speaker requested the talk to not be recorded.