Publications

2023

Optimal distributed covering algorithms.
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman
Distributed Comput., 36(1) 45-55, 2023

Bandit Task Assignment with Unknown Processing Time.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
NeurIPS, 2023

A half-integral Erdős-Pósa theorem for directed odd cycles.
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie
SODA, 3043-3062, 2023

Rooted topological minors on four vertices.
Koyo Hayashi, Ken-ichi Kawarabayashi
J. Comb. Theory, Ser. B, 158(Part) 146-185, 2023

Additive non-approximability of chromatic number in proper minor-closed classes.
Zdenek Dvorák, Ken-ichi Kawarabayashi
J. Comb. Theory, Ser. B, 158(Part) 74-92, 2023

2022

Directed Tangle Tree-Decompositions and Applications.
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms(SODA), 377-405, 2022

Query Obfuscation by Semantic Decomposition.
Danushka Bollegala, Tomoya Machide, Ken-ichi Kawarabayashi
13th Language Resources and Evaluation Conference(LREC), 6200-6211, 2022

A Polynomial Excluded-Minor Approximation of Treedepth.
K. Kawarabayashi and B. Rossman
J. Eur. Math. Soc, 24 1449-1470, 2022

Online Task Assignment Problems with Reusable Resources.
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
AAAI, 5199-5207, 2022

2021

The Effect of Random Projection on Local Intrinsic Dimensionality.
Michael E. Houle, Ken-ichi Kawarabayashi
Similarity Search and Applications - 14th International Conference(SISAP), 201-214, 2021

How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-ichi Kawarabayashi, Stefanie Jegelka
9th International Conference on Learning Representations(ICLR), 2021

Automorphisms and Isomorphisms of Maps in Linear Time.
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman
48th International Colloquium on Automata, Languages, and Programming(ICALP), 86-15, 2021

Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut.
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
FOCS, 480-491, 2021

RelWalk - A Latent Variable Model Approach to Knowledge Graph Embedding.
Danushka Bollegala, Huda Hakami, Yuichi Yoshida, Ken-ichi Kawarabayashi
Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume(EACL), 1551-1565, 2021

CutTheTail: An Accurate and Space-Efficient Heuristic Algorithm for Influence Maximization.
Diana Popova, Ken-ichi Kawarabayashi, Alex Thomo
The Computer Journal, 64(9) 1343-1357, 2021

Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Thirty-Fifth AAAI Conference on Artificial Intelligence(AAAI), 9791-9798, 2021

A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
The 24th International Conference on Artificial Intelligence and Statistics(AISTATS), 3367-3375, 2021

2020

Improved Distributed Approximations for Maximum Independent Set.
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, Gregory Schwartzman
34th International Symposium on Distributed Computing(DISC), 35-16, Oct, 2020

A nearly 5/3-approximation FPT Algorithm for Min-k-Cut.
Ken-ichi Kawarabayashi, Bingkai Lin
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms(SODA), 990-999, 2020

The Directed Flat Wall Theorem.
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms(SODA), 239-258, 2020

Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set.
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, Gregory Schwartzman
PODC '20: ACM Symposium on Principles of Distributed Computing(PODC), 283-285, 2020

Delay and Cooperation in Nonstochastic Linear Bandits.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020(NeurIPS), 2020

What Can Neural Networks Reason About?
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka
8th International Conference on Learning Representations(ICLR), 2020

Model-Checking on Ordered Structures.
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz
ACM Trans. Comput. Log., 21(2) 11-28, 2020

Minimum Violation Vertex Maps and Their Applications to Cut Problems.
Ken-ichi Kawarabayashi, Chao Xu
SIAM J. Discret. Math., 34(4) 2183-2207, 2020

Linear min-max relation between the treewidth of an H-minor-free graph and its largest grid minor.
Ken-ichi Kawarabayashi, Yusuke Kobayashi 0001
J. Comb. Theory, Ser. B, 141 165-180, 2020

2019

Optimal Distributed Covering Algorithms.
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman
33rd International Symposium on Distributed Computing(DISC), 5-15, 2019

Parameterized Distributed Algorithms.
Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman
33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary., 6-16, 2019

Optimal Distributed Covering Algorithms.
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman
33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary., 104-106, 2019

Polylogarithmic approximation for Euler genus on bounded degree graphs.
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., 164-175, 2019

