Publications of 2019

Publications of 2014　 Publications of 2015　 Publications of 2016　 Publications of 2017　Publications of 2018　　　

A: Sublinear-time Algorithm Group (Team A)
D: Sublinear Data Structure Group (Team D)
M: Sublinear-time Modeling Group (Team M)

Awards

A DAYPLA Award (Sponsor Special Award), Web Intelligence and Interaction Research Group, Munehiko Sasajima, 29/06/19.

D 2019 Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science and Technology Science and Technology Award (Science and Technology Promotion Division), Ministry of Education, Culture, Sports, Science and Technology, Katsutoshi Yada, 09/04/19.

D Minister of Education, Culture, Sports, Science and Technology Young Scientist Award, Ministry of Education, Culture, Sports, Science and Technology, Shin-ichi Tanigawa, 17/04/19.

D Best Paper Award, The 16th International Symposium on Algorithms and Data Structures (WADS 2019), Sankardeep Chakraborty, 07/08/19.

D IPSJ Hokkaido Branch Academic Research Award, IPSJ, Naoya Toriyabe, Isamu Furuya and Takuya Kida, 05/10/19.

D Okawa Publishing Award, Okawa Information and Communication Foundation, Kunihiko Sadakane, 30/10/19.

D Mitani Business Contest, Mitani Sangyo Co., Ltd., Shinichi Yamagiwa, 13/12/19.

M Student Encouragement Award, IPSJ, Tomu Katsumata and Muneki Yasuda, 05/03/20.

Conferences

Invited talks

A Kenjiro Takazawa, “b-branchings: Branchings with High Indegree”, The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2019), Tokyo, Japan, 30/05/19.

A Michael Williamson, “Validating NMR protein structures using structural rigidity theory”, Invited seminar at PDBe EBI-EMBL Wellcome Sanger Institute, Cambridge, UK, 12/06/19.

A Adnan Sljoka, “Lifting the curtain: probing biological secrets at molecular level with rigidity theory and algorithms”, 2nd International Conference on Applications of Mathematics to Nonlinear Sciences, Pokhara, Nepal, 27/06/19.

A Hiro Ito, “Sublinear-Time Paradigm — How to Challenge Big Data (Keynote Speech)”, The 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), Xiamen, China, 13/12/19.

D Katsutoshi Yada, “Sensor Marketing and Data Mining”, 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Budapest, Hungary, 05/09/19.

D Shin-ichi Nakano, “Dispersion Problems”, 2nd International Conference on Innovation in Engineering and Technology (ICIET-19), Dhaka, Bangladesh, 23/12/19.

M Shun Kataoka, “Neural network and its variants”, The 34th International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2019), Jeju, Korea, 23/06/19.

M Muneki Yasuda, “Empirical Bayes method for Boltzmann machines”, Workshop on Statistical Physics of Disordered Systems and Its Applications (SPDSA2019), Miyagi, 27/10/19.

Oral presentations

A Y. Asahiro, G. Lin, Z. Liu and E. Miyano, “On the Approximability of the Maximum Induced Matching Problem on Regular Graphs”, The 12th Annual Meeting of the Asian Association for Algorithms and Computation, Seoul, South Korea, 19/04/19.

A Y. Higashikawa, “An Improved Algorithm for Minsum k-Sink Problems on Dynamic Flow Path Networks”, The 30th European Conference on Operational Research (EURO 2019), Dublin, Ireland, 24/06/19.

A J. Kawahara, T. Saitoh, H. Suzuki and R. Yoshinaka, “Colorful Frontier-based Search: Implicit Enumeration of Chordal and Interval Subgraphs”, Special Event on Analysis of Experimental Algorithms, Kalamata, Greece, 24/06/19.

A K. Higashizono and H. Ito, “Hyperfiniteness of hierarchical models for complex networks”, The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2019), Tokyo, Japan, 08/09/19.

A H. Ito, C. Nara, I. Shirahama and M. Tomura, “Strip flat folding with parallel oblique or orthogonal zigzag mountain-valley-assigned creases”, The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2019), Tokyo, Japan, 08/09/19.

A A. Sljoka, “Rigidity of graphs for structural protein validation and functional design”, The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, 30/10/19.

A H. Ito, “Constant-time algorithms on complex networks”, The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, 30/10/19.

A K. Chiba and H. Ito, “Sublinear progressive algoriothms — The frame work and fundamental theorems”, The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, 30/10/19.

A D M T. Horiyama, S. Nakano, T. Saitoh, K. Suetsugu, A. Suzuki, R. Uehara, T. Uno and K. Wasa, “Max-Min 3-dispersion Problems”, The 25th International Computing and Combinatorics Conference (COCOON 2019), Xian, China, 29/07/19.

D S. Chakraborty, “Succinct Data Structures for Families of Interval Graphs”, 17th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, Enschede, The Netherlands, 01/07/19.

D G. Hu, S. Nakano, R. Uehara and T. Uno, “Simple Fold and Cut Problem for Line Segments”, The 31st Canadian Conference in Computational Geometry, Edmonton, Alberta, Canada, 08/08/19.

D K. Ishibashi and K. Yada, “Analysis of social influence on in-store purchase behavior by using ecological system of ants”, 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Budapest, Hungary, 05/09/19.

D K. Yada and H. Gu, “The impact of self-control on search behavior”, 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Budapest, Hungary, 05/09/19.

D K. Ishibashi, “Application of Deep Learning to Pre-processing of Cousumer’s Eye Tracking Data in Supermarket”, 2019 International Conference on Data Mining Workshops, Beijing, China, 08/11/19.

D K. Ishibashi, C. Xiao and K. Yada, “Study of the Effects of Visual Complexity and Consumer Experience on Visual Attention and Purchase Behavior through the Use of Eye Tracking”, 2019 IEEE International Conference on Big Data, Los Angels, USA, 09/12/19.

M A. Shioura, “M-convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Re-allocation in Bike Sharing System”, 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, 28/05/19.

M A. Shioura, “Connection Between Discrete Convex Analysis and Auction Theory”, SIAM Conference on Applied Algebraic Geometry, Bern, Switzerland, 09/07/19.

M A. Suzuki, “Diameter of colorings under Kempe changes”, The 25th International Computing and Combinatorics Conference (COCOON 2019), Xian, China, 30/07/19.

M T. Ito, “Shortest Reconfiguration of Perfect Matchings via Alternating Cycles”, The 27th Annual European Symposium on Algorithms (ESA 2019), Munich, Germany, 09/09/19.

M M.J. Miyama and A.S. Koshikawa, “No Chain Embedding on Quantum Annealer and its Perspective”, D-Wave Qubits North America Users Conference 2019, Newport, USA, 26/09/19.

M S. Arai, “Statistical mechanical analysis of reverse annealing for code-division multiple-access multiuser demodulator”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2019) Statistical-Mechanical Informatics and Statistical Machine Learning Theory in Big Data Sciences, Miyagi, Japan, 27/10/19.

M A.S. Koshikawa, “Search for the ground state of a spin glass with Bayesian optimization”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2019) Statistical-Mechanical Informatics and Statistical Machine Learning Theory in Big Data Sciences, Miyagi, Japan, 27/10/19.

Poster presentations

A N. Fowler, A. Sljoka and M. Williamson, “Validation of NMR protein structures using structural rigidity theory and random coil index”, The 18th European Conference on Computational Biology, Basel, Switzerland, 22/07/19.

A A. Sljoka, “Detection of Allosteric Pathways and Hotspots with Rigidity Propagation across GPCR networks”, GPCR Workshop, Hawaii, USA, 01/12/19.

A M. Williamson, “Is your NMR protein structure accurate? We have the ANSURR!”, Reson8 5th Biophysical and biochemical symposium, York, USA, 10/01/20.

A M. Huai, D. Wang, C. Miao, J. Xu and A. Zhang, “Pairwise Learning with Differ- ential Privacy Guarantees”, AAAI2020, New York, USA, 09/02/20.

D S. Yamagiwa, R. Morita and K. Marumo, “Reducing Symbol Search Overhead on Stream-based Lossless Data Compression”, ICCS 2019, Faro, Portugal, 13/06/19.

D Y.Z. Zhang, A. Akdemir, G. Tremmel, S. Imoto, S. Miyano, T. Shibuya and R. Yamaguchi, “Nanopore base-calling from a perspective of instance segmentation”, The 18th European Conference on Computational Biology, Basel, Switzerland, 21/07/19.

D S. Yamagiwa, E. Hayakawa and K. Marumo, “Adaptive Stream-based Entropy Coding”, Data Compression Conference 2020, Snowbird, Utah, USA, 24/03/20.

