Upcoming Talk

Linear subspaces with shading

Title

Speaker

Date

Time

Venue

Abstract

Solving connectivity problems via basic Linear Algebra

Anish Mukherjee

15th Mar,2018

4-5pm

KD103

We consider some classical graph connectivity problems like reachability, shortest path and disjoint paths in different settings. For the first two problems, we show efficient parallel algorithms in the dynamic framework, confirming a conjecture of Patnaik and Immerman ’94 for directed reachability. Very recently we have been able to extend this for more general updates. For the shortest disjoint paths problem, we show efficient (and parallel) algorithms in planar graphs where all the terminals lie on a single face. This answers an open question of Colin de Verdiere and Schrijver ’08. Interestingly the basic idea behind all these algorithms is to compute some linear algebraic properties of the matrix associated with the given graph, which I shall try to convey in this talk.

This is based on joint works with Samir Datta, Raghav Kulkarni, Siddharth Iyer, Thomas Schwentick, and Thomas Zeume.

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