Naoto Ohsaka
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Naoto Ohsaka has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
Ken-Ichi Kawarabayashi
National Institute of Informatics
6 shared publications- Shuichi Hirahara
National Institute of Informatics, Tokyo, Japan
4 shared publications - Riku Togashi
CyberAgent, Tokyo, Japan
3 shared publications Naonori Kakimura
Keio University
2 shared publicationsSumio Fujita
Yahoo Japan Corporation
2 shared publicationsTomohiro Sonobe
National Institute of Informatics
2 shared publications
Latest Publications
- Open Access
- 13 August 2026
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 394, 229-237
Tight inapproximability of target set reconfiguration
- 13 August 2026
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 394, 229-237
Open AccessTight inapproximability of target set reconfiguration
- Open Access
- 13 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-12
DiverXplorer: Stock Image Exploration via Diversity Adjustment for Graphic Design
Graphic designers explore large stock image collections during open-ended or early-stage design tasks, yet common tools emphasize relevance and similarity, limiting designers’ ability to overview the design space or discover visual patterns. We present an image exploration prototype that enables stepwise adjustment of diversity, allowing users to transition from diverse overviews to increasingly focused subsets during exploration. Our approach implements diversity control via determinantal point process (DPP)-based sampling and exposes diversity-similarity tradeoffs through interaction rather than static ranking. We report findings from a pilot study with professional graphic designers comparing our technique to baselines inspired by current tools in open-ended image selection tasks. Results suggest that stepwise diversity control supports early-stage sensemaking and comparison of visual patterns, while revealing important tradeoffs: diversity aids discovery and reduces backtracking, but becomes less desirable as exploration progresses. We aim to provide a novel perspective on how to implement transitions between diversity and similarity. Our code is available at https://github.com/CyberAgentAILab/DiverXplorer.
- 13 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Open AccessDiverXplorer: Stock Image Exploration via Diversity Adjustment for Graphic Design
Graphic designers explore large stock image collections during open-ended or early-stage design tasks, yet common tools emphasize relevance and similarity, limiting designers’ ability to overview the design space or discover visual patterns. We present an image exploration prototype that enables stepwise adjustment of diversity, allowing users to transition from diverse overviews to increasingly focused subsets during exploration. Our approach implements diversity control via determinantal point process (DPP)-based sampling and exposes diversity-similarity tradeoffs through interaction rather than static ranking. We report findings from a pilot study with professional graphic designers comparing our technique to baselines inspired by current tools in open-ended image selection tasks. Results suggest that stepwise diversity control supports early-stage sensemaking and comparison of visual patterns, while revealing important tradeoffs: diversity aids discovery and reduces backtracking, but becomes less desirable as exploration progresses. We aim to provide a novel perspective on how to implement transitions between diversity and similarity. Our code is available at https://github.com/CyberAgentAILab/DiverXplorer.
- Open Access
- 6 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (2) , 1-38
Gap Amplification for Reconfiguration Problems
Combinatorial reconfiguration is a brand-new field aimed at investigating the connectivity of the solution space of a combinatorial problem. We study the hardness of achieving “approximate” reconfigurability, which allows to relax the feasibility of intermediate solutions. For example, in the Minmax Set Cover Reconfiguration problem, given a set family and a pair of its covers, we are asked to transform one cover into the other by repeatedly adding or removing a single set from the family. The objective is to minimize the maximum size of covers encountered during the transformation. The recent study by Ohsaka (STACS 2023) showed that several reconfiguration problems are \(\mathbf{PSPACE}\) -hard to approximate assuming the Reconfiguration Inapproximability Hypothesis (RIH) . One limitation of this approach is that inapproximability factors are not explicitly shown, so that even a \(1.00\cdots 001\) -approximation algorithm for Minmax Set Cover Reconfiguration may not be ruled out, whereas it admits a 2-factor approximation algorithm due to Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (TCS 2011). In this article, we demonstrate gap amplification for reconfiguration problems. Specifically, we establish explicit \(\mathbf{PSPACE}\) -hardness of approximation factors for three reconfiguration problems, assuming only RIH. Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is \(\mathbf{PSPACE}\) -hard to approximate within a factor of 0.9942. The crux of its proof is an alteration of the gap amplification technique due to Dinur (JACM 2007), which boosts the 1 vs. \(1-\varepsilon\) gap to the 1 vs. \(1-0.0058\) gap for any small positive real \(\varepsilon\) . As an application of the main result, we further show that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguration are \(\mathbf{PSPACE}\) -hard to approximate within a factor of 1.0029 under RIH.- 6 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (2) , 1-38
Open AccessGap Amplification for Reconfiguration Problems
Combinatorial reconfiguration is a brand-new field aimed at investigating the connectivity of the solution space of a combinatorial problem. We study the hardness of achieving “approximate” reconfigurability, which allows to relax the feasibility of intermediate solutions. For example, in the Minmax Set Cover Reconfiguration problem, given a set family and a pair of its covers, we are asked to transform one cover into the other by repeatedly adding or removing a single set from the family. The objective is to minimize the maximum size of covers encountered during the transformation. The recent study by Ohsaka (STACS 2023) showed that several reconfiguration problems are \(\mathbf{PSPACE}\) -hard to approximate assuming the Reconfiguration Inapproximability Hypothesis (RIH) . One limitation of this approach is that inapproximability factors are not explicitly shown, so that even a \(1.00\cdots 001\) -approximation algorithm for Minmax Set Cover Reconfiguration may not be ruled out, whereas it admits a 2-factor approximation algorithm due to Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (TCS 2011). In this article, we demonstrate gap amplification for reconfiguration problems. Specifically, we establish explicit \(\mathbf{PSPACE}\) -hardness of approximation factors for three reconfiguration problems, assuming only RIH. Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is \(\mathbf{PSPACE}\) -hard to approximate within a factor of 0.9942. The crux of its proof is an alteration of the gap amplification technique due to Dinur (JACM 2007), which boosts the 1 vs. \(1-\varepsilon\) gap to the 1 vs. \(1-0.0058\) gap for any small positive real \(\varepsilon\) . As an application of the main result, we further show that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguration are \(\mathbf{PSPACE}\) -hard to approximate within a factor of 1.0029 under RIH. - Open Access
- 19 November 2025
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 157
Gap preserving reductions between reconfiguration problems
- 19 November 2025
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 157
Open AccessGap preserving reductions between reconfiguration problems
- Open Access
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\varphi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses of $\varphi$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin E$k$-SAT Reconfiguration is $1 - Θ\left(\frac{1}{k}\right)$. On the algorithmic side, we develop a deterministic $\left(1-\frac{1}{k-1}-\frac{1}{k}\right)$-factor approximation algorithm for every $k \geq 3$. On the hardness side, we show that it is $\mathsf{PSPACE}$-hard to approximate this problem within a factor of $1-\frac{1}{10k}$ for every sufficiently large $k$. Note that an ``$\mathsf{NP}$ analogue'' of Maxmin E$k$-SAT Reconfiguration is Max E$k$-SAT, whose approximation threshold is $1-\frac{1}{2^k}$ shown by Håstad (JACM 2001). To the best of our knowledge, this is the first reconfiguration problem whose approximation threshold is (asymptotically) worse than that of its $\mathsf{NP}$ analogue. To prove the hardness result, we introduce a new ``non-monotone'' test, which is specially tailored to reconfiguration problems, despite not being helpful in the PCP regime.Open AccessAsymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\varphi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses of $\varphi$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin E$k$-SAT Reconfiguration is $1 - Θ\left(\frac{1}{k}\right)$. On the algorithmic side, we develop a deterministic $\left(1-\frac{1}{k-1}-\frac{1}{k}\right)$-factor approximation algorithm for every $k \geq 3$. On the hardness side, we show that it is $\mathsf{PSPACE}$-hard to approximate this problem within a factor of $1-\frac{1}{10k}$ for every sufficiently large $k$. Note that an ``$\mathsf{NP}$ analogue'' of Maxmin E$k$-SAT Reconfiguration is Max E$k$-SAT, whose approximation threshold is $1-\frac{1}{2^k}$ shown by Håstad (JACM 2001). To the best of our knowledge, this is the first reconfiguration problem whose approximation threshold is (asymptotically) worse than that of its $\mathsf{NP}$ analogue. To prove the hardness result, we introduce a new ``non-monotone'' test, which is specially tailored to reconfiguration problems, despite not being helpful in the PCP regime. - Open Access
- 4 January 2025
- Published by Elsevier in Information Processing Letters
- Vol. 189
On approximate reconfigurability of label cover
- 4 January 2025
- Published by Elsevier in Information Processing Letters
- Vol. 189
Open AccessOn approximate reconfigurability of label cover
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1435-1445
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at most one bit, and every proof can be probabilistically checked by reading a constant number of bits. Using the new characterization, we prove PSPACE-completeness of approximate versions of many reconfiguration problems, such as the Maxmin 3-SAT Reconfiguration problem. This resolves the open problem posed by Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (ISAAC 2008; Theor. Comput. Sci. 2011) as well as the Reconfiguration Inapproximability Hypothesis by Ohsaka (STACS 2023) affirmatively. We also present PSPACE-completeness of approximating the Maxmin Clique Reconfiguration problem to within a factor of nε for some constant ε > 0.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1435-1445
Open AccessProbabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at most one bit, and every proof can be probabilistically checked by reading a constant number of bits. Using the new characterization, we prove PSPACE-completeness of approximate versions of many reconfiguration problems, such as the Maxmin 3-SAT Reconfiguration problem. This resolves the open problem posed by Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (ISAAC 2008; Theor. Comput. Sci. 2011) as well as the Reconfiguration Inapproximability Hypothesis by Ohsaka (STACS 2023) affirmatively. We also present PSPACE-completeness of approximating the Maxmin Clique Reconfiguration problem to within a factor of nε for some constant ε > 0.
- 24 March 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 997
Computational complexity of normalizing constants for the product of determinantal point processes
- 24 March 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 997
Computational complexity of normalizing constants for the product of determinantal point processes
- Open Access
Gap Amplification for Reconfiguration Problems
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 reconfiguration problems only assuming the Reconfiguration Inapproximability Hypothesis (RIH) due to Ohsaka (STACS 2023). Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is PSPACE-hard to approximate within a factor of $0.9942$. Moreover, the same result holds even if the constraint graph is restricted to $(d,λ)$-expander for arbitrarily small $\fracλ{d}$. The crux of its proof is an alteration of the gap amplification technique due to Dinur (J. ACM, 2007), which amplifies the $1$ vs. $1-\varepsilon$ gap for arbitrarily small $\varepsilon \in (0,1)$ up to the $1$ vs. $1-0.0058$ gap. As an application of the main result, we demonstrate that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguratio} are PSPACE-hard to approximate within a factor of $1.0029$ under RIH. Our proof is based on a gap-preserving reduction from Label Cover to Set Cover due to Lund and Yannakakis (J. ACM, 1994). Unlike Lund--Yannakakis' reduction, the expander mixing lemma is essential to use. We highlight that all results hold unconditionally as long as "PSPACE-hard" is replaced by "NP-hard," and are the first explicit inapproximability results for reconfiguration problems without resorting to the parallel repetition theorem. We finally complement the main result by showing that it is NP-hard to approximate Maxmin 2-CSP Reconfiguration within a factor better than $\frac{3}{4}$.Open AccessGap Amplification for Reconfiguration Problems
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 reconfiguration problems only assuming the Reconfiguration Inapproximability Hypothesis (RIH) due to Ohsaka (STACS 2023). Our main result is that under RIH, Maxmin 2-CSP Reconfiguration is PSPACE-hard to approximate within a factor of $0.9942$. Moreover, the same result holds even if the constraint graph is restricted to $(d,λ)$-expander for arbitrarily small $\fracλ{d}$. The crux of its proof is an alteration of the gap amplification technique due to Dinur (J. ACM, 2007), which amplifies the $1$ vs. $1-\varepsilon$ gap for arbitrarily small $\varepsilon \in (0,1)$ up to the $1$ vs. $1-0.0058$ gap. As an application of the main result, we demonstrate that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguratio} are PSPACE-hard to approximate within a factor of $1.0029$ under RIH. Our proof is based on a gap-preserving reduction from Label Cover to Set Cover due to Lund and Yannakakis (J. ACM, 1994). Unlike Lund--Yannakakis' reduction, the expander mixing lemma is essential to use. We highlight that all results hold unconditionally as long as "PSPACE-hard" is replaced by "NP-hard," and are the first explicit inapproximability results for reconfiguration problems without resorting to the parallel repetition theorem. We finally complement the main result by showing that it is NP-hard to approximate Maxmin 2-CSP Reconfiguration within a factor better than $\frac{3}{4}$. - Open Access
Tight Inapproximability of Target Set Reconfiguration
Given a graph $G$ with a vertex threshold function $τ$, consider a dynamic process in which any inactive vertex $v$ becomes activated whenever at least $τ(v)$ of its neighbors are activated. A vertex set $S$ is called a target set if all vertices of $G$ would be activated when initially activating vertices of $S$. In the Minmax Target Set Reconfiguration problem, for a graph $G$ and its two target sets $X$ and $Y$, we wish to transform $X$ into $Y$ by repeatedly adding or removing a single vertex, using only target sets of $G$, so as to minimize the maximum size of any intermediate target set. We prove that it is NP-hard to approximate Minmax Target Set Reconfiguration within a factor of $2-o\left(\frac{1}{\operatorname{polylog} n}\right)$, where $n$ is the number of vertices. Our result establishes a tight lower bound on approximability of Minmax Target Set Reconfiguration, which admits a $2$-factor approximation algorithm. The proof is based on a gap-preserving reduction from Target Set Selection to Minmax Target Set Reconfiguration, where NP-hardness of approximation for the former problem is proven by Chen (SIAM J. Discrete Math., 2009) and Charikar, Naamad, and Wirth (APPROX/RANDOM 2016).Open AccessTight Inapproximability of Target Set Reconfiguration
Given a graph $G$ with a vertex threshold function $τ$, consider a dynamic process in which any inactive vertex $v$ becomes activated whenever at least $τ(v)$ of its neighbors are activated. A vertex set $S$ is called a target set if all vertices of $G$ would be activated when initially activating vertices of $S$. In the Minmax Target Set Reconfiguration problem, for a graph $G$ and its two target sets $X$ and $Y$, we wish to transform $X$ into $Y$ by repeatedly adding or removing a single vertex, using only target sets of $G$, so as to minimize the maximum size of any intermediate target set. We prove that it is NP-hard to approximate Minmax Target Set Reconfiguration within a factor of $2-o\left(\frac{1}{\operatorname{polylog} n}\right)$, where $n$ is the number of vertices. Our result establishes a tight lower bound on approximability of Minmax Target Set Reconfiguration, which admits a $2$-factor approximation algorithm. The proof is based on a gap-preserving reduction from Target Set Selection to Minmax Target Set Reconfiguration, where NP-hardness of approximation for the former problem is proven by Chen (SIAM J. Discrete Math., 2009) and Charikar, Naamad, and Wirth (APPROX/RANDOM 2016).