M M. Okuyama and M. Ohzeki, “An exact solution of the partition function for mean-field quantum spin systems without the static approximation”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M S. Arai, M. Ohzeki and K. Tanaka, “Mean-field analysis of quantum error-correcting codes with non-stoquastic Hamiltonian”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M C. Takahashi, M. Ohzeki and K. Tanaka, “Statistical-mechanical analysis of restrictecd Boltzmann machine with transverse field”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 226/06/19.

M A. Koshikawa, M. Ohzeki and K. Tanaka, “Black-box optimization with D-Wave 2000Q”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M N. Maruyama, M. Ohzeki and K. Tanaka, “Optimization of bus schedule using quantum annealer”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M H. Naganuma, D. Hendrian, R. Yoshinaka, A. Shinohara and N. Kobayashi, “Grammar Compression with Probabilistic Context-Free Grammar”, Data Compression Conference 2020, Snowbird, Utah, USA, 24/03/20.

Journal papers

A H.L. Bodlaender, T. Hanaka, Y. Okamoto, Y. Otachi and T.C. van der Zanden, “Subgraph Isomorphism on Graph Classes that Exclude a Substructure”, Proceedings of 11th International Conference on Algorithms and Complexity (CIAC 2019), pp.87-98, 2019 (DOI: 10.1007/978-3-030-17402-6_8)

A Y. Asahiro, J. Jansson, E. Miyano, H. Ono and T.P. Sandhya, “Graph orientation with edge modifications”, Proceedings of FAW 2019, Vol.11458, pp.38-50, 2019 (DOI: 10.1007/978-3-030-18126-0_4)

A Y. Asahiro, T. Kubo and E. Miyano, “Experimental evaluation of approximation and heuristic algorithms for maximum distance-bounded subgraph problems”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.143-161, 2019 (DOI: 10.1007/s12626-019-00036-2)

A R. Yamamoto and A. Takizawa, “Partitioning Vertical Evacuation Areas in Umeda Underground Mall to Minimize the Evacuation Completion Time”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.209-225, 2019 (DOI: 10.1007/s12626-019-00037-0)

A E. Boros, K.M. Elbassioni, V. Gurvich and K. Makino, “A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions,” Inf. Comput. No.267, pp.74-95, 2019 (DOI: 10.1016/j.ic.2019.03.005)

A E. Boros, V. Gurvich, N.B. Ho, K. Makino and P. Mursic, “Sprague-Grundy function of symmetric hypergraphs,” Journal of Combinatorial Theory, Series A, No.165, pp.176-186, 2019 (DOI: 10.1016/j.jcta.2019.02.006)

A K. Takazawa and Y. Yokoi, “A generalized-polymatroid approach to disjoint common independent sets in two matroids”, Discrete Mathematics, Vol.342, issue 7, pp.2002-2011, 2019 (DOI: 10.1016/j.disc.2019.03.009)

A D. Wang, C. Chen and J. Xu, “Differentially Private Empirical Risk Minimization with Non-convex Loss Functions”, Proc. the 36th International Conference on Machine Learning (ICML 2019), pp.6326-6535, 2019.

A P. Mehrabi, C.D. Pietrantonio, T.H. Kim, A. Sljoka, K. Taverner, C. Ing, N. Kruglyak, R. Pomès, E.F. Pai and R.S. Prosser, “Substrate-Based Allosteric Regulation of a Homodimeric Enzyme”, J. Am. Chem. Soc., Vol.141, No.29, 11540-11556, 2019 (DOI: 10.1021/jacs.9b03703)

A Y. Kobayashi, Y. Kobayashi, S. Miyazaki and S. Tamaki, “An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number”, IWOCA 2019, Lecture Notes in Computer Science, Vol.11638, pp.327-338, 2019 (DOI: 10.1007/978-3-030-25005-8)

A Y. Kawase, X. Han and K. Makino, “Proportional cost buyback problem with weight bounds”, Theoretical Computer Science, No.774, pp.51-64, 2019 (DOI: 10.1016/j.tcs.2016.06.005)

A H. Hayakawa, T. Ishii, H. Ono and Y. Uno, “Settlement fund circulation problem”, Discrete Applied Mathematics, Vol.265, pp.86-103, 2019 (DOI: 10.1016/j.dam.2019.03.017)

A E.D. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara and Y. Uno, “Reconfiguring Undirected Paths”, Lecture Notes in Computer Science, Vol.11646, pp.353-365, 2019 (DOI: 10.1007/978-3-030-24766-9_26)

A Y. Kawase, X. Han and K. Makino, “Unit Cost Buyback Problem,” Theory Comput. Syst. Vol.63, No.6, pp.1185-1206, 2019 (DOI: 10.1007/s00224-018-9897-7)

A D. Wang and J. Xu, “Principal Component Analysis in the Local Differential Privacy Model”, Proc. 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp.4795-4801, 2019 (DOI: 10.24963/ijcai.2019/66)

A Y. Asahiro, G. Lin, Z. Liu and E. Miyano, “An approximation algorithm for the maximum induced matching problem on C_5-free regular grapha”, IEICE TRANSACTIONS on Information and Systems, Vol.E102-A, No.9, pp.1142-1149, 2019 (DOI: 10.1587/transfun.E102.A.1142)

A H. Ito, A. Nagao and T. Park, “Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 102, No.9, pp.1126-1133, 2019 (DOI: 10.1587/transfun.E102.A.1126)

A Y. Higashikawa and N. Katoh, “A Survey on Facility Location Problems in Dynamic Flow Networks”, The Review of Socionetwork Strategies, Vol.13, pp.163-208, 2019 (DOI: 10.1007/s12626-019-00047-z)

A Y. Honda, Y. Inoue, H. Ito, M. Sasajima, J. Teruyama and Y. Uno, “Hyperfiniteness of Real-world Networks”, The Review of Socionetwork Strategies, Vol.13, pp.123-141, 2019 (DOI: 10.1007/s12626-019-00051-3)

A K. Elbassioni and K. Makino, “Oracle-based Primal-dual Algorithms for Packing and Covering Semidefinite Programs”, The 27th Annual European Symposium on Algorithms (ESA 2019), 2019 (DOI: 10.4230/LIPIcs.ESA.2019.43)

A E. Demaine, H. Ito, S. Langerman, J. Lynch, M. Rudoy and K. Xiao, “Cookie Clicker”, Graphs and Combinatorics, Vol.36, pp.269-302, 2020 (DOI: 10.1007/s00373-019-02093-4)

A H. Ito, “What graph properties are constant-time testable? -Dense graphs, sparse graphs, and complex networks”, The Review of Socionetwork Strategies, Vol.13, pp.101-121, 2019 (DOI: 10.1007/s12626-019-00054-0)

A X. Han, Q. Chen and K. Makino, “Online knapsack problem under concave functions”, Theoretical Computer Science Vol.786, pp.88-95, 2019 (DOI: 10.1016/j.tcs.2018.03.025)

A D. Wang and J. Xu, “Faster constrained linear regression via two-step preconditioning”, Neurocomputing, Vol.364, pp.280-296, 2019 (DOI: 10.1016/j.neucom.2019.07.070 )

A T. Sakai, K. Seto, S. Tamaki and J. Teruyama,“Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression”, J. Comput. Syst. Sci., Vol.105, pp.87-103, 2019 (DOI: 10.1016/j.jcss.2019.04.004)

A Y. Asahiro, J. Jansson, G. Lin, E. Miyano, H. Ono and T. Utashima, “Exact algorithms for the bounded repetition longest common subsequence problem”, Proc. 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), LNCS11949, pp.1-12, 2019 (DOI: 10.1007/978-3-030-36412-0_1)

A X. Han, Y. Kawase, K. Makino and H. Yokomaku, “Online Knapsack Problems with a Resource Buffer”, ISAAC 2019: 28:1-28:14 2019 (DOI: 10.4230/LIPIcs.ISAAC.2019.28)

A O. Aichholzer, M. Korman, Y. Okamoto, I. Parada, D. Perz, A.van Renssen and B. Vogtenhuber, “Graphs with Large Total Angular Resolution”, Proceedings of 27th International Symposium on Graph Drawing and Network Visualization，pp.193-199, 2019 (DOI: 10.1007/978-3-030-35802-0_15)

A Y. Okamoto, A. Ravsky and A. Wolff, “Variants of the Segment Number of a Graph”, Proceedings of 27th International Symposium on Graph Drawing and Network Visualization, pp.430-443, 2019 (DOI: 10.1007/978-3-030-35802-0_33)

