Yutaro YAMAGUCHI

Assistant Professor

Department of Information and Physical Sciences,

Graduate School of Information Science and Technology,

Osaka University

Information Science and Technology Building C, Room C501,

1-5 Yamadaoka, Suita, Osaka 565-0871, Japan

Tel: +81-6-6879-7872

Email: yutaro_yamaguchi [at] ist.osaka-u.ac.jp

(old: ymgc [at] kurims.kyoto-u.ac.jp, yutaro_yamaguchi [at] mist.i.u-tokyo.ac.jp)

C.V.

March 2008: Graduation from Tennoji High School attached to Osaka Kyoiku University, Japan.

March 2011: Withdrawal from Undergraduate School of Informatics and Mathematical Science,

Faculty of Engineering, Kyoto University, Japan. (Because of proceeding to the master's course.)

March 2013: **Master of Science** from Department of Mathematical Sciences,

Graduate School of Science, Kyoto University, Japan.

March 2016: **Doctor of Philosophy in the field of Mathematical Informatics** from Department of Mathematical Informatics,

Graduate School of Information Science and Technology, University of Tokyo, Japan.

Feb. 2013 – Mar. 2013: Project Assistant of JST ERATO Kawarabayashi Large Graph Project (Link)

"The Network Graph Theories and Optimization Group."

Apr. 2013 – Mar. 2016: Research Fellow of the Japan Society for the Promotion of Science (DC1).

Apr. 2016 – Today: Assistant Professor at Osaka University.

Aug. 2017 – Mar. 2018: Visiting Researcher at Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project.

Apr. 2013 – Today: Research Collaborator of JST ERATO Kawarabayashi Large Graph Project

"The Network Graph Theories and Optimization Group."

Aug. 2013 – Sep. 2013: Visit for Joint Research to NEC Laboratories at Kawasaki, Kanagawa, Japan.

Feb. 2014 – Mar. 2014: Visit for Joint Research to NEC Laboratories America at Cupertino, California, U.S.

Aug. 2017 – Sep. 2017: Visit for Joint Research to Minato Discrete Structure Manipulation System Project at Hokkaido University, Japan.

Oct. 2013 – Mar. 2014: Teaching Assistant of the class "Algorithm Design" at Department of Mathematical Informatics,

Graduate School of Information Science and Technology, University of Tokyo.

Oct. 2014 – Mar. 2015: Teaching Assistant of the class "Algorithm Design" at Department of Mathematical Informatics,

Graduate School of Information Science and Technology, University of Tokyo.

Apr. 2015 – Aug. 2015: Teaching Assistant of "First-Year Seminar for Natural Sciences Students"

(Theme: Introduction to Operations Research) at College of Arts and Sciences, University of Tokyo.

1st Semester in 2017: "Information Literacy A" at Division of Applied Science, School of Engineering, Osaka University.

2nd Semester in 2017: "Exercises in Information Physics and Sciences I" at Department of Applied Physics, School of Engineering, Osaka University.

Apr. 2013 – Mar. 2016: Grant-in-Aid for JSPS Research Fellow (No. 13J02522).

Aug. 2016 – Mar. 2018: JSPS KAKENHI, Grant-in-Aid for Research Activity Start-up (No. 16H06931).

Dec. 2016 – Mar. 2018: JST ACT-I "Information and Future" (No. JPMJPR16UR).

Apr. 2013 – Today: A member of the Operations Research Society of Japan (No. 05000219).

During 2015: A student member of the Institute of Electrical and Electronics Engineers (IEEE) (No. 93303728).

Research Interest

Combinatorial Optimization, Graph Theory, Matroid Theory, Discrete Algorithms, Game Theory, Quantum Computing, Machine Learning, etc.

Pubilications

4. Shin-ichi Tanigawa, __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Matroid Matching**.

3. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

*Discrete Mathematics*, **339**:8 (2016), pp. 2007–2017.

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

1. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

*IEEE Transactions on Smart Grid*, **6**:5 (2015), pp. 2189–2199.

6. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Packing Integer Programs with Few Queries**.

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms* (*SODA 2018*), to appear. New!

5. __Yutaro Yamaguchi__: **Shortest Disjoint S-paths via Weighted Linear Matroid Parity**.

4. Naoto Ohsaka, __Yutaro Yamaguchi__, Naonori Kakimura, Ken-ichi Kawarabayashi: **Maximizing Time-decaying Influence in Social Networks**.

*Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases*

(*ECML-PKDD 2016*), pp. 132–147, 2016.

3. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path in Group-Labeled Graphs with Two Labels Forbidden**.

*Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming* (*ICALP 2015*), pp. 797–809, 2015.

* The full version is available here.

2. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

*Proceedings of the 5th IEEE International Conference on Smart Grid Communications* (*SmartGridComm 2014*), pp. 830–835, 2014.

1. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

11. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Packing Integer Programs with Few Queries**.

*arXiv preprints*, arXiv:1707.04020 (Link), 2017.

10. Yasushi Kawase, __Yutaro Yamaguchi__: **Antimatroids Induced by Matchings**.

*arXiv preprints*, arXiv:1705.05510 (Link), 2017.

9. Yoichi Iwata, __Yutaro Yamaguchi__, Yuichi Yoshida: **0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms**.

* A preliminary version is entitled

8. Kristóf Bérczi, Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **Making Bipartite Graphs DM-irreducible**.

*arXiv preprints*, arXiv:1612.08828 (Link), 2016.

* A preliminary version had appeared as a Mathematical Engineering Technical Report, METR 2016-14 (Link).

7. Yoshinobu Kawahara, __Yutaro Yamaguchi__:

**Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions**.

*arXiv preprints*, arXiv:1509.03946 (Link), 2015.

6. __Yutaro Yamaguchi__: **Shortest Disjoint Non-zero A-paths via Weighted Matroid Matching**.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2015.

5. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path in Group-Labeled Graphs with Two Labels Forbidden**.

*Mathematical Engineering Technical Reports*, METR 2014-41 (Link),

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.

* A revised version (the full version of the same-title paper in ICALP 2015) is available here.

4. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

*Mathematical Engineering Technical Reports*, METR 2014-28 (Link),

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.

3. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

*Mathematical Engineering Technical Reports*, METR 2014-12 (Link),

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2013.

1. Shin-ichi Tanigawa, __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Matroid Matching**.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2013.

[Ph.D. Thesis] *Combinatorial Optimization on Group-Labeled Graphs*. (Supervised by Prof. Satoru Iwata)

Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Japan, March 2016.

[Master's Thesis] *Structures and Algorithms for Path-Packing Problems*. (Supervised by Prof. Satoru Iwata)

Department of Mathematical Sciences, Graduate School of Science, Kyoto University, Japan, January 2013.

6. Yusuke Kobayashi, __Yutaro Yamaguchi__: **On Applications of Weighted Linear Matroid Parity**.

*Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications*, pp. 363–372, 2017.

5. Ryohei Fujimaki, __Yutaro Yamaguchi__, Riki Eto: **Piecewise Sparse Linear Classification via Factorized Asymptotic Bayesian Inference**.

*Transactions of the Japanese Society for Artificial Intelligence*, **31**:6 (2016), No. AI30-I_1-9 (Link).

* This article is written in Japanese except for the title and abstract.

4. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

*Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications*, pp. 137–146, 2015.

3. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Zero Path in Z _{3}-Labeled Graphs**.

Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan, 2015.

* This is a resume of the technical report METR 2014-41.

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan, 2014.

* This is a resume of the same-title paper in SODA 2014.

1. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Matroid Matching**.

International Talks

12. Yusuke Kobayashi, __Yutaro Yamaguchi__: **On Applications of Weighted Linear Matroid Parity**.

The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 2017. (Slide)

11. __Yutaro Yamaguchi__: **Shortest Disjoint S-paths via Weighted Linear Matroid Parity**.

The 27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney, Australia, December 2016. (Slide)

10. Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **How to Make a Bipartite Graph DM-irreducible by Adding Edges**.

The Japanese Conference on Combinatorics and its Applications (JCCA 2016), Kyoto, Japan, May 2016. (Slide)

9. Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **How to Make a Bipartite Graph DM-irreducible by Adding Edges**.

NII Shonan Meeting Seminar 071 "Current Trend in Combinatorial Optimization," Kanagawa, Japan, April 2016. (Slide)

8. __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Linear Matroid Parity**.

The 6th Cargèse Workshop on Combinatorial Optimization, Cargèse, Corsica, France, September 2015. (Slide)

7. Shin-ichi Tanigawa, __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Matroid Matching**.

The 22nd International Symposium on Mathematical Programming (ISMP 2015), Pittsburgh, Pennsylvania, U.S., July 2015. (Slide)

6. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path in Group-Labeled Graphs with Two Labels Forbidden**.

The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, July 2015. (Slide)

5. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, June 2015. (Slide)

4. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labeled Graphs via Linear Matroid Parity**.

IMA Annual Program Year Workshop "Convexity and Optimization: Theory and Applications,"

Minneapolis, Minnesota, U.S., February 2015. (Poster, Summary)

3. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

The 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014), Venice, Italy, November 2014. (Slide)

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

The 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, U.S., January 2014. (Slide)

1. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Matroid Matching**.

The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Veszprém, Hungary, June 2013.

Visited Cities

15. **Barcelona** in **Spain**: January 2017,

The 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).

