Circuit Complexity of Bipartite Bounded Planar Cutwidth Graph Matching
11th 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.
Who are we???
SIGTACS - Special Interest Group on Theoretical Aspects of Computer Science, was born out of an effort to bring together people interested in areas of Theoretical Computer Science.
What we do???
It is a platform for students and faculty members to come together and share their excitement in the area. The group aims at organizing problem solving sessions, seminars and guest lectures.