A Z. Huang, Q. Feng, J. Wang and J. Xu, “Small Candidate Set for Translational Pattern Search”, Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), pp.16:1-26:17, 2019 (DOI: 10.4230/LIPIcs.ISAAC.2019.26)

A E. Boros, V. Gurvich, N.B. Ho, K. Makino and P. Mursic, “Sprague-Grundy function of matroids and related hypergraphs”, Theor. Comput. Sci., Vol.799, pp.40-58, 2019 (DOI: 10.1016/j.tcs.2019.09.041)

A P. Carmi, M.K. Chiu, M.J. Katz, M. Korman, Y. Okamoto, A.van Renssen, M. Roeloffzen, T. Shiitada and S. Smorodinsky, “Balanced line separators of unit disk graphs”, Computational Geometry: Theory and Applications, Vol.86, 2019 (DOI: 10.1016/j.comgeo.2019.101575)

A H. Ito, A. Khoury and I. Newman, “On the characterization of 1-sided error strongly-testable graph properties for bounded-degree graphs”, Journal of Computational Complexity, Vol.29, No.1, pp.1-45, 2020 (DOI: 10.1007/s00037-020-00191-6)

A K. Yamazaki, T. Saitoh, M. Kiyomi and R. Uehara, “Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs”, Theoretical Computer Science, Vol.806, pp.310-322, 2020 (DOI: 10.1016/j.tcs.2019.04.017)

A K. Iwama and J. Teruyama, “Improved Average Complexity for Comparison-based Sorting”, Theoretical Computer Science, Vol.807, pp.201-219, 2019 (DOI: 10.1016/j.tcs.2019.06.032)

A B. Soumen, A. Sljoka and C. Amit, “Allosteric regulation of Glutamate dehydrogenase deamination activity”, Scientific Reports, 2020 (DOI: 10.1016/j.bpj.2019.11.2851)

A Y. Asahiro, H. Eto, T. Hanaka, G. Lin, E. Miyano and I. Terabaru, “Parameterized algorithms for the happy set problem”, Proc. 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), LNCS12049, pp.323-328, 2020 (DOI: 10.1007/978-3-030-39881-1_27)

A Y. Kawase and K. Makino, “Surrogate optimization for p-norms”, Discret. Optim. 34, 2019 (DOI: 10.1016/j.disopt.2019.05.003)

A R. Mubasher, B. Soumen, A. Sljoka and A. Chakraborty, “Feedforward Control of Plant Nitrate Transporter NRT1.1Biphasic Adaptive Activity”, Biophysical Journal, Vol.118, No.4, pp.898-908, 2019 (DOI: 10.1016/j.bpj.2019.10.018)

A Z. Huang and J. Xu, “An Efficient Sum Query Algorithm for Distance-Based Locally Dominating Functions”, Algorithmica, 2020 (DOI: 10.1007/s00453-020-00691-w)

A R. Benkoczi, B. Bhattacharya, Y. Higashikawa, T. Kameda and N. Katoh, “Minsum k-sink problem on path networks”, Theor. Comput. Sci. 806: 388-401, 2020 (DOI: 10.1016/j.tcs.2019.05.047)

A D. Wang and J. Xu, “Tight Lower Bound of Sparse Covariance Matrix Estimation in the Local Differential Privacy Model”, Theoretical Computer Science, Vol.815, pp.47-59, 2020 (accepted) (DOI: 10.1016/j.tcs.2020.02.02)

A H. Ding and J. Xu, “Learning the Truth Vector in High Dimensions”, Journal of Computer and System Sciences, 109:78-94, 2020 (accepted) (DOI: 10.1016/j.jcss.2019.12.002)

A X. Wang, A. Mafi, A. Sljoka, W.A. Goddard and Y. Libin, “Conformational Insights into Signaling Mechanism of Partial Agonism in GPCRs”, Cell (submitted)

A D M T. Horiyama, S. Nakano, T. Saitoh, K. Suetsugu, A. Suzuki, R. Uehara, T. Uno and K. Wasa, “Max-Min 3-dispersion Problems”, Proc. of COCOON 2019, LNCS 11653, pp.291-300, 2019 (DOI: 10.1007/978-3-030-26176-4_24)

A M T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Shortest Reconfiguration of Perfect Matchings via Alternating Cycles,” Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics, Vol.144, pp.61:1-61:15, 2019 (DOI: 10.4230/LIPIcs.ESA.2019.61)

A M J. Kawahara, T. Saitoh, H. Suzuki and R. Yoshinaka, “Colorful Frontier-based Search: Implicit Enumeration of Chordal and Interval Subgraphs,” Special Event on Analysis of Experimental Algorithms, LNCS, Vol.11544, pp.125-141, 2019 (DOI: 10.1007/978-3-030-34029-2_9)

D T. Jordan and S. Tanigawa, “Global rigidity of triangulations with braces”, Journal of Combinatorial Theory, Series B, No.136, pp.249-288, 2019 (DOI: 10.1016/j.jctb.2018.11.003)

D H. Furuta, K. Ishibashi and K. Nakatsu, “Resilient restoration scheduling on road network,” Proceedings of 13th International Conference on Applications of Statistics and Probability in Civil Engineering(ICASP13), pp.1–8, 2019 (DOI: 10.22725/ICASP13.141)

D S. Yamagiwa, R. Morita and K. Marumo, “Reducing Symbol Search Overhead on Stream-based Lossless Data Compression”, Proceedings of ICCS 2019, LNCS 11540, pp.619-626, 2019 (DOI: 10.1007/978-3-030-22750-0_59)

D S. Chakraborty, A. Mukherjee and S.R. Satti, “Space Efficient Algorithms for Breadth-Depth Search”, Fundamentals of Computation Theory – 22nd International Symposium (FCT 2019), pp.201-212, 2019 (DOI: 10.1007/978-3-030-25027-0_14)

D H. Acan, S. Chakraborty, S. Jo and S.R. Satti, “Succinct Data Structures for Families of Interval Graphs”, Workshop on Algorithms and Data Structures (WADS 2019), pp.1-13, 2019 (DOI: 10.1007/978-3-030-24766-9_1)

D S. Denzumi, “New Algorithms for Manipulating Sequence BDDs”, The 24th International Conference on Implementation and Application of Automata (CIAA 2019), pp.108-120, 2019 (DOI: 10.1007/978-3-030-23679-3_9)

D S. Ahmed, S. Nakano and Md.S. Rahman, “One-dimensional r-Gathering under Uncertainty”, Proc. of AAIM 2019, LNCS 11640, pp.1-15, 2019 (DOI: 10.1007/978-3-030-27195-4_1)

D I. Furuya and T. Kida, “Compaction of Church Numerals”, Algorithms, Vol.12, No.8:159, 2019 (DOI: 10.3390/a12080159)

D A. Akdemir and T. Gungor, “A Detailed Analysis and Improvement of Feature-Based Named Entity Recognition for Turkish”, SPECOM 2019, LNAI 11658, pp.9–19, 2019 (DOI: 10.1007/978-3-030-26061-3_2)

D S. Chakraborty and K. Sadakane, “Indexing Graph Search Trees and Applications”, Proceedings of MFCS, LIPIcs 138, pp.67:1-67:14, 2019 (DOI: 10.4230/LIPIcs.MFCS.2019.67)

D K. Yamanaka, Y. Matsui and S. Nakano, “Enumerating Highly-Edge-Connected Spanning Subgraphs”, IEICE TRANS. FUNDAMENTALS, Vol.E102-A, No.9, pp.1002-1006, 2019 (DOI: 10.1587/transfun.E102.A.1002)

D Y. Sasaki, T. Shibuya, K. Ito and H. Arimura, “Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score”, IEICE Transactions on Fundamentals, E102.A(9), pp.1159-1170, 2019 (DOI: 10.1587/transfun.E102.A.986)

D M.J. Kashyop, T. Nagayama and K. Sadakane, “Faster algorithms for shortest path and network flow based on graph decomposition”, Journal of Graph Algorithms and Applications, Vol.23, No.5, pp.781-813, 2019 (DOI: 10.7155/jgaa.00512)

D S. Nakano, “A Simple Algorithm for r-gatherings on the Line”, JGAA, Vol.23, No.5, pp.837-845, 2019 (DOI: 10.7155/jgaa.00514)

D T. Gagie, T. I, G. Manzini, G. Navarro, H. Sakamoto and Y. Takabatake, “Rpair: Rescaling RePair with Rsync”, SPIRE 2019, pp.35-44, 2019 (DOI: 10.1007/978-3-030-32686-9_3)

