All reports by Author Weiqiang Yuan:

__
TR22-015
| 12th February 2022
__

Mika Göös, Stefan Kiefer, Weiqiang Yuan#### Lower Bounds for Unambiguous Automata via Communication Complexity

__
TR20-155
| 18th October 2020
__

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan#### Log-rank and lifting for AND-functions

Revisions: 1

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.

$\textbf{Complement:}$ There is a language $L$ recognised by an $n$-state UFA such that the complement language $\overline{L}$ requires NFAs with $n^{\tilde{\Omega}(\log n)}$ states. This improves on ... more >>>

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is ... more >>>