Intrinsic Dimensionality Estimation within Tight Localities.
Laurent Amsaleg, Oussama Chelly,Michael E. Houle, Ken-ichi Kawarabayashi, Milos Radovanovic, Weeris Treeratanajaru
Proceedings of the 2019 SIAM International Conference on Data Mining, SDM 2019, Calgary, Alberta, Canada, May 2-4, 2019., 181-189, 2019

Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising.
Daisuke Hatano, Yuko Kuroki, Yasushi Kawase, Hanna Sumita, Naonori Kakimura, Ken-ichi Kawarabayashi
PRICAI 2019: Trends in Artificial Intelligence - 16th Pacific Rim International Conference on Artificial Intelligence, Cuvu, Yanuca Island, Fiji, August 26-30, 2019, Proceedings, Part I, 568-582, 2019

Improved Regret Bounds for Bandit Combinatorial Optimization.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada., 12027-12036, 2019

Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada., 10589-10598, 2019

Are Girls Neko or Shōjo? Cross-Lingual Alignment of Non-Isomorphic Embeddings with Iterative Normalization.
Mozhi Zhang, Keyulu Xu, Ken-ichi Kawarabayashi, Stefanie Jegelka, Jordan L. Boyd-Graber
Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers, 3180-3189, 2019

Stochastic Submodular Maximization with Performance-Dependent Item Costs.
Takuro Fukunaga, Takuya Konishi, Sumio Fujita, Ken-ichi Kawarabayashi
The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Hono, 1485-1494, 2019

K6 minors in 6-connected graphs of bounded tree-width.
Ken-ichi Kawarabayashi, Serguei Norine, Robin Thoma, Paul Wollan
J. Comb. Theory, Ser. B, 136 1-32, 2019

Polynomial Planar Directed Grid Theorem.
Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, 1465-1484, 2019

Deterministic Edge Connectivity in Near-Linear Time.
Ken-ichi Kawarabayashi, Mikkel Thorup
J. ACM, 66(1) 4-50, 2019

2018

ClassiNet - Predicting Missing Features for Short-Text Classification.
Danushka Bollegala,Vincent Atanasov, Takanori Maehara, Ken-ichi Kawarabayashi
Transactions on Knowledge Discovery from Data, 12(5) 55:1-55:29, Jun, 2018

Optimal cache placement for an academic backbone network
Than Nguyen Hau, Naonori Kakimura, Ken-Ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, Yu Yokoi
Journal of the Operations Research Society of Japan, 61(2) 197-216, Apr 1, 2018

Jointly learning word embeddings using a corpus and a knowledge base
Mohammed Alsuhaibani, Danushka Bollegala, Takanori Maehara, Ken-ichi Kawarabayashi
PLoS ONE, 13(3), Mar 1, 2018

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs.
Ken-ichi Kawarabayashi, Yusuke Kobayashi
SIAM J. Comput., 47(4) 1483-1504, 2018

A Polynomial Excluded-Minor Approximation of Treedepth.
Ken-ichi Kawarabayashi, Benjamin Rossman
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, 234-246, 2018

Online Regression with Partial Information: Generalization and Linear Projection.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, 1599-1607, 2018

A new proof of the flat wall theorem.
Ken-ichi Kawarabayashi, Robin Thoma, Paul Wollan
J. Comb. Theory, Ser. B, 129 204-238, 2018

K6 minors in large 6-connected graphs.
Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan
J. Comb. Theory, Ser. B, 129 158-203, 2018

Adapting Local Sequential Algorithms to the Distributed Setting.
Ken-ichi Kawarabayashi, Gregory Schwartzman
32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, 35-17, 2018

NoSingles: a space-efficient algorithm for influence maximization.
Diana Popova, Naoto Ohsaka, Ken-ichi Kawarabayashi, Alex Thomo
Proceedings of the 30th International Conference on Scientific and Statistical Database Management, SSDBM 2018, Bozen-Bolzano, Italy, July 09-11, 2018, 18:1-18:12-12, 2018

A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(logN log varDelta /log ^2log varDelta ) Rounds.
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman
Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, 226-236, 2018

Regret Bounds for Online Portfolio Selection with a Cardinality Constraint.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., 10611-10620, 2018

Think Globally, Embed Locally - Locally Linear Meta-embedding of Words.
Danushka Bollegala, Kohei Hayashi, Ken-ichi Kawarabayashi
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden., 3970-3976, 2018

Causal Bandits with Propagating Inference.
Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, Ken-ichi Kawarabayashi
Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, 5508-5516, 2018

Representation Learning on Graphs with Jumping Knowledge Networks.
Keyulu Xu,Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, Stefanie Jegelka
Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, 5449-5458, 2018

Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes.
Zdenek Dvorák, Ken-ichi Kawarabayashi
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, 47:1-47:12-12, 2018

