14 citations · 59 across the 21 of their papers we have counts for
Showing cs.DMShow all
3 papers · 1 filter
cs.DM2023★ 4 cited
Gap Amplification for Reconfiguration Problems
Naoto Ohsaka
In this paper, we demonstrate gap amplification for reconfiguration problems. In particular, we prove an explicit factor of PSPACE-hardness of approximation for three popular recon…
cs.DM2023★ 2 cited
On Approximate Reconfigurability of Label Cover
Naoto Ohsaka
Given a two-prover game and its two satisfying labelings and , the Label Cover Reconfiguration problem asks whether can be tra…
cs.DM2022★ 3 cited
Gap Preserving Reductions Between Reconfiguration Problems
Naoto Ohsaka
Combinatorial reconfiguration is a growing research field studying problems on the transformability between a pair of solutions of a search problem. We consider the approximability…