14 citations · 59 across the 21 of their papers we have counts for
23 papers
DiverXplorer: Stock Image Exploration via Diversity Adjustment for Graphic Design
Antonio Tejero-de-Pablos, Sichao Song, Naoto Ohsaka +2
Graphic designers explore large stock image collections during open-ended or early-stage design tasks, yet common tools emphasize relevance and similarity, limiting designers' abil…
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…
Alphabet Reduction for Reconfiguration Problems
Naoto Ohsaka
We present a reconfiguration analogue of alphabet reduction à la Dinur (J. ACM, 2007) and its applications. Given a binary constraint graph and its two satisfying assignments $…
Tight Inapproximability of Target Set Reconfiguration
Naoto Ohsaka
Given a graph with a vertex threshold function , consider a dynamic process in which any inactive vertex becomes activated whenever at least of its neighbors have…
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…
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…
Fast and Examination-agnostic Reciprocal Recommendation in Matching Markets
Yoji Tomita, Riku Togashi, Yuriko Hashizume +1
In matching markets such as job posting and online dating platforms, the recommender system plays a critical role in the success of the platform. Unlike standard recommender system…
Safe Collaborative Filtering
Riku Togashi, Tatsushi Oka, Naoto Ohsaka +1
Excellent tail performance is crucial for modern machine learning tasks, such as algorithmic fairness, class imbalance, and risk-sensitive decision making, as it ensures the effect…
A Critical Reexamination of Intra-List Distance and Dispersion
Naoto Ohsaka, Riku Togashi
Diversification of recommendation results is a promising approach for coping with the uncertainty associated with users' information needs. Of particular importance in diversified…
Curse of "Low" Dimensionality in Recommender Systems
Naoto Ohsaka, Riku Togashi
Beyond accuracy, there are a variety of aspects to the quality of recommender systems, such as diversity, fairness, and robustness. We argue that many of the prevalent problems in…
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…
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…
On the Parameterized Intractability of Determinant Maximization
Naoto Ohsaka
In the Determinant Maximization problem, given an positive semi-definite matrix in and an integer , we are required to find a $k\ti…
Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes
Naoto Ohsaka, Tatsuya Matsuoka
We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as…
Reconfiguration Problems on Submodular Functions
Naoto Ohsaka, Tatsuya Matsuoka
Reconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Sc…
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
Naoto Ohsaka
We study the computational complexity of two hard problems on determinantal point processes (DPPs). One is maximum a posteriori (MAP) inference, i.e., to find a principal submatrix…
On Reconfigurability of Target Sets
Naoto Ohsaka
We study the problem of deciding reconfigurability of target sets of a graph. Given a graph with vertex thresholds , consider a dynamic process in which vertex becomes a…
A Fully Polynomial Parameterized Algorithm for Counting the Number of Reachable Vertices in a Digraph
Naoto Ohsaka
We consider the problem of counting the number of vertices reachable from each vertex in a digraph , which is equal to computing all the out-degrees of the transitive closure of…
Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate
Tatsuya Matsuoka, Naoto Ohsaka
We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph and a positive semi-definite matrix indexed by , a spanning-…
Predictive Optimization with Zero-Shot Domain Adaptation
Tomoya Sakai, Naoto Ohsaka
Prediction in a new domain without any training sample, called zero-shot domain adaptation (ZSDA), is an important task in domain adaptation. While prediction in a new domain has g…
The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches
Naoto Ohsaka
Influence maximization is among the most fundamental algorithmic problems in social influence analysis. Over the last decade, a great effort has been devoted to developing efficien…
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka
There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of su…