D T. Shibuya, “Application-Oriented Succinct Data Structures for Big Data”, The Review of Socionetwork Strategies, Vol.13, pp.227–236, 2019 (DOI: 10.1007/s12626-019-00045-1)

D K. Sumigawa and K. Sadakane, “Storing Partitions of Integers in Sublinear Space”, The Review of Socionetwork Strategies, Vol.13, pp.237–252, 2019 (DOI: 10.1007/s12626-019-00044-2)

D K. Ishibashi and K. Yada, “Analysis of social influence on in-store purchase behavior by using ecological system of ants”, Procedia Computer Science, Vol.159, pp.2162-2171, 2019 (DOI: 10.1016/j.procs.2019.09.390)

D K. Ishibashi, “Application of Deep Learning to Pre-processing of Cousumer’s Eye Tracking Data in Supermarket”, Proceedings of 2019 International Conference on Data Mining Workshops (ICDMW), pp.341-348, 2019 (DOI: 10.1109/ICDMW.2019.00057)

D K. Ishibashi, C. Xiao and K. Yada, “Study of the Effects of Visual Complexity and Consumer Experience on Visual Attention and Purchase Behavior through the Use of Eye Tracking”, Proceedings of 2019 IEEE International Conference on Big Data (Big Data), pp.2664-2673, 2019 (DOI: 10.1109/BigData47090.2019.9005498)

D T. Araki and S. Nakano, “Max-Min Dispersion on a Line”, Journal of Combinatorial Optimization, 2020 (DOI: 10.1007/s10878-020-00549-5)

D K. Amano and S. Nakano, “An Approximation Algorithm for the 2-dispersion Problem”, IEICE TRANS. INF.& SYST., Vol.E103-D, No.3, pp.506-508, 2020 (DOI: 10.1587/transinf.2019FCP0005)

D Y. Yoshimoto, M. Kataoka, Y. Takabatake, T. I, K. Shin and H. Sakamoto, “Faster Privacy-Preserving Computation of Edit Distance with Moves”, WALCOM 2020, pp.308-320, 2020 (DOI: 10.1007/978-3-030-39881-1_26)

D S. Chakraborty and K. Sadakane, “Indexing Graph Search Trees and Applications”, Proceedings of MFCS, 2019 (in press)

D I. Furuya, “Practical Repetition-Aware Grammar Compression”, In Proceedings of Data Compression Conference, 2020 (in press)

M M. Yasuda, H. Sakata, S.I. Cho, T. Harada, A. Tanaka and M. Yokoyama, “An efficient test method for noise robustness of deep neural networks”, Nonlinear Theory and its Applications (NOLTA), IEICE, Vol.10, Issue 2, pp.221-235, 2019 (DOI: 10.1587/nolta.10.221)

M T. Ito, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Algorithms for Gerrymandering Over Graphs”, Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), pp.1413-1421, 2019 (DOI: 10.5555/3306127.3331851)

M T. Ito and Y. Otachi, “Reconfiguration of Colorable Sets in Classes of Perfect Graphs”, Theoretical Computer Science, Vol.772, pp.111-122, 2019 (DOI: 10.1016/j.tcs.2018.11.024)

M S. Kataoka and M. Yasuda, “Bayesian Image Denoising with Multiple Noisy Images”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.267-280, 2019 (DOI: 10.1007/s12626-019-00043-3)

M M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki and K. Wasa, “Diameter of colorings under Kempe changes”, Proceedings of COCOON 2019, Vol.11653, pp.52-64, 2019 (DOI: 10.1007/978-3-030-26176-4_5)

M T. Ito, H. Mizuta, N. Nishimura and A. Suzuki, “Incremental optimization of independent sets under the reconfiguration framework”, Proceedings of COCOON 2019, Vol.11653, pp.313-324, 2019 (DOI: 10.1007/978-3-030-26176-4_26)

M Y. Yokoyama, T. Katsumata and M. Yasuda, “Restricted Boltzmann Machine with Multivalued Hidden Variables: a model suppressing over-fitting”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.253-266, 2019 (DOI: 10.1007/s12626-019-00042-4)

M N. Minamikawa and A. Shioura, “Separable convex resource allocation problem with L1-distance constraint”, Journal of Operations Research Society of Japan, Vol.62, pp.109-120, 2019 (DOI: 10.15807/jorsj.62.109)

M S. Kobayashi, D. Hendrian, R. Yoshinaka and A. Shinohara, “An improvement of the Franek-Jennings-Smyth pattern matching algorithm”, Proceedings of Prague Stringology Conference 2019, pp.56-68, 2019.

M M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Mühlenthaler and K. Wasa, “The Perfect Matching Reconfiguration Problem”, Proceedings of MFCS 2019, Vol.138, pp.80:1-80:14, 2019 (DOI: 10.4230/LIPIcs.MFCS.2019.80)

M H. Mizuta, T. Hatanaka, T. Ito and X. Zhou, “Reconfiguration of Minimum Steiner Trees via Vertex Exchanges”, Proceedings of MFCS 2019, Vol.138, pp.79:1-79:11, 2019 (DOI: 10.4230/LIPIcs.MFCS.2019.79)

M K. Chubachi, D. Hendrian, R. Yoshinaka and A. Shinohara, “Query Learning Algorithm for Residual Symbolic Finite Automata”, In Proceedings of the Tenth International Symposium on Games, Automata, Logics, and Formal Verification, 2019.

M M. Yasuda, K. Katou, Y. Mikuni, Y. Yokoyama, T. Harada, A. Tanaka and M. Yokoyama, “Detection of human-interaction network using Markov random field”, Nonlinear Theory and its Applications (NOLTA), IEICE, Vol.10, Issue 4, pp.485-495, 2019 (DOI: 10.1587/nolta.10.485)

M M. Tsuchiya, A. Tanaka, M. Yasuda, T. Harada, S. Cho and M. Yokoyama, “Estimation of Sleep Onset and Awaking Time Using a Deep Neural Network with Physiological Data during Sleep”, Nonlinear Theory and its Applications (NOLTA), IEICE, Vol.10, Issue 4, pp.366-372, 2019 (DOI: 10.1587/nolta.10.366)

M M. Yasuda and S. Ueno, “Improvement of Batch Normalization in Imbalanced Data”, Proceedings of the 2019 International Symposium on Nonlinear Theory and its Applications (NOLTA2019), pp.146-149, 2019.

M S. Cho, M. Tsuchiya, A. Tanaka, M. Yasuda, T. Harada and M. Yokoyama, “A Study on the Relation Between the Estimated Sleep Satisfaction Levels Using Multiple Regression Analysis and Autonomic Nervous System”, Proceedings of the 2019 International Symposium on Nonlinear Theory and its Applications (NOLTA2019), pp.153-156, 2019.

M A. Tanaka, S. Nagasawa, M. Yasuda, T. Harada and M. Yokoyama, “Overcoming Chasm Phenomena in Diffusion on Cookpad Community”, Proceedings of the 2019 International Symposium on Nonlinear Theory and its Applications (NOLTA2019), pp.150-152, 2019.

M M. Yasuda and T. Obuchi, “Empirical Bayes Method for Boltzmann Machines”, Journal of Physics A: Mathematical and Theoretical, Vol.53, No.1, 2019 (DOI: 10.1088/1751-8121/ab57a7)

M K. Nakashima, D. Hendrian, R. Yoshinaka and A. Shinohara, “An Extension of Linear-size Suffix Tries for Parameterized Strings”, SOFSEM (Doctoral Student Research Forum) 2020: 97-108, 2020.

M D. Jargalsaikhan, D. Hendrian, R. Yoshinaka and A. Shinohara, “Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching,” SOFSEM 2020, pp.211-222, 2020.

M T. Hanaka, T. Ito, H. Mizuta, B. Moore, N. Nishimura, V. Subramanya, A. Suzuki and K. Vaidyanathan, “Reconfiguring Spanning and Induced Subgraphs,” Theoretical Computer Science, Vol.806, pp.553-566, 2020 (DOI: 10.1016/j.tcs.2019.09.018)

M Y. Tamura, T. Ito and X. Zhou, “Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs,” Proceedings of the 14th International Conference and Workshop on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science, Vol.12049, pp.286-295, 2020 (DOI: 10.1007/978-3-030-39881-1_24)

M K. Kimura and A. Suzuki, “Trichotomy for the reconfiguration problem of integer linear systems,” Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science, Vol.12049, pp.336-341, 2020 (DOI: 10.1007/978-3-030-39881-1_29)

