From the 1 of 5 linked papers with an AI index.
5 papers
Optimal PSPACE-hardness of Approximating -CSP Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
The paper proves that approximating the Maxmin q‑CSP Reconfiguration problem within a factor of 1/2^{q‑1}+ε is PSPACE‑hard for any q≥2, and shows that achieving a (1/2^{q‑1}‑ε)‑app…
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga +3
In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate…
Asymptotically Optimal Inapproximability of E-SAT Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Maxmin E-SAT Reconfiguration problem, we are given a satisfiable -CNF formula where each clause contains exactly literals, along with a pair of its satisfying…
Communication Complexity is NP-hard
Shuichi Hirahara, Rahul Ilango, Bruno Loff
In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing (the 2-way communication complexity of a given function ) NP-complete?} The pr…
Asymptotically Optimal Inapproximability of Maxmin -Cut Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
-Coloring Reconfiguration is one of the most well-studied reconfiguration problems, which asks to transform a given proper -coloring of a graph to another by repeatedly recol…