Research work

Also see: DBLP | Google Scholar

I'm broadly interested in the design and analysis of algorithms and theoretical computer science. I've so far worked on devising Approximation Algorithms, Randomized Algorithms and Parameterized Algorithms for problems in Graph Theory and Social Choice Theory. I've also worked on finding the Computational Complexity of problems (in the Parameterized Setting too). I'm also interested in Streaming Algorithms, Combinatorial Optimization, Algorithms for Big Data and Algorithmic Game Theory.

A Parameterized Perspective on Attacking and Defending Elections

Co-authored by: Neeldhara Misra, Vraj Patel

Accepted - 31st International Workshop on Combinatorial Algorithms (IWOCA), 2020

Abstract: We consider the problem of protecting and manipulating elections by recounting and changing ballots, respectively. Our setting involves a plurality-based election held across multiple districts, and the problem formulations are based on the model proposed recently by~[Elkind et al, IJCAI 2019]. It turns out that both of the manipulation and protection problems are NP-complete even in fairly simple settings. We study these problems from a parameterized perspective with the goal of establishing a more detailed complexity landscape. The parameters we consider include the number of voters, and the budgets of the attacker and the defender. While we observe fixed-parameter tractability when parameterizing by number of voters, our main contribution is a demonstration of parameterized hardness when working with the budgets of the attacker and the defender.

Conference Version: Link     Full Version: Link    Presentation: Link

Survey on De Bruijn Sequences

Advisor: Neeldhara Misra

Course Project - An Introductory Survey on the Properties, Constructions and Applications of De Bruijn Sequences

Survey: Link     Presentation: Link

Survey on Matching in the Graph-Stream Model

Co-authored by: Mrinal Anand, Vraj Patel
Advisor: Anirban Dasgupta

Under Progress - A Survey on Algorithms for the Maximum Matching Problem in the Semi-Streaming Model

Improved FPT Algorithms for Deletion to Forest-like Structures

Co-authored by: Aditya Lonkar, Fahad Panolan, Vraj Patel, Saket Saurabh

Under Review - 31st International Symposium On Algorithms And Computation (ISAAC), 2020