M D.A. Hoang, A. Suzuki and T. Yagita, “Reconfiguring k-path vertex covers,” Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science, Vol.12049, pp.133-145, 2020 (DOI: 10.1007/978-3-030-39881-1_12)

M M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki and K. Wasa, “Shortest Reconfiguration of Colorings Under Kempe Changes,” Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Leibniz International Proceedings in Informatics, Vol.154, pp.35:1-35:14, 2020 (DOI: 10.4230/LIPIcs.STACS.2020.35)

M S. Narisada, D. Hendrian, R. Yoshinaka and A. Shinohara, “Linear-time online algorithm for inferring the shortest path graph from a walk label”, Theor. Comput. Sci., Vol.812, pp.187-202, 2020 (in press) (DOI: 10.1016/j.tcs.2019.10.029)

M A. Blanché, P. Ouvrard, H. Mizuta and A. Suzuki, “Decremental optimization of dominating sets under the reconfiguration framework”, Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), to appear (accepted)

M M. Okuyama and M. Ohzeki, “Inequality for local energy of Ising models with quenched randomness and its application”, arXiv::2001.10707 (submitted)
A Best Paper Award, International Conference on Artificial Intelligence and Statistics (AISTATS), Yuichi Yoshida, 01/04/18.

D University-initiated venture commendation 2018 Japan Science and Technology Promotion Organization President’s Award, Shinichi Yamagiwa and Hiroshi Sakamoto, “Project on Compression Communication (Stream Technology Inc.)”, 30/08/18.

M Student Paper Award, 2018 International Symposium on Nonlinear Theory and its Applications, Minami Tsuchiya et. al., 06/09/18.

Conferences

Invited talks

A Naoki Katoh, “Concept and Challenge of Faculty of Social Information Science, University of Hyogo”, International Conference on Education of Data Science in Hikone 2018 (HDS2018), Shiga, Japan, 15/11/18.

A Adnan Sljoka, “Rigidity theory and its applications to protein function analysis”, Workshop of CREST Big Data Applications, Kyoto, Japan, 24/01/19.

D Kunihiko Sadakane, “Renge minimum Queries and Applications”, IWOCA 2018: 29th International Workshop on Combinational Algorithms, Singapore, 17/07/17.

Oral presentations

A Y. Okamoto, “Submodular reassignment problem for reallocating agents to tasks with synergy effects”, 11th Combinatorial Algorithms Day, ETH Zurich, 04/06/18.

A Y. Okamoto, “Submodular reassignment problem for reallocating agents to tasks with synergy effects”, First Conference on Discrete Optimization and Machine Learning, Tokyo, Japan, 23/07/18.

A Y. Kobayashi, “Generation Methods of Panel-Hinge Frameworks Based on Regular Skew Polyhedra”, Bridges 2018 : Mathematics, Music, Art, Architecture, Culture, Stockholm, Sweden, 27/07/18.

A K. Takazawa, “The b-branching problem in digraphs”, The 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK, 27/08/18.

A Y. Kobayashi, “Periodic Sponge Surfaces and Their Rigidity”, The 21th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2018), Metro Manila, Philippines, 01/09/18.

A A. Nagao and M. Yokota, “PSPACE-completeness for Snakebird”, The 21th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, (JCDCGGG 2018), Metro Manila, Philippines, 02/09/18.

A N. Tsuchimura, “Distributed Computation for Protein Structure Analysis”, The 10th International Conference on Intelligent Networking and Collaborative Systems (INCoS-2018), Bratislava, Slovakia, 05/09/18.

A Y. Higashikawa, “Characterizing minimally rigid body-bar graphs without proper rigid subgraphs”, Operations Research 2018, The annual international conference of the German Operations Research Society (GOR), Brussels, Belgium, 13/09/18.

A X. Bultel, J. Dreier, J. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, A. Nagao, T. Sasaki, K. Shinagawa and H. Sone, “Physical Zero-Knowledge Proof for Makaro”, 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), Tokyo, Japan, 05/11/18.

A S. Tamaki, “Beating Brute Force for Systems of Polynomial Equations over Finite Fields”, MPI-INF and MPI-MiS joint workshop on Theoretical Computer Science and Algebraic Geometry, Saarbrücken, Germany, 18/01/19.

D K. Amano and S. Nakano, “Away from Rivals”, 30th Canadian Conference on Computational Geometry, CCCG 2018, Winnipeg, Canada, 08/08/18.

D M. Ikeda, “Cut Sparsifiers for Balanced Digraphs”, 16th International Workshop on Approximation and Online Algorithms (WAOA2018), Helsinki, Finland, 24/08/18.

D K. Ishibashi and K. Yada, “Assessment of Effect of POP on Purchase Behavior: Comparison of Effectiveness of Eyetracking Data and Shopping Path Data”, 5th Asia-Pacific World Congress on Computer Science and Engineering (APWC on CSE 2018), Momi Bay, Fiji, 12/12/18.

M S. Arai, M. Ohzeki and K. Tanaka, “Deep Neural Network detects quantum phase transition in D-Wave 2000Q”, Adiabatic Quantum Computing Conference 2018, Moffett field, CA, 28/06/18.

M A. Shioura, “M-convex Function Minimization Under L1-distance Constraint”, 23rd International Symposium on Mathematical Programming, Bordeaux, France, 04/07/18.

M C. Takahashi, M. Yasuda and K. Tanaka, “Learning restricted Boltzmann machine via the adaptive Thouless-Anderson-Palmer mean-field approximation”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2018), Miyagi, Japan, 07/11/18.

M M. Okuyama and M. Ohzeki, “Optimal control theory solves mean-field quantum spin systems”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2018), Miyagi, Japan, 07/11/18.

M S. Arai, M. Ohzeki and K. Tanaka, “Dynamics of order parameters of non-stoquastic Hamiltonian in adaptive quantum Monte Carlo method”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2018), Miyagi, Japan, 07/11/18.

Poster presentations

D S. Yamagiwa, R. Morita and K. Marumo, “Bank Select Method for Reducing Symbol Search Operations on Stream-based Lossless Data Compression”, Data Compression Conference 2019, Snowbird, UT, 28/03/19.

M S. Arai, S. Okada, M. Ohzeki and K. Tanaka, “Acceleration of adaptive quantum Monte Carlo Sampling for a class of non-stoquastic Hamiltonian by using D-Wave 2000Q”, Adiabatic Quantum Computing Conference 2018 (AQC-18), Moffett field, CA, 25/06/18.

M C. Takahashi, M. Ohzeki, S. Okada, M. Terabe, S. Taguchi and K. Tanaka, “Statistical Mechanical Analysis of Hamiltonian Estimation of Ising Spin Glass Based on the Framework of Statistical Query Learning”, Adiabatic Quantum Computing Conference 2018 (AQC-18), Moffett field, CA, 26/06/18.

M M. Okuyama and M. Ohzeki, “Classical speed limit applied to imaginary-time Grover problem”, Adiabatic Quantum Computing Conference 2018 (AQC-18), Moffett field, CA, 28/06/18.

M S. Arai, M. Ohzeki and K. Tanaka, “Adaptive quantum Monte Carlo method for a class of non-stoquastic Hamiltonian by using D-Wave machine”, Qubits 2018, Knoxville, USA, 26/09/18.

Journal papers

A K. Kimura and K. Makino, “Linear satisfiability preserving assignments (Extended Abstract)”, IJCAI 2018, pp.5622-5626, 2018 (DOI: 10.24963/ijcai.2018/797)

A A. Kawachi, K. Kawano, F.L. Gall and S. Tamaki, “Quantum Query Complexity of Unitary Operator Discrimination”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E102-D, No. 3, pp.483-491, 2019 (DOI: 10.1587/transinf.2018FCP0012)

A T. Akagi, T. Araki, T. Horiyama, S. Nakano, Y. Okamoto, Y. Otachi, T. Saitoh, R. Uehara, T. Uno and K. Wasa, “Exact Algorithms for the Max-Min Dispersion Problem”, Lecture Notes in Computer Science, Vol. 10823, pp.263-272, 2018 (DOI: 10.1007/978-3-319-78455-7_20)

A A. Golovnev, A.S. Kulikov, A.V. Smal and S.Tamaki, “Gate Elimination: Circuit Size Lower Bounds and #SAT Upper Bounds”, Theoretical Computer Science, Vol.719, pp.46-63, 2018 (DOI: 10.1016/j.tcs.2017.11.008)

A L. Ye, C. Neale, A. Sljoka, B. Lyda, D. Pichugin, N. Tsuchimura, S.T. Larda, R. Pomès, A.E. García, O.P. Ernst, R.K. Sunahara and R.S. Prosser, “Mechanistic insights into allosteric regulation of the A2A adenosine G protein-coupled receptor by physiological cations”, Nature Communication, 1 9:1372, 2018 (DOI: 10.1038/s41467-018-03314-9)

A Y. Asahiro, J. Jansson, E. Miyano, H. Nikpey and H. Ono, “Graph orientation with splits”, ISCO2018, Lecture Notes in Computer Science10856, pp.52-63, 2018 (DOI: 10.1007/978-3-319-96151-4_5)

A E. Boros, V. Gurvich, N.B. Ho, K. Makino and P. Mursic, “On the Sprague-Grundyfunction of Exact k-Nim”, Discrete Applied Mathematics 239, pp.1-14, 2018 (DOI: 10.1016/j.dam.2017.08.007)

A T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Reconfiguration of Maximum-Weight b-Matchings in a Graph”, Journal of Combinatorial Optimization, Vol.37, pp.454-464, 2019 (DOI: 10.1007/s10878-018-0289-3)

A P. Zhang, Y. Xu, T. Jian, A. Li, G. Lin and E. Miyano, “Improved approximation algorithms for the maximum happy vertices and edges problems”, Algorithmica, Vol.80, No.5, pp.1412-1438, 2018 (DOI: 10.1007/s00453-017-0302-8)

A T. Akagi, T. Araki, T. Horiyama, S. Nakano, Y. Okamoto, Y. Otachi, T. Saitoh, R. Uehara, T. Uno and K. Wasa, “Exact Algorithms for the Max-Min Dispersion Problem”, Proc. of FAW 2018, LNCS 10823, pp.263-272, 2018 (DOI: 10.1007/978-3-319-78455-7_20)

A Y. Asahiro, Y. Doi, E. Miyano, K. Samizo and H. Shimizu, “Optimal approximation algorithms for maximum distance-bounded subgraph problems”, Algorithmica, Vol.80, No.6, pp.1834-1856, 2018 (DOI: 10.1007/s00453-017-0344-y)

A K. Yamanaka, T. Horiyama, J.M. Keil, D.G. Kirkpatrick, Y. Otachi, T. Saitoh, R. Uehara and Yushi Uno, “Swapping colored token on graphs”, Theoretical Computer Science, Vol.729, pp.1-10, 2018 (DOI: 10.1016/j.tcs.2018.03.016)

A H. Sumita, N. Kakimura and K. Makino, “Total dual integrality of the linear complementarity problem”, Annals OR, 274, pp.531-553, 2019 (DOI: 10.1007/s10479-018-2926-8)

A T. Ito and Y. Otachi, “Reconfiguration of Colorable Sets in Classes of Perfect Graphs”, Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), LIPIcs 101, pp.27:1-27:13, 2018 (DOI: 10.4230/LIPIcs.SWAT.2018.27)

A K. Elbassioni and K. Makino, “Enumerating vertices of 0/1-polyhedra associated with 0/1-Totally unimodular matrices”, SWAT 2018, pp.18:1-18:14, 2018 (DOI: 10.4230/LIPIcs.SWAT.2018.18)

A S. Li, J. Xu and M. Ye, “Approximating Global Optimum for Probabilistic Truth Discovery”, Proc. 24th International Computing and Combinatorics Conference (COCOON 2018), Vol.10976, 2018 (DOI: 10.1007/978-3-319-94776-1_9)

A R. Benkoczi, B. Bhattacharya, Y. Higashikawa, T. Kameda and N. Katoh, “Minsum k-Sink Problem on Dynamic Flow Path Networks”, Proceedings of IWOCA 2018, pp.78-89, 2018 (DOI: 10.1007/978-3-319-94667-2_7)

A Y. Asahiro, E. Miyano and T. Yagita, “Approximation Algorithms for Packing Directed Acyclic Graphs into Two-Size Blocks”, ICCSA 2018, Lecture Notes in Computer Science, Vol.10961, pp.607-623, 2018 (DOI: 10.1007/978-3-319-95165-2_43)

A Y. Kawase, K. Makino and K. Seimi, “Optimal composition ordering problems for piecewise linear functions”, Algorithmica, 80, pp.2134-2159, 2018 (DOI: 10.1007/s00453-017-0397-y)

A T. Feng, T. Horiyama, Y. Okamoto, Y. Otachi, T. Saitoh, T. Uno and R. Uehara, “Computational Complexity of Robot Arm Simulation Problems”, Lecture Notes in Computer Science, Vol.10979, pp.177-188, 2018 (DOI: 10.1007/978-3-319-94667-2_15)

A W. Tong, E. Miyano, R. Goebel and G. Lin, “An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops”, Theoretical Computer Science, Vol.734, pp.24-31, 2018 (DOI: 10.1016/j.tcs.2017.09.018)

A Y. Higashikawa, S.W. Cheng, T. Kameda, N. Katoh and S. Saburi, “Minimax Regret 1-Median Problem in Dynamic Path Networks”, Theory of Computing Systems, Vol.62(6), pp.1392-1408, 2018 (DOI: 10.1007/s00224-017-9783-8)

A S. Tamaki and Y. Yoshida, “Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues”, ACM Transactions on Algorithms, Vol.14, No.4, pp.45:1-45:13, 2018 (DOI: 10.1145/3228342)

A N. Tsuchimura and A. Sljoka, “Distributed Computation for Protein Structure Analysis”, Advances in Intelligent Networking and Collaborative Systems. INCoS 2018. Lecture Notes on Data Engineering and Communications Technologies, Vol.23, pp.16-23, 2019 (DOI: 10.1007/978-3-319-98557-2_2)

A N. Kakimura, N. Kamiyama and K. Takazawa, “The b-branching problem in digraphs”, Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics 117, pp.12:1-12:15, 2018 (DOI: 10.4230/LIPIcs.MFCS.2018.12)

A K. Yamanaka, Md.S. Rahman and S. Nakano, “Enumerating Floorplans with Columns”, IEICE TRANS. FUNDAMENTALS, Vol.E101-A, No.9, pp.1392-1397, 2018 (DOI: 10.1587/transfun.E101.A.1392)

A S. Ehara, K. Iwama and J. Teruyama, “Small Complexity Gaps for Comparison-Based Sorting”, Adventures Between Lower Bounds and Higher Altitudes – Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, LNCS 1011, pp.280-296, 2018 (DOI: 10.1007/978-3-319-98355-4)

A E. Argyriou, S. Cornelsen, H. Förster, M. Kaufmann, M. Nöllenburg, Y. Okamoto, C. Raftopoulou and A. Wolff, “Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity”, Lecture Notes in Computer Science, Vol.11282, pp.509-523, 2018 (DOI: 10.1007/978-3-030-04414-5_36)

A A. Nagao, K. Seto and J. Teruyama, “A Moderately Exponential Time Algorithm for k-IBDD Satisfiability”, Algorithmica, Vol.80, No.10, pp.2725–2741, 2018 (DOI: 10.1007/s00453-017-0332-2)

A M. Lampis, K. Makino, V. Mitsou and Y. Uno, “Parameterized edge Hamiltonicity”, Discrete Applied Mathematics, Vol.248, pp.68-78, 2018 (DOI: 10.1016/j.dam.2017.04.045)

A Y. Hanawa, Y. Higashikawa, N. Kamiyama, N. Katoh and A. Takizawa, “The mixed evacuation problem”, Journal of Combinatorial Optimization, Vol.36(4), pp.1299-1314, 2018 (DOI: 10.1007/s10878-017-0237-7)

A E. Boros, K. Elbassioni, M. Fouz, V. Gurvich, K. Makino and B. Manthey, “Approximation schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions”, Algorithmica, 80, pp.3132-3157, 2018 (DOI: 10.1007/s00453-017-0372-7)

A S. Langerman and Yushi Uno, “Threes!, Fives, 1024!, and 2048 are hard”, Theoretical Computer Science, Vol.748, pp.17-27, 2018 (DOI: 10.1016/j.tcs.2018.03.018)

A B. Bhattacharya, Y. Higashikawa, T. Kameda and N. Katoh, “An O(n^2 log^2 n) Time Algorithm for Minmax Regret Minsum Sink on Path Networks”, Proceedings of ISAAC 2018, pp.14:1-14:13, 2018 (DOI: 10.4230/LIPIcs.ISAAC.2018.14)

A Z. Abel, E.D. Demaine, M.L. Demaine, H. Ito, J. Snoeyink and R. Uehara, “Bumpy pyramid folding”, Computational Geometry, Vol.75, pp.22-31, 2018 (DOI: 10.1016/j.comgeo.2018.06.007)

A D. Wang, M. Gaboardi and J. Xu, “Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited”, Proc. 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2018), pp.965-974, 2018.

A E. Arseneva, M.K. Chiu, M. Korman, A. Markovic, Y. Okamoto, A. Ooms, A. van Renssen and M. Roeloffzen, “Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain”, Leibniz International Proceedings in Informatics, Vol.123, pp.58:1-58:13, 2018 (DOI: 10.4230/LIPIcs.ISAAC.2018.58)

A T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Minimum-Cost b-Edge Dominating Sets on Trees”, Algorithmica, Vol.81, No.1, pp.343-366, 2019 (DOI: 10.1007/s00453-018-0448-z)

A K. Iwama and A. Nagao, “Read-Once Branching Programs for Tree Evaluation Problems”, ACM Transactions on Computation Theory, Vol.11, No.1, 2019, Article No.5, 2019 (DOI: 10.1145/3282433)

A J. Kawahara, T. Saitoh and R. Yoshinaka, “The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant”, Journal of Graph Algorithms and Applications, Vol.23, No.1, pp.29-70, 2018 (DOI: 10.7155/jgaa.00483)

A J. Andro-Vasko, W. Bein and H. Ito, “Energy efficiency and renewable energy management with multi-state power-down system”, special issue “Information technology: new generation (ITNG 2018),” Information, MDPI, Vol.10, No.2, Article 44, pp.1-21, 2019 (DOI: 10.3390/info10020044)

A D. Wang and J. Xu, “Differentially private empirical risk minimization with smooth nonconvex loss functions: A non-stationary view”, Proc. the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI 2019), 2019.

A T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Reconfiguration of Maximum-Weight b-Matchings in a Graph”, Journal of Combinatorial Optimization, Vol.37, No.2, pp.454-464, 2019.

A Y. Kishi, N. Kitsuwan, H. Ito, B.C. Chatterjee and E. Oki, “Modulation-Adaptive Link-Disjoint Path Selection Model for 1+1 Protected Elastic Optical Networks”, IEEE Access, Vol.7, No.1, pp.25422-25437, 2019 (DOI: 10.1109/ACCESS.2019.2901018)

A S.W. Bae, M. Korman and Y. Okamoto, “Computing the Geodesic Centers of a Polygonal Domain”, Computational Geometry: Theory and Applications, Vol.77, pp.3-9, 2019 (DOI: 10.1016/j.comgeo.2015.10.009)

A Z. Huang, H. Ding and J. Xu, “Faster Algorithm for Truth Discovery via Range Cover”, Accepted to the special issue of Algorithmica on a few invited paper from WADS 2017, pp.1–16, 2019 (DOI: 10.1007/s00453-019-00562-z)

A R. Yamamoto and A. Takizawa, “Partitioning vertical evacuation areas in Umeda underground mall to minimize the evacuation completion time”, The Review of Socionetwork Strategies, to appear (in press)

A Y. Higashikawa and N. Katoh, “A Survey on Facility Location Problems in Dynamic Flow Networks”, The Review of Socionetwork Strategies (submitted)

A K. Takazawa and Y. Yokoi, “A generalized-polymatroid approach to disjoint common independent sets in two matroids”, Discrete Mathematics, to appear (in press)

A E.D. Demaine, H. Ito, S. Langerman, J. Lynch, M. Rudoy and K. Xiao, “Cookie Clicker”, special issue of JCDCG^3 2017, Graphs and Combinatorics, Springer, 2019 (in press)

A H. Ito, A. Nagao and T. Park, “Generalized shogi, chess, and xiangqui are constant-time testable”, IEICE Transactions, 2019 (in press)

A K. Elbassioni and K. Makino, “Finding Sparse Solutions for Packing and Covering Semidefinite Programs”, 2019 (submitted)

AD K. Yamanaka, E.D. Demaine, T. Horiyama, A. Kawamura, S. Nakano, Y. Okamoto, T. Saitoh, A. Suzuki, R. Uehara and T. Uno, “Sequentially swapping colored tokens on graphs”, Journal of Graph Algorithms and Applications (JGAA), to appear (in press)

ADM K. Yamanaka, E.D. Demaine, T. Horiyama, A. Kawamura, S. Nakano, Y. Okamoto, T. Saitoh, A. Suzuki, R. Uehara and T. Uno, “Sequentially Swapping Colored Tokens on Graphs”, JGAA, Vol.23, No.1, pp.3-27, 2019 (DOI: 10.7155/jgaa.00482)

D P. Abedin, A. Ganguly, W.K. Hon, Y. Nekrich, R. Shah, S.V. Thankachan and K. Sadakane, “A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time”, Proceedings of COCOON, LNCS 10976, pp.615-625, 2018 (DOI: 10.1007/978-3-319-94776-1_51)

D K. Yamanaka, Y. Matsui and S. Nakano, “More Routes for Evacuation”, Proc. of COCOON 2018, LNCS 10976, pp.76-83, 2018 (DOI: 10.1007/978-3-319-94776-1_7)

D T. Ohno, K. Goto, Y. Takabatake, T. I and H. Sakamoto, “LZ-ABT: A Practical Algorithm for α-Balanced Grammar Compression”, IWOCA 2018, 323-335, 2018.

D S. Denzumi, J. Kawahara, K. Tsuda, H. Arimura, S. Minato and K. Sadakane, “DenseZDD: A Compact and Fast Index for Families of Sets”, Algorithms, 11(8), 128, 2018 (DOI: 10.3390/a11080128)

D A. Conte, G. Ferraro, R. Grossi, A. Marino, K. Sadakane and T. Uno, “Node Similarity with q-Grams for Real-World Labeled Networks”, Proceedings of KDD, pp.1282-1291, 2018 (DOI: 10.1145/3219819.3220085)

D H.T. Wei, W.K. Hon, P. Horn, C.S. Liao and K. Sadakane, “An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity”, Proceedings of APPROX, 27:1-27:14, 2018 (DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.27)

D T. Ohno, K. Sakai, Y. Takabatake, T. I and H. Sakamoto, “A faster implementation of online RLBWT and its application to LZ77 parsing”, J. Discrete Algorithms, 52, 18-28, 2018 (DOI: 10.1016/j.jda.2018.11.002)

D S. Nakagawa, T. Sakamoto, Y. Takabatake, T. I, K. Shin and H. Sakamoto, “Privacy-Preserving String Edit Distance with Moves”, SISAP 2018: 226-240, 2018.

D B. Wu, Y. Sun and K. Yada, “The Short-term Impact of an Item-based Loyalty Program”, Proceedings of 2018 IEEE Conference on System, Man and Cybernetics, IEEE Press, pp.1846-1851, 2018 (DOI: 10.1109/SMC.2018.00319)

D Y. Zuo, K. Yada, T. Li and P. Chen, “Application of Network Analysis Techniques for Customer In-store Behavior in Supermarket”, Proc. of 2018 IEEE Conference on System, Man and Cybernetics, IEEE Press, pp.1861-1866, 2018 (DOI: 10.1109/SMC.2018.00322)

D X. Zhong, K. Ishibashi and K. Yada, “An Empirical Study of the Relationship among Self-Control, Price Promotions and Consumer Purchase Behavior”, Proc. of 2018 IEEE Conference on System, Man and Cybernetics, IEEE Press, pp.1867-1872, 2018 (DOI: 10.1109/SMC.2018.00323)

D Y. Kaneko, K. Yada, W. Ihara and R. Odagiri, “How Game Users Consume Virtual Currency: The Relationship Between Consumed Quantity, Inventory, and Elapsed Time Since Last Consumption in the Mobile Game World”, ICDM 2018 Workshop Proceeding, pp.848-855, 2018 (DOI: 10.1109/ICDMW.2018.00125)

D T. Araki and S. Nakano, “The Max-Min Dispersion on a Line”, Proc. of COCOA 2018, LNCS 11346, pp.672-678, 2018 (DOI: 10.1007/978-3-030-04651-4_45)

D K. Nakamura and K. Sadakane, “Space-Efficient Fully Dynamic DFS in Undirected Graphs”, Algorithms, 12(3), Article No.52, 2019 (DOI: 10.3390/a12030052)

D S. Ahmed, S. Nakano and Md.S. Rahman, “r-Gatherings on a Star”, Proc. of WALCOM 2019, LNCS11355, pp.31-42, 2019 (DOI: 10.1007/978-3-030-10564-8_3)

