Talks - Fall 2017

Kuratowski

Title

Speaker

Date

Time

Venue

Abstract

Circuit Complexity of Bipartite Bounded Planar Cutwidth Graph Matching

Aayush Ojha

9th Sept, 2017

12:15-1:15 PM

KD102

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.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator