20 citations · 81 across the 30 of their papers we have counts for
7 papers · 1 filter
Parameterized Aspects of Distinct Kemeny Rank Aggregation
Koustav De, Harshil Mittal, Palash Dey +1
The Kemeny method is one of the popular tools for rank aggregation. However, computing an optimal Kemeny ranking is NP-hard. Consequently, the computational task of finding a Kemen…
Knapsack: Connectedness, Path, and Shortest-Path
Palash Dey, Sudeshna Kolay, Sipra Singh
We study the knapsack problem with graph theoretic constraints. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs t…
On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules
Chinmay Sonar, Palash Dey, Neeldhara Misra
The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee o…
Resolving the Complexity of Some Fundamental Problems in Computational Social Choice
Palash Dey
This thesis is in the area called computational social choice which is an intersection area of algorithms and social choice theory.
Query Complexity of Tournament Solutions
Arnab Maiti, Palash Dey
A directed graph where there is exactly one edge between every pair of vertices is called a {\em tournament}. Finding the "best" set of vertices of a tournament is a well studied p…
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems
Arnab Bhattacharyya, Palash Dey, David P. Woodruff
We give the first optimal bounds for returning the -heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work o…
Sample Complexity for Winner Prediction in Elections
Arnab Bhattacharyya, Palash Dey
Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the prefere…