D I. Furuya, T. Takagi, Y. Nakashima, S. Inenaga, H. Bannai and T. Kida, “MR-RePair: Grammar Compression Based on Maximal Repeats”, In Proceedings of Data Compression Conference (DCC2019), IEEE Computer Society Press, pp.508-517, 2019.

D Y. Sasaki, T. Shibuya, K. Ito and H. Arimura, “Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score”, IEICE Transactions on Fundamentals, to appear (in press)

D K. Sakai, T. Ohno, K. Goto, Y. Takabatake, T. I and H. Sakamoto, “RePair in Compressed Space and Time”, DCC2019, to appear (in press)

D K. Ishibashi and K. Yada, “Assessment of Effect of POP on Purchase Behavior: Comparison of Effectiveness of Eyetracking Data and Shopping Path Data”, Proceedings of 5th Asia-Pacific World Congress on Computer Science and Engineering (APWC on CSE 2018), to appear (in press)

M M. Ohzeki, Y. Kudo and K. Tanaka, “An Extension of Estimation of Critical Points in Ground State for Random Spin Systems”, Journal of the Physical Society of Japan, Vol.87, No.1, Article ID.015001, pp.1-2, 2018 (DOI: 10.7566/JPSJ.87.015001)

M S. Arai, M. Ohzeki and K. Tanaka, “Deep Neural Network Detects Quantum Phase Transition”, Journal of the Physical Society of Japan, Vol.87, No.3, Article ID.033001, pp.1-4, 2018 (DOI: 10.7566/JPSJ.87.033001)

M K. Murota and A. Shioura, “On Equivalence of M^\natural-concavity of a Set Function and Submodularity of its Conjugate”, Journal of Operations Research Society of Japan, Vol.61, pp.163-171, 2018 (DOI: 10.15807/jorsj.61.163)

M M. Yasuda, “Learning Algorithm of Boltzmann machine based on Spatial Monte Carlo integration Method”, Algorithms, Vol.11, No.4, Article ID: 42, 2018 (DOI: 10.3390/a11040042)

M M. Yasuda, J. Watanabe, S. Kataoka and K. Tanaka, “Linear-Time Algorithm in Bayesian Image Denoising based on Gaussian Markov Random Field”, IEICE Transactions on Information and Systems, Vol.E101-D, No.6, pp.1629-1639, 2018 (DOI: 10.1587/transinf.2017EDP7346)

M C. Takahashi, M. Ohzeki, S. Okada, M. Terabe, S. Taguchi and K. Tanaka, “Statistical-Mechanical Analysis of Compressed Sensing for Hamiltonian Estimation of Ising Spin Glass”, Journal of the Physical Society of Japan, Vol. 87, No.7, article no. 074001, pp.1–7, 2018 (DOI: 10.7566/JPSJ.87.074001)

M T. Hanaka, T. Ito, H. Mizuta, B. Moore, N. Nishimura, V. Subramanya, A. Suzuki and K. Vaidyanathan, “Reconfiguring Spanning and Induced Subgraphs”, Proceedings of the 24th Annual International Computing and Combinatorics Conference (COCOON 2018), LNCS 10976, pp.428-440, 2018 (DOI: 10.1007/978-3-319-94776-1_36)

M K. Tanaka, M. Nakamura, S. Kataoka, M. Ohzeki and M. Yasuda, “Momentum-space renormalization group transformation in Bayesian image modeling by Gaussian graphical model”, Journal of the Physical Society of Japan, Vol.87, No.8, Article ID.085001, pp.1-2, 2018 (DOI: 10.7566/JPSJ.87.085001)

M S. Cho, M. Tsuchiya, M. Yasuda and M. Yokoyama, “Estimation System of Blood Pressure Variation Using Multiple Regression Analysis and Neural Network”, Proceedings of the International Conference on Advances in Next Generation Computer and Information Technology V (NGCIT2018), Advanced Science and Technology Letters, Vol.152, pp.61-64, 2018 (DOI: 10.14257/astl.2018.152.13)

M T. Hatanaka, T. Ito and X. Zhou, “Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters”, Theoretical Computer Science, Vol.739, pp.65-79, 2018 (DOI: 10.1016/j.tcs.2018.05.005)

M H. Maniwa, T. Oki, A. Suzuki, K. Uchizawa and X. Zhou, “Computational power of threshold circuits of energy at most two”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E101-A, No.9, pp.1431-1439, 2018 (DOI: 10.1587/transfun.E101.A.1431)

M M. Tsuchiya, A. Tanaka, M. Yasuda, T. Harada, S. Cho and M. Yokoyama, “Estimation of Awaking Time Using a Deep Neural Network with Physiological Data During Sleep”, Proceedings of the 2018 International Symposium on Nonlinear Theory and its Applications (NOLTA2018), pp.27-30, 2018.

M T. Harada, M. Yokoyama, M. Yasuda and A. Tanaka, “The Multiple Beacon System for Detection of the Gathering Degree of People in a Certain Place”, Proceedings of the 2018 International Symposium on Nonlinear Theory and its Applications (NOLTA2018), pp.31-33, 2018.

M M. Yasuda, Y. Mikuni, Y. Yokoyama, T. Harada, A. Tanaka and M. Yokoyama, “Detecting Human-Interaction Networks Based on Statistical Machine Learning and Sparse Modeling”, Proceedings of the 2018 International Symposium on Nonlinear Theory and its Applications (NOLTA2018), pp.34-37, 2018.

M A. Tanaka, S. Cho, M. Yasuda, T. Harada and M. Yokoyama, “Community Analysis of Social Networks Based on Network Indexes”, Proceedings of the 2018 International Symposium on Nonlinear Theory and its Applications (NOLTA2018), pp.38-41, 2018.

M M. Ohzeki, C. Takahashi, S. Okada, M. Terabe, S. Taguchi and K. Tanaka, “Quantum annealing: next-generation computation and how to implement it when information is missing”, Nonlinear Theory and Its Applications, IEICE, Vol.9, No.4, pp.392–405, 2018 (DOI: 10.1587/nolta.9.392)

M A. Shioura, N.V. Shakhlevich, V.A. Strusevich and B. Primas, “Models and Algorithms for Energy-Efficient Scheduling with Immediate Start of Jobs”, Journal of Scheduling, Vol.21, pp.505–516, 2018 (DOI: 10.1007/s10951-017-0552-y)

M S. Cho, M. Yasuda, M. Tsuchiya, T. Harada, A. Tanaka and M. Yokoyama, “Estimation of Correlation between Multiple Parameters and Sleep Satisfaction Using Deep Neural Network for Pleasant Sleeping Support System”, Proceedings of the 31th International Conference on Computer Applications in Industry and Engineering (CAINE2018), pp.26-30, 2018.

M S. Cho, T. Negishi, M. Tsuchiya, M. Yasuda and M. Yokoyama, “Estimation system of blood pressure variation with photoplethysmography signals using multiple regression analysis and neural network”, International Journal of Fuzzy Logic and Intelligent Systems, Vol.18, No.4, pp.229-236, 2018 (DOI: 10.5391/IJFIS.2018.18.4.229)

M S. Okada, M. Ohzeki and K. Tanaka, “Phase diagrams of one-dimensional Ising and XY models with fully connected ferromagnetic and anti-ferromagnetic quantum fluctuations”, Journal of the Physical Society of Japan, Vol.88, No.2, Article ID.024802, pp.1-6, 2019 (DOI: 10.7566/JPSJ.88.024802)

M S. Okada, M. Ohzeki and K. Tanaka, “Difference between quantum annealing by imaginary-time and real-time Schrodinger equations of Grover’s search”, Journal of the Physical Society of Japan, Vol.88, No.2, Article ID.024803, pp.1-6, 2019 (DOI: 10.7566/JPSJ.88.024803)

M T. Hatanaka, T. Ito and X. Zhou, “The Coloring Reconfiguration Problem on Specific Graph Classes”, IEICE Trans. on Information and Systems, Vol.E102-D, No.3, pp.423-429, 2019 (DOI: 10.1587/transinf.2018FCP0005)

M S. Arai, M. Ohzeki and K. Tanaka, “Dynamics of order parameters of nonstoquastic Hamiltonians in the adaptive quantum Monte Carlo method”, Physical Review E, Vol.99, article No.032120, 2019 (DOI: 10.1103/PhysRevE.99.032120)

M M. Yasuda, H. Sakata, S.I. Cho, T. Harada, A. Tanaka and M. Yokoyama, “An efficient test method for noise robustness of deep neural networks”, Nonlinear Theory and its Applications, IEICE (in press).