Weiqiang Yuan

collaborators

2 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 $k$ , the exact perfect matching problem asks if there exists a perfect matching with exactly $k$ red edges. There exists…

cs.CC2020

Log-rank and lifting for AND-functions

Alexander Knop, Shachar Lovett, Sam McGuire +1

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…