3 citations · 5 across the 7 of their papers we have counts for
9 papers
Improved Quantum Random Self-Reduction for Linear Problems
Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
We study quantum random self-reductions for linear problems over finite fields. Let be an arbitrary matrix, and let be an oracle that agr…
Optimal PSPACE-hardness of Approximating -CSP Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Maxmin -CSP Reconfiguration problem, given a satisfiable -CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the othe…
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…
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
In the Minmax Set Cover Reconfiguration problem, given a set system over a universe and its two covers and of…
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Shuichi Hirahara, Naoto Ohsaka
Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration pr…
Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen, Shuichi Hirahara, Hanlin Ren
We show that there is a language in (symmetric exponential time with one bit of advice) with circuit complexity at least . In particular, the abo…