14. **Sydney** in **Australia**: December 2016,

Talk in the 27th International Symposium on Algorithms and Computation (ISAAC 2016).

13. **Arlington** in **Virginia**, **U.S.**: January 2016,

The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).

12. **Bonn** (+ **Frankfurt**, **Stuttgart**, **München (Munich)**, **Köln**, and **Mainz**) in **Germany**: October 2015,

HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop.

11. **Cargèse** in **Corsica** (+ **Paris**), **France**: September 2015,

Talk in the 6th Cargèse Workshop on Combinatorial Optimization.

10. **Seattle** in **Washington**, **U.S.**: August 2015,

Private Visit.

9. **Pittsburgh** in **Pennsylvania**, **U.S.**: July 2015,

Talk in the 22nd International Symposium on Mathematical Programming (ISMP 2015).

8. **Minneapolis** in **Minnesota**, **U.S.**: February 2015,

IMA Annual Program Year Workshop "Convexity and Optimization: Theory and Applications."

7. **Venezia (Venice)** in **Italy**: November 2014,

Talk in the 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014).

6. **Budapest** in **Hungary**: June 2014, May 2017;

Summer School in Mathematics at Institute of Mathematics in Eötvös Loránd University,

Talk in the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications.

5. **Silicon Valley (San Jose, Mountain View, Cupertino)** and **San Francisco** (+ **Yosemite Park**) in **California**, **U.S.**: February and March 2014,

Joint Research to NEC Laboratories America at Cupertino.

4. **Portland** in **Oregon**, **U.S.**: January 2014,

Talk in the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).

3. **Veszprém** in **Hungary**: June 2013,

Talk in the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications.

2. **Zurich** and **Engelberg** in **Switzerland**: March 2012,

The 1st ETH-Japan Symposium for the Promotion of Academic Exchanges and the 1st ETH-Japan Workshop on Science and Computing.

1. **Toronto** and **Waterloo** in **Canada**: September 2011,

Invited to a special program on Quantum Computing at Institute for Quantum Computing (IQC) in University of Waterloo.