3 papers
cs.CC2022
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
Xinrui Jia, Ola Svensson, Weiqiang Yuan
Given a graph with edges colored red or blue and an integer , the exact perfect matching problem asks if there exists a perfect matching with exactly red edges. There exists…
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.CC2020
Log-rank and lifting for AND-functions
Alexander Knop, Shachar Lovett, Sam McGuire +1
Let be a boolean function, and let denote the AND-function of , where denotes bit-wise AND. We study the…