All News
All News
Joint work with Umang Bhaskar, Aditi Sethia, and Rohit Vaish ⸱ To Appear at SAGT 2023 ⸱ ArXiV
In fair division problems, the notion of price of fairness measures the loss in welfare due to a fairness constraint. Prior work on the price of fairness has focused primarily on envy-freeness up to one good (EF1) as the fairness constraint, and on the utilitarian and egalitarian welfare measures. Our work instead focuses on the price of equitability up to one good (EQ1) (which we term price of equity) and considers the broad class of generalized p-mean welfare measures (which includes utilitarian, egalitarian, and Nash welfare as special cases). We derive fine-grained bounds on the price of equity in terms of the number of agent types (i.e., the maximum number of agents with distinct valuations), which allows us to identify scenarios where the existing bounds in terms of the number of agents are overly pessimistic.
Our work focuses on the setting with binary additive valuations, and obtains upper and lower bounds on the price of equity for p-mean welfare for all p <= 1. For any fixed p, our bounds are tight up to constant factors. A useful insight of our work is to identify the structure of allocations that underlie the upper (respectively, the lower) bounds simultaneously for all p-mean welfare measures, thus providing a unified structural understanding of price of fairness in this setting. This structural understanding, in fact, extends to the more general class of binary submodular (or matroid rank) valuations. We also show that, unlike binary additive valuations, for binary submodular valuations the number of agent types does not provide bounds on the price of equity.
Joint work with Saraswati Nanoti ⸱ To Appear at MFCS 2023 ⸱ Preprint coming soon!
We study a two-player game on a graph between an attacker and a defender. To begin with, the defender places guards on a subset of vertices. In each move, the attacker attacks an edge. The defender must move at least one guard across the attacked edge to defend the attack. The defender wins if and only if the defender can defend an infinite sequence of attacks. The smallest number of guards with which the defender has a winning strategy is called the eternal vertex cover number of a graph G and is denoted by evc(G). It is clear that evc(G) is at least mvc(G), the size of a minimum vertex cover of G. We say that G is Spartan if evc(G) = mvc(G). The characterization of Spartan graphs has been largely open. In the setting of bipartite graphs on 2n vertices where every edge belongs to a perfect matching, an easy strategy is to have n guards that always move along perfect matchings in response to attacks. We show that these are essentially the only Spartan bipartite graphs.
Joint work with Yash More ⸱ To Appear at IWOCA 2023 ⸱ Preprint coming soon!
A cut (X,Y) is a perfect matching cut if and only if each vertex in X has exactly one neighbor in Y and each vertex in Y has exactly one neighbor in X. The computational problem of determining if a graph admits a perfect matching cut is NP-complete, even when restricted to the class of bipartite graphs of maximum degree 3 and arbitrarily large girth. We demonstrate a faster exact exponential time algorithm on general graphs and an even faster algorithm on graphs of maximum degree three that have girth six.
CompEd will be held between December 7-9, 2023, at Hyderabad, India. Check out the call for participation! The deadline for submitting abstracts is Sunday, 7 May.
The International Symposium on Parameterized and Exact Computation (IPEC) is an annual conference covering all aspects of parameterized and exact algorithms and complexity. Its 18th edition will be part of ALGO 2023, which also hosts ESA 2023 and other specialized conferences and workshops. We are excited that ALGO 2023 is planned as an in-person conference and we look forward to seeing you there! ALGO will be held between September 4-8, 2023, at Amsterdam, the Netherlands.
Do submit your best work to IPEC 2023 --- the abstract submission deadline is June 27th (23:59 AoE).
Recieved the NASI Platinum Jubilee Young Scientist Award. Most grateful to all collaborators and mentors who make this recognition possible.
INYAS is the Young Science Academy established by Indian National Science Academy (INSA). Their work in science outreach and popularization has been wide-ranging and very inspiring over the years. It is wonderful and humbling to have been selected as a member this year. Looking forward to pitching in!
We recently concluded the CSEd Workshop with support from ACM India, NPTEL, and the discipline of CSE at IIT Gandhinagar. The workshop featured talks by Sonia Garcha, Viraj Kumar, Venkatesh Choppella, and N S Kumar. The talks covered various themes, including CSPathshala, refute questions, mapcode, and key takeaways to convey in a data structures course.
The materials from the course (including video recordings and slides) can be accessed from here.
Mount Carmel College (in Bangalore), my alma mater, is celebrating its Platinum Jubilee this year. A part of this celebration is HERSTORY: "75 years of scripting success stories of Confident, Competent, & Compassionate Carmelites".
I was honored to be among the 75 Carmelites invited for the HERSTORY event today. It was very nostalgic to be back on campus, and the organizers put together an impeccable event that made all of us feel very special. It was humbling to be in inspiring company. I can't thank MCC enough for providing an empowering and fun environment at a crucial stage of my life!
We recently concluded the GIAN course on Randomized Methods for Parameterized Algorithms by Daniel Lokshtanov, Professor, Dept of Computer Science, University of California Santa Barbara, between Dec 5—9, 2022. The course consisted of over ten hours of lectures covering modern techniques in randomized algorithms, and five interactive tutorial sessions.
The materials from the course (including video recordings and slides) can be accessed from here.
My course on Getting Started with Competitive Programming will run from 23 Jan 2023 to 14 Apr 2023. The deadline to register is 30th January 2023. I hope you have a chance to check it out if it is of interest to you!
(More generally, the NPTEL Jan 2023 semester is open with courses across engineering, humanities and social sciences. You can enrol in these courses at no cost here and get a certification by taking up a proctored exam for a nominal fee of Rs 1,000 per course.)
Joint work with Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami ⸱ To Appear at FSTTCS 2022 ⸱ Preprint available from ArXiV
The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k agents. While the initial positions of Facilitator’s agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with k agents. In this work, we prove that this problem is hard even when the graph is very close to a forest.
Joint work with Harshil Mittal and Sarasati Nanoti ⸱ To Appear at CCCG 2022
A perfect matching M on a set P of n points is a collection of line segments with endpoints from P such that every point belongs to exactly one segment. A matching is non-crossing if the line segments do not cross. We introduce a notion of distance between non-crossing matchings, and investigate the complexity of the problem of finding matchings that are far apart with respect to this notion of distance.
Joint work with N. R. Aravind and Harshil Mittal ⸱ To appear at FUN 2022 ⸱ Preprint available from ArXiV
We introduce a generalization of “Solo Chess”, a single-player variant of the game that can be played on chess.com. We show that this version of the game is NP-complete even if played only by rooks with at most two captures left, or only by queens with exactly two captures left. On the other hand, solvable instances of rooks on 1D boards and pawns on 2D boards can efficiently characterized. Find out more on Twitter or at the blog.
Members of the discipline of Computer Science and Engineering just concluded a virtual open house. You can now find out more about research directions in CSE at IIT Gandhinagar and the research opportunities that we offer. Please share these links with anyone that you think would find them useful!
Joint work with Saraswati Nanoti ⸱ To appear at CSR 2022 ⸱ Preprint available from ArXiV
Eternal Vertex Cover is a dynamic variant of the vertex cover problem. The complexity of the problem on bipartite graphs is open, as is the question of whether the problem admits a polynomial kernel. We settle both these questions by showing that Eternal Vertex Cover is NP-hard and does not admit a polynomial compression even on bipartite graphs of diameter six. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.
Joint work with Harshil Mittal ⸱ Published in Theoretical Computer Science (Dec 2021) ⸱ A shorter version was accepted at COCOON 2020 ⸱ Preprint available from ArXiV
Imbalance is a layout optimization problem, where we would like to order the vertices of a graph so that, roughly speaking, vertices have their neighbors split up as equally as possible on their left and right. We examine the parameterized complexity of the problem with respect to a structural parameter called twin cover.
My course on Getting Started with Competitive Programming will run from 24 Jan 2022 to 15 Apr 2022. The deadline to register is 31st January 2022.
(More generally, the NPTEL Jan 2022 semester is open with courses across engineering, humanities and social sciences. You can enrol in these courses at no cost here and get a certification by taking up a proctored exam for a nominal fee of Rs 1,000 per course.)
Submit your most fun work to FUN 2022! Also spread the word with a retweet :)
Joint work with Debanuj Nayak ⸱ Accepted at CALDAM 2022 ⸱ Preprint available from ArXiV.
These developments explore the complexity of finding envy-free allocations of indivisible items in settings where envy is only experienced between friends, the valuations over items are binary, and the social network over agents is given by an undirected graph.
Here’s a Twitter thread with more detailsl
I'll be co-teaching a couple of new courses this August on the NPTEL platform. The first is about competitive programming (co-taught with Arjun Arul from Codechef) and the second is an introduction to parameterized algorithms (co-taught with Saket Saurabh from IMSc). Both are meant as follow ups to a first undergraduate algorithms course.
