Talks

This page is best viewed on a desktop device and the slides in fullscreen.

All slides were made either with Beamer+PGF/TikZ or Keynote. The fonts are typically free fonts picked up from the internet. When using LaTeX, I prefer to compile the math with Euler fonts.

All the slides are on Slideshare and can take some time to load. If you follow through to slideshare, you can download the slides (all of them are PDF files) for offline viewing.

This talk was a five-minute presentation of a cute open problem in the context of fair division with minimal sharing, following up from work of Fedor Sandomirskiy and Erel Segal-Halevi from last year. To view the entire session with ten talks in all — complete with the chat transcript — please see the wonderful COMSOC Video Seminar page. I should also point out that the last slide in my presentation had a typo: the claim about EF1+fPO was about EF+fPO. The result is joint work with Aditi Sethia and a preprint will be available soon!

Rump Session: COMSOC Video Seminar

This talk was a part of the Workshop on Parametric Complexity at NUS, which in turn was a part of a four-week program called “Aspects of Computation” held in celebration of the research work of Professor Rod Downey at NUS. The four-week full program focused on recent developments in parametric complexity theory, computability theory with applications in algebra, algorithmic randomness, model theory, etc. I spoke about exploiting structure in voting profiles to obtain efficient algorithms for problems that are computationally intractable in general.

Workshop at NUS, 2017

This was a tutorial about upper and lower bounds in kernelization back in 2010. While the upper bounds are mostly presented the same way, you might want to look up cross-composition for the lower bounds —while the ideas are similar, the terminology has evolved since. See the Kernelization book for a deep dive into both upper and lower bounds, and even coping strategies for lower bounds including Turing kernels and Lossy kernels.

IMPECS 2010

This talk was addressed to the 2019 batch of summer interns admitted to IIT Gandhinagar under the Summer Research Internship Program. The content was based entirely on a beautiful “explorable explanation” called The Evolution of Trust by the amazing Nicky Case. The interactions with the audience were powered by Mentimeter.

This talk was a five-minute presentation of a cute open problem in the context of fair division with minimal sharing, following up from work of Fedor Sandomirskiy and Erel Segal-Halevi from last year. To view the entire session with ten talks in all — complete with the chat transcript — please see the wonderful COMSOC Video Seminar page. I should also point out that the last slide in my presentation had a typo: the claim about EF1+fPO was about EF+fPO. The result is joint work with Aditi Sethia and a preprint will be available soon!

This talk was based on joint work with Jayesh Choudhari, Anirban Dasgupta and M. S. Ramanujan. The talk was a part of the CSA50 Pratiksha Trust Workshop on Theoretical Computer Science organized by the department of Computer Science and Automation (CSA) at IISc as a part of a series of events held in 2019 to mark the golden jubilee year for the department.

The talk itself was a survey of algorithmic results in the context of the firefighting game. View the videos from the rest of the workshop here.

This talk was a part of the Workshop on Parametric Complexity at NUS, which in turn was a part of a four-week program called “Aspects of Computation” held in celebration of the research work of Professor Rod Downey at NUS. The four-week full program focused on recent developments in parametric complexity theory, computability theory with applications in algebra, algorithmic randomness, model theory, etc. I spoke about exploiting structure in voting profiles to obtain efficient algorithms for problems that are computationally intractable in general.

Workshop at NUS, 2017

Single Peaked on Trees

I gave this talk when I was visiting Duke University during the summer of 2016. It was based on joint work with Palash Dey. The talk focused on the problem of preference elicitation, where the goal is to understand the preferences of agents (which we model by total orders) by querying them about their pairwise preferences.

CS-Econ Seminar Series, Duke, 2016

A Modern Perspective

This talk was a part of the fourth edition of the wonderful India-Taiwan Conference on Discrete Mathematics held at IIT Madras in 2015. The talk was about graph modification problems, seen from the lens of forbidden minors, and was mostly in an algorithmic context. The literature has certainly evolved since, hopefully a blog post about more recent developments will be up soon!

