Combinatorics and TCS Seminar

Wednesday, 3rd January 2024, 2.30 pm

=======================

Venue: Google Meet (https://meet.google.com/ctv-ynac-gjt)

Host: Sudhir R. Ghorpade

Speaker: Prafullkumar Tale

Affiliation: IISER Bhopal

Title: Parameterized Complexity and Some New Lower Bounds for Problems in NP

Abstract: In this talk, we briefly introduce Parameterized Complexity and some graph theoretical NP complete problems. We then look at the usual conditional lower bounds in this domain, most of which are single (or almost single) exponential.

Our results, for the first time, derive double-exponential lower bounds for natural, important, and well-studied NP-complete graph problems when parameterized by structural parameters. Specifically, we design a technique to obtain such lower bounds and show its versatility by applying it to three different problems: Metric Dimension, Strong Metric Dimension, and Geodetic Set. This techniques use for the lower bounds uses a novel yet simple technique based on the Sperner families of sets.

Algebraic Groups seminar

Friday, 5 January, 4.00-5.15

==================

Venue: Room 105

Host: Dipendra Prasad

Speakers: Dibyendu Biswas, Chayan. Karmakar and Mohammed Saad

Affiliation: IIT Bombay

Abstract: We will discuss a variety of topics in Algebraic groups through reading some of the papers that have become classics in the subject. The first few seminars will be on the paper by Robert Steinberg, Regular elements of semi-simple algebraic groups Publications mathématiques de l’I.H.É.S., tome 25 (1965), p. 49-80