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