Upcoming Talk

Kuratowski

Title

Speaker

Date

Time

Venue

Abstract

Circuit Complexity of Bipartite Bounded Planar Cutwidth Graph Matching

Aayush Ojha

11th Sept, 2017

5:30-6:30 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.

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.

What we like???

Algorithms, Combinatorics, Cryptology, Quantum Computing, Graph-Theory, Information Theory, Game-Theory, Computational Complexity.


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator