Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-004 | 3rd January 2018 08:11

Circuit Complexity of Bounded Planar Cutwidth Graph Matching


Authors: Aayush Ojha, Raghunath Tewari
Publication: 4th January 2018 04:31
Downloads: 695


Recently, perfect matching in bounded planar cutwidth bipartite graphs
$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that
the problem is in AC$^0$.
In this paper, we disprove their conjecture by showing that the problem is
not in AC$^0[p^{\alpha}]$ for every prime $p$. Our results show that the
previous upper bound is almost tight. Our techniques involve giving a reduction
from Parity to $BGGM$. A further improvement in lower bounds is difficult since
we do not have an algebraic characterization for AC$^0[m]$ where $m$ is not a
prime power. Moreover, this will also imply a separation of AC$^0[m]$ from P.
Our results also imply a better lower bound for perfect matching in general
bounded planar cutwidth graphs.

ISSN 1433-8092 | Imprint