Showing cs.CCShow all
2 papers · 1 filter
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.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…