Boosting PageRank Scores by Optimizing Internal Link Structure.
Naoto Ohsaka, Tomohiro Sonobe, Naonori Kakimura, Takuro Fukunaga, Sumio Fujita, Ken-ichi Kawarabayashi
Database and Expert Systems Applications - 29th International Conference, DEXA 2018, Regensburg, Germany, September 3-6, 2018, Proceedings, Part I, 424-439, 2018

Using k-Way Co-Occurrences for Learning Word Embeddings.
Danushka Bollegala, Yuichi Yoshida, Ken-ichi Kawarabayashi
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orl, 5037-5044, 2018

ClassiNet - Predicting Missing Features for Short-Text Classification.
Danushka Bollegala,Vincent Atanasov, Takanori Maehara, Ken-ichi Kawarabayashi
TKDD, 12(5) 55:1-55:29-29, 2018

Existence of outsiders as a characteristic of online communication networks.
Taro Takaguchi, Takanori Maehara, Ken-ichi Kawarabayashi, Masashi Toyoda
Network Science, 6(4) 431-447, 2018

The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs.
Naonori Kakimura, Ken-ichi Kawarabayashi
J. Comb. Theory, Ser. B, 131 138-169, 2018

Extreme-value-theoretic estimation of local intrinsic dimensionality.
Laurent Amsaleg, Array,Teddy Furon, Stéphane Girard, Michael E. Houle, Ken-ichi Kawarabayashi, Michael Nett
Data Min. Knowl. Discov., 32(6) 1768-1805, 2018

2017

Coherent Ising machines-optical neural networks operating at the quantum limit
Yoshihisa Yamamoto, Kazuyuki Aihara, Timothee Leleu, Ken-ichi Kawarabayashi, Satoshi Kako, Martin Fejer, Kyo Inoue, Hiroki Takesue
NPJ QUANTUM INFORMATION 3 2017年12月

Triangle-free graphs of tree-width t are ⌈ (t+3)/2 ⌉-colorable.
Zdenek Dvorák, Ken-ichi Kawarabayashi
EUROPEAN JOURNAL OF COMBINATORICS, 66 95-100, Dec, 2017

Learning linear transformations between counting-based and prediction-based word embeddings
Danushka Bollegala, Kohei Hayashi, Ken-Ichi Kawarabayashi
PLoS ONE, 12(9), Sep 1, 2017

An iterative approach for the global estimation of sentence similarity.
Tomoyuki Kajiwara, Danushka Bollegala, Yuichi Yoshida, Ken-ichi Kawarabayashi
PLOS ONE, 12(9) 1-15, Sep, 2017

Coarsening massive influence networks for scalable diffusion analysis.
Naoto Ohsaka, Tomohiro Sonobe, Sumio Fujita, Ken-Ichi Kawarabayashi
Proceedings of the ACM SIGMOD International Conference on Management of Data, 127746 635-650, May 9, 2017

Matching extension missing vertices and edges in triangulations of surfaces
Kawarabayashi Ken-ichi, Ozeki Kenta, Plummer Michael D
Journal of Graph Theory 85(1) 249-257-257, May, 2017

Coloring 3-Colorable Graphs with Less than n(1/5) Colors Ken-Ichi Kawarabayashi, Mikkel Thorup Journal of the ACM 64(1), Mar, 2017

Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, 4102-4111, 2017

Polylogarithmic approximation for minimum planarization (almost)
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 779-788, 2017

An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization.
Hanna Sumita, Yuma Yonebayashi, Naonori Kakimura, Ken-ichi Kawarabayashi
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 4412-4418, 2017

FO model checking on map graphs
Kord Eickmeyer, Ken-ichi Kawarabayashi
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10472 204-216, 2017

Packing Edge-Disjoint Odd Eulerian Subgraphs through Prescribed Vertices in 4-edge-conntected Graphs.
Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi
SIAM JOURNAL ON DISCRETE MATHEMATICS, 31(2) 766-782, 2017

Scalable Algorithm for Higher-Order Co-Clustering via Random Sampling.
Daisuke Hatano, Takuro Fukunaga, Takanori Maehara, Ken-ichi Kawarabayashi
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., 1992-1999, 2017

Optimal Pricing for Submodular Valuations with Bounded Curvature.
Takanori Maehara, Yasushi Kawase, Hanna Sumita, Katsuya Tono, Ken-ichi Kawarabayashi
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., 622-628, 2017