47 citations · 138 across the 17 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.FL2021
Lower Bounds for Unambiguous Automata via Communication Complexity
Mika Göös, Stefan Kiefer, Weiqiang Yuan
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. The…
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 , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…