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!
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.
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.
Evolution of Trust
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.
SRIP 2019
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.
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.
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!
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.
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.
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.
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.
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
Evolution of Trust
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.
SRIP 2019
Cheat Sheets for Hard Problems
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.
CSA, IISc 2013
