# 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.

### Fair Division with Minimal Sharing

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

### Firefighting with Critical Nodes

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.

CSA, IISc 2019

### Efficient algorithms for hard problems on structured electorates

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

### Elicitation for Preferences 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

### Parameterized Graph Modification 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

### Deleting to Structured Trees

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

### Parameterized Complexity of Party Nominations

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.

### An EKR theorem for matchings in the complete graph

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

### An FPT Algorithm for the 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

### Efficient Simplification: The (im)possibilities

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

### An Introduction to Voting

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.

AGT Summer School, 2019

### Arrow's Theorem

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.

AGT Summer School, 2019

### Gibbard Satterthwaite Theorem

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.

AGT Summer School, 2019

### Tournament Fixing and Superkings

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.

AGT Summer School, 2019

### Domain Restrictions and Multiwinner Elections

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.

AGT Summer School, 2019