39 citations · 308 across the 129 of their papers we have counts for
5 papers · 1 filter
Even Edge-Matching and Jigsaw Puzzles are Really Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3
We prove the computational intractability of rotating and placing square tiles into a array such that adjacent tiles are compatible--either equal edge colors, as i…
An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut
Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
We construct an improved integrality gap instance for the Calinescu-Karloff-Rabani LP relaxation of the Multiway Cut problem. In particular, for terminals, our inst…
Almost-Polynomial Ratio ETH-Hardness of Approximating Densest -Subgraph
Pasin Manurangsi
In the Densest -Subgraph problem, given an undirected graph and an integer , the goal is to find a subgraph of on vertices that contains maximum number of edges.…
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Pasin Manurangsi, Prasad Raghavendra
A -birthday repetition of a two-prover game is a game in which the two provers are sent random sets of questions from $\mathc…
Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
Warut Suksompong
We consider an assignment problem that has aspects of fair division as well as social choice. In particular, we investigate the problem of assigning a small subset from a set of in…