Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shalev Ben-David:

TR22-112 | 12th August 2022
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

Randomised Composition and Small-Bias Minimax

We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, ... more >>>

TR21-016 | 16th February 2021
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

Unambiguous DNFs from Hex

Revisions: 1

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(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 ... more >>>

ISSN 1433-8092 | Imprint