research
∙
09/11/2023
Truthful Interval Covering
We initiate the study of a novel problem in mechanism design without mon...
share
research
∙
08/17/2023
The Complexity of Fair Division of Indivisible Items with Externalities
We study the computational complexity of fairly allocating a set of indi...
research
∙
07/03/2023
Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
We introduce and study a new optimization problem on digraphs, termed Ma...
research
∙
05/11/2023
Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
We investigate the difficulty of finding economically efficient solution...
research
∙
03/21/2023
Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source
We consider the influence maximization problem over a temporal graph, wh...
research
∙
09/30/2022
Tight Inapproximability for Graphical Games
We provide a complete characterization for the computational complexity ...
research
∙
09/30/2022
Pure-Circuit: Strong Inapproximability for PPAD
The current state-of-the-art methods for showing inapproximability in PP...
research
∙
07/14/2022
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
Since the seminal PPAD-completeness result for computing a Nash equilibr...
research
∙
04/25/2022
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
Since the celebrated PPAD-completeness result for Nash equilibria in bim...
research
∙
01/24/2022
Constant Inapproximability for PPA
In the ε-Consensus-Halving problem, we are given n probability measures ...
research
∙
01/18/2022
The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
Schelling's model considers k types of agents each of whom needs to sele...
research
∙
12/16/2021
Minimizing Reachability Times on Temporal Graphs via Shifting Labels
We study how we can accelerate the spreading of information in temporal ...
research
∙
08/04/2021
Combinatorial Algorithms for Multidimensional Necklaces
A necklace is an equivalence class of words of length n over an alphabet...
research
∙
05/06/2021
Heterogeneous Facility Location with Limited Resources
We initiate the study of the heterogeneous facility location problem wit...
research
∙
04/09/2021
Ranking Bracelets in Polynomial Time
The main result of the paper is the first polynomial-time algorithm for ...
research
∙
12/28/2020
Square-Cut Pizza Sharing is PPA-complete
We study the computational complexity of computing solutions for the squ...
research
∙
07/29/2020
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
We consider the ε-Consensus-Halving problem, in which a set of heterogen...
research
∙
05/24/2020
Walrasian Equilibria in Markets with Small Demands
We study the complexity of finding a Walrasian equilibrium in markets wh...
research
∙
05/20/2020
The K-Centre Problem for Necklaces
In graph theory, the objective of the k-centre problem is to find a set ...
research
∙
05/17/2020
Matching in Stochastically Evolving Graphs
This paper studies the maximum cardinality matching problem in stochasti...
research
∙
05/06/2020
Heterogeneous Facility Location Games
We study heterogeneous k-facility location games. In this model there ar...
research
∙
04/13/2020
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
In this paper we consider the following total functional problem: Given ...
research
∙
04/13/2020
Optimizing Reachability Sets in Temporal Graphs by Delaying
A temporal graph is a dynamic graph where every edge is assigned a set o...
research
∙
03/27/2020
Crystal Structure Prediction via Oblivious Local Search
We study Crystal Structure Prediction, one of the major problems in comp...
research
∙
02/27/2020
Tree Polymatrix Games are PPAD-hard
We prove that it is PPAD-hard to compute a Nash equilibrium in a tree po...
research
∙
10/26/2019
On the Hardness of Energy Minimisation for Crystal Structure Prediction
Crystal Structure Prediction (csp) is one of the central and most challe...
research
∙
06/06/2019
Connected Subgraph Defense Games
We study a security game over a network played between a defender and k ...
research
∙
03/07/2019
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
We study the problem of finding an exact solution to the consensus halvi...
research
∙
11/16/2018
Incentivizing the Dynamic Workforce: Learning Contracts in the Gig-Economy
In principal-agent models, a principal offers a contract to an agent to ...
research
∙
10/02/2018