17 citations · 20 across the 11 of their papers we have counts for
13 papers
On the Control of Mobile Ad-Hoc Agent Deployments in Partially Observed Space
Edwin Meriaux, Louis-Roy Langevin, Shuo Wen +3
We study the online deployment of mobile ad hoc networks in unknown orthogonal environments, formalized as the Partially Observable Cooperative Guard Art Gallery Problem. We give a…
Random Serial Dictatorship is -Envy-Free
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin +4
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem i…
On the hardness of recognizing graphs of small mim-width and its variants
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
The mim-width of a graph is a powerful structural parameter that, when bounded by a constant, allows several hard problems to be polynomial-time solvable - with a recent meta-theor…
Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
Leaf powers and pairwise compatibility graphs were introduced over twenty years ago as simplified graph models for phylogenetic trees. Despite significant research, several propert…
The Popular Dimension of Matchings
Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye +3
We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching problem, (a subset of…
-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye +1
A graph is a -leaf power if there is a tree whose leaves are the vertices of with the property that a pair of leaves and induce an edge in if and o…
Optimizing the CGMS upper bound on Ramsey numbers
Parth Gupta, Ndiame Ndiaye, Sergey Norin +1
In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the diagonal Ramsey numbers since 1935. We shor…
The Price of Anarchy of the Asymmetric One-Sided Allocation Problem
Sissi Jiang, Ndiame Ndiaye, Adrian Vetta +1
We study fair mechanisms for the (asymmetric) one-sided allocation problem with m items and n multi-unit demand agents with additive, unit-sum valuations. The symmetric case (m=n),…
On depth-3 circuits and covering number: an explicit counter-example
Lianna Hambardzumyan, Hamed Hatami, Ndiamé Ndiaye
We give a simple construction of Boolean matrices with zero entries that are free of all-zero submatrices and have covering number $O(\log^4(n…
The Speed and Threshold of the Biased Hamilton Cycle Game
Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3
We show that there is a constant C such that for any , Maker wins the Maker-Breaker Hamilton cycle game in $n+\frac{Cn}{\sqrt{\ln{n}}}…
The Speed and Threshold of the Biased Perfect Matching Game
Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3
We show that Maker wins the Maker-Breaker perfect matching game in turns when the bias is at least , for any …
Descending the Stable Matching Lattice: How many Strategic Agents are required to turn Pessimality to Optimality?
Ndiame Ndiaye, Sergey Norin, Adrian Vetta
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the gi…
Improving performance of logical qubits by parameter tuning and topology compensation
Jack Raymond, Ndiamé Ndiaye, Gautam Rayaprolu +1
Optimization or sampling of arbitrary pairwise Ising models, in a quantum annealing protocol of constrained interaction topology, can be enabled by a minor-embedding procedure. The…