We stand with Ukraine  

Naoto Ohsaka

Orcid: 0000-0001-9584-4764

According to our database1, Naoto Ohsaka authored at least 40 papers between 2011 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
On the Parameterized Intractability of Determinant Maximization.
[BibTeX]
[DOI]
Naoto Ohsaka
Algorithmica, June, 2024

Computational complexity of normalizing constants for the product of determinantal point processes.
[BibTeX]
[DOI]
Tatsuya Matsuoka
,
Naoto Ohsaka
Theor. Comput. Sci., 2024

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration.
[BibTeX]
[DOI]
Shuichi Hirahara
,
Naoto Ohsaka
Electron. Colloquium Comput. Complex., 2024

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.
[BibTeX]
[DOI]
Shuichi Hirahara
,
Naoto Ohsaka
Electron. Colloquium Comput. Complex., 2024

Asymptotic Inapproximability of Reconfiguration Problems: Maxmin <i>k</i>-Cut and Maxmin E<i>k</i>-SAT.
[BibTeX]
[DOI]
Shuichi Hirahara
,
Naoto Ohsaka
CoRR, 2024

Tight Inapproximability of Target Set Reconfiguration.
[BibTeX]
[DOI]
Naoto Ohsaka
CoRR, 2024

Gap Amplification for Reconfiguration Problems.
[BibTeX]
[DOI]
Naoto Ohsaka
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Matroid Semi-Bandits in Sublinear Time.
[BibTeX]
[DOI]
Ruo-Chun Tzeng
,
Naoto Ohsaka
,
Kaito Ariu
Proceedings of the Forty-first International Conference on Machine Learning, 2024

Safe Collaborative Filtering.
[BibTeX]
[DOI]
Riku Togashi
,
Tatsushi Oka
,
Naoto Ohsaka
,
Tetsuro Morimura
Proceedings of the Twelfth International Conference on Learning Representations, 2024

Alphabet Reduction for Reconfiguration Problems.
[BibTeX]
[DOI]
Naoto Ohsaka
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023
On reconfigurability of target sets.
[BibTeX]
[DOI]
Naoto Ohsaka
Theor. Comput. Sci., 2023

On Approximate Reconfigurability of Label Cover.
[BibTeX]
[DOI]
Naoto Ohsaka
CoRR, 2023

Gap Preserving Reductions Between Reconfiguration Problems.
[BibTeX]
[DOI]
Naoto Ohsaka
Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

A Critical Reexamination of Intra-List Distance and Dispersion.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Riku Togashi
Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2023

Curse of "Low" Dimensionality in Recommender Systems.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Riku Togashi
Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2023

Fast and Examination-agnostic Reciprocal Recommendation in Matching Markets.
[BibTeX]
[DOI]
Yoji Tomita
,
Riku Togashi
,
Yuriko Hashizume
,
Naoto Ohsaka
Proceedings of the 17th ACM Conference on Recommender Systems, 2023

2022
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes.
[BibTeX]
[DOI]
Naoto Ohsaka
J. Artif. Intell. Res., 2022

Reconfiguration Problems on Submodular Functions.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Tatsuya Matsuoka
Proceedings of the WSDM '22: The Fifteenth ACM International Conference on Web Search and Data Mining, Virtual Event / Tempe, AZ, USA, February 21, 2022

2021
Spanning tree constrained determinantal point processes are hard to (approximately) evaluate.
[BibTeX]
[DOI]
Tatsuya Matsuoka
,
Naoto Ohsaka
Oper. Res. Lett., 2021

A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph.
[BibTeX]
[DOI]
Naoto Ohsaka
Inf. Process. Lett., 2021

Approximation algorithm for submodular maximization under submodular cover.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Tatsuya Matsuoka
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Predictive Optimization with Zero-Shot Domain Adaptation.
[BibTeX]
[DOI]
Tomoya Sakai
,
Naoto Ohsaka
Proceedings of the 2021 SIAM International Conference on Data Mining, 2021

Unconstrained MAP Inference, Exponentiated Determinantal Point Processes, and Exponential Inapproximability.
[BibTeX]
[DOI]
Naoto Ohsaka
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

Tracking Regret Bounds for Online Submodular Optimization.
[BibTeX]
[DOI]
Tatsuya Matsuoka
,
Shinji Ito
,
Naoto Ohsaka
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

On the Convex Combination of Determinantal Point Processes.
[BibTeX]
[DOI]
Tatsuya Matsuoka
,
Naoto Ohsaka
,
Akihiro Yabe
Proceedings of the Asian Conference on Machine Learning, 2021

Maximization of Monotone k-Submodular Functions with Bounded Curvature and Non-k-Submodular Functions.
[BibTeX]
[DOI]
Tatsuya Matsuoka
,
Naoto Ohsaka
Proceedings of the Asian Conference on Machine Learning, 2021

2020
The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches.
[BibTeX]
[DOI]
Naoto Ohsaka
Proceedings of the 2020 International Conference on Management of Data, 2020

A Predictive Optimization Framework for Hierarchical Demand Matching.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Tomoya Sakai
,
Akihiro Yabe
Proceedings of the 2020 SIAM International Conference on Data Mining, 2020

On the (In)tractability of Computing Normalizing Constants for the Product of Determinantal Point Processes.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Tatsuya Matsuoka
Proceedings of the 37th International Conference on Machine Learning, 2020

2018
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms.
[BibTeX]
[DOI]
Yoichi Iwata
,
Tomoaki Ogasawara
,
Naoto Ohsaka
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

NoSingles: a space-efficient algorithm for influence maximization.
[BibTeX]
[DOI]
Diana Popova
,
Naoto Ohsaka
,
Ken-ichi Kawarabayashi
,
Alex Thomo
Proceedings of the 30th International Conference on Scientific and Statistical Database Management, 2018

Boosting PageRank Scores by Optimizing Internal Link Structure.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Tomohiro Sonobe
,
Naonori Kakimura
,
Takuro Fukunaga
,
Sumio Fujita
,
Ken-ichi Kawarabayashi
Proceedings of the Database and Expert Systems Applications, 2018

2017
Portfolio Optimization for Influence Spread.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Yuichi Yoshida
Proceedings of the 26th International Conference on World Wide Web, 2017

Coarsening Massive Influence Networks for Scalable Diffusion Analysis.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Tomohiro Sonobe
,
Sumio Fujita
,
Ken-ichi Kawarabayashi
Proceedings of the 2017 ACM International Conference on Management of Data, 2017

2016
Dynamic Influence Analysis in Evolving Networks.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Takuya Akiba
,
Yuichi Yoshida
,
Ken-ichi Kawarabayashi
Proc. VLDB Endow., 2016

Maximizing Time-Decaying Influence in Social Networks.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Yutaro Yamaguchi
,
Naonori Kakimura
,
Ken-ichi Kawarabayashi
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2016

2015
Monotone k-Submodular Function Maximization with Size Constraints.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Yuichi Yoshida
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Efficient PageRank Tracking in Evolving Networks.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Takanori Maehara
,
Ken-ichi Kawarabayashi
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

2014
Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Takuya Akiba
,
Yuichi Yoshida
,
Ken-ichi Kawarabayashi
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2011
A reinforcement learning method to improve the sweeping efficiency for an agent.
[BibTeX]
[DOI]
Naoto Ohsaka
,
Daisuke Kitakoshi
,
Masato Suzuki
Proceedings of the 2011 IEEE International Conference on Granular Computing, 2011


  Loading...