K. Balodis

activity

20112026

most citedQuantum Lower and Upper Bounds for 2D-Grid and Dyck Language

10 citations · 19 across the 11 of their papers we have counts for

collaborators

Showing 2021 · cs.CCShow all

2 papers · 2 filters

cs.CC2021

Several Separations Based on a Partial Boolean Function

Kaspars Balodis

We show a partial Boolean function $f$ together with an input $x \in f^{- 1} (*)$ such that both $C_{0 ˉ} (f, x)$ and $C_{1 ˉ} (f, x)$ are at leas…

cs.CC2021

Unambiguous DNFs and Alon-Saks-Seymour

Kaspars Balodis, Shalev Ben-David, Mika Göös +2

We exhibit an unambiguous k-DNF formula that requires CNF width $Ω ~ (k^{2})$ , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…