ITCDM 2015

This talk was based on joint work with Pratyush Dayal and was delivered (remotely) at COCOON 2019. Here, we consider a natural variant of the well-known Feedback Vertex Set problem, namely the problem of deleting a small subset of vertices or edges to a full binary tree. This version of the problem is motivated by real-world scenarios that are best modeled by full binary trees. We establish that both versions of the problem are NP-hard, which stands in contrast to the fact that deleting edges to obtain a forest or a tree is equivalent to the problem of finding a minimum cost spanning tree, which can be solved in polynomial time. We also establish that both problems are FPT by the standard parameter.

COCOON 2019

Many thanks to Dominik Peters for presenting it on my behalf at ADT 2019. Consider a fixed voting rule R. In the *Possible President* problem, we are given an election where the candidates are partitioned into parties, and the problem is to determine if, given a party P, it is possible for every party to nominate a candidate such that the nominee from P is a winner of the election that is obtained by restricting the votes to the nominated candidates. In the *Necessary President* problem, we would like to find a nominee who wins no matter who else is nominated. In this talk, we explore the complexity of these problems, which can be thought of as the two natural extremes of the party nomination problem.

ADT 2019

The talk concerns the following higher-order analog of the Erdős-Ko-Rado theorem. For positive integers $r$ and $n$ with $r \leq n$, let $M^r_n$ be the family of all matchings of size r in the complete graph $K_{2n}$. For any edge $e$ in $E(K_{2n}$), the family $M^r_n(e$), which consists of all sets in $M^r_n$ containing $e$, is called the star centered at $e$. We prove that if $r<n$ and $\mathcal{A}$ is an intersecting family of matchings in $M^r_n$, then $|\mathcal{A}|\leq |M^r_n(e$)|, where $e$ is an edge in $E(K_{2n}$). We also prove that equality holds if and only if $\mathcal{A}$ is a star. The main technique we use to prove the theorem is an analog of Katona’s elegant cycle method.

Eurocomb 2013

Maximum Edge Coloring Problem

This talk was based on joint work with Prachi Goyal and Vikram Kamat. Here, we investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q>1. For the case when q=2, we show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

MFCS 2013

This was a tutorial about upper and lower bounds in kernelization back in 2010. While the upper bounds are mostly presented the same way, you might want to look up cross-composition for the lower bounds —while the ideas are similar, the terminology has evolved since. See the Kernelization book for a deep dive into both upper and lower bounds, and even coping strategies for lower bounds including Turing kernels and Lossy kernels.

IMPECS 2010

These talks were a part of the ACM-W India Summer School on Algorithmic Game Theory held in 2019 at IIT Gandhinagar. These tutorials were a part of the session on Voting. You can find the full playlist of videos from the summer school here. The other two themes explored in the school were matchings and fair division.

These talks were a part of the ACM-W India Summer School on Algorithmic Game Theory held in 2019 at IIT Gandhinagar. These tutorials were a part of the session on Voting. You can find the full playlist of videos from the summer school here. The other two themes explored in the school were matchings and fair division.

These talks were a part of the ACM-W India Summer School on Algorithmic Game Theory held in 2019 at IIT Gandhinagar. These tutorials were a part of the session on Voting. You can find the full playlist of videos from the summer school here. The other two themes explored in the school were matchings and fair division.

This talk was addressed to the 2019 batch of summer interns admitted to IIT Gandhinagar under the Summer Research Internship Program. The content was based entirely on a beautiful “explorable explanation” called The Evolution of Trust by the amazing Nicky Case. The interactions with the audience were powered by Mentimeter.

The Department of Computer Science and Automation at the Indian Institute of Science has a rich tradition of hosting summer schools for undergraduate audiences. This talk was a part of the first edition organized in 2013 and was a broad introduction to strategies for coping with NP-hardness. The remaining talks in the summer school can be found here. Most of them have accompanying slides and videos. You might also be interested in the subsequent editions: 2014, 2016, 2017, 2018, and 2019.