NONaoto Ohsaka

Naoto Ohsaka

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    DiverXplorer: Stock Image Exploration via Diversity Adjustment for Graphic Design

    by Antonio Tejero-De-Pablos, Sichao Song, Naoto Ohsaka, Mayu Otani, Shin’IChi Satoh

    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

    Gap Amplification for Reconfiguration Problems

    by Naoto Ohsaka

    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

    Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

    by Shuichi Hirahara, Naoto Ohsaka

    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

    Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

    by 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 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.


  • Open Access

    Gap Amplification for Reconfiguration Problems

    by 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 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

    by Naoto Ohsaka

    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).