Circuit Complexity of Bipartite Bounded Planar Cutwidth Graph Matching
9th Sept, 2017
Recently, Bipartite Bounded Planar Cutwidth Graph Matching was
shown to be in ACC^0 by Hansen et al. Best known lower bound was AC^0. We
improve on their work to show that the problem is not in AC^0[p^α] where p
is a prime. Our results show that the previous upper bound is quite tight.
We also show a reduction of PARITY to Bipartite Bounded Planar Cutwidth
Graph Matching. A further improvement in lower bounds by methods used by
Hansen et al is not possible as we don’t have a algebraic characteristics
for AC^0[m] where m is not a power of prime. Also a further improvement
will imply separation of AC^0[m] from P. Currently we don’t even have a
separation of AC^0[m] and NP. Our results also imply a better lower bound
for General(Non-Bipartite) Bounded Planar Cutwidth Graph Matching.