Yuichi Yoshida

Last updated: Apr 15, 2014 at 10:09
 
Avatar
Name
Yuichi Yoshida
Affiliation
National Institute of Informatics
Job title
Assistant Professor
Degree
Doctor of Informatics(Kyoto University)
Other affiliation
Preferred Infrastructure

Academic & Professional Experience

 
Oct 2012
 - 
Today
National Institute of Informatics, Global Research Center for Big Data Mathematics
 
Apr 2012
 - 
Today
Assistant Professor, National Institute of Informatics
 
Mar 2006
 - 
Today
Preferred Infrastructure
 

Education

 
Apr 2009
 - 
Mar 2012
Department of Communications and Computer Engineering (PhD course), School of Informatics, Kyoto University
 
Apr 2007
 - 
Mar 2009
Department of Communications and Computer Engineering (master course), School of Informatics, Kyoto University
 
Apr 2003
 - 
Mar 2007
School of Informatics and Mathematical Science, Faculty of Engineering, Kyoto University
 

Awards & Honors

 
Feb 2014
Inoue Research Award for Young Scientists, Inoue Foundation for Science
 
Apr 2013
The Funai Research Incentive Award, Funai Foundation for Information Technology
 
Mar 2012
Ikushi Prize, Japan Society for the Promotion of Science
 
Mar 2012
President Award, Kyoto University
 
May 2009
1st place, Multicore Programming Contest Cell Challenge, Symposium on Advanced Computing Systems and Infrastructures (SACSIS)
Winner: Shun Sakuraba, Yuichi Yoshida
 
Apr 2008
World Finals: 47th place, International Collegiate Programming Contest, ACM
Winner: Norihiro Katsumaru, Toshiyuki Hanaoka, Yuichi Yoshida
 
Mar 2007
World Finals: 14th place, International Collegiate Programming Contest, ACM
Winner: Norihiro Katsumaru, Toshiyuki Hanaoka, Yuichi Yoshida
 
Oct 2007
5th place, ICFP Programming Contest, ACM / SIGPLAN
Winner: Yuichi Yoshida (as a member of Preferred Infrastructure)
 

Published Papers

 
Testing Forest-Isomorphism in the Adjacency List Model
Mitsuru Kusumoto and Yuichi Yoshida
Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP)      Jul 2014   [Refereed]
Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations
Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-Ichi Kawarabayashi
Proc. 28th AAAI Conference on Artificial Intelligence (AAAI)      Jul 2014   [Refereed]
Yuichi Yoshida
Proc. 46th ACM Symposium on the Theory of Computing (STOC)      May 2014   [Refereed]
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida
Proc. 23rd International World Wide Web Conference (WWW)      Apr 2014   [Refereed]
Yoichi Iwata, Keigo Oka, and Yuichi Yoshida
Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)   1749-1761   Jan 2014   [Refereed]
Kazuo Iwama and Yuichi Yoshida
Proc. 5th Innovations in Theoretical Computer Science (ITCS)   507-516   Jan 2014   [Refereed]
Yuichi Yoshida and Yuan Zhou
Proc. 5th Innovations in Theoretical Computer Science (ITCS)   423-438   Jan 2014   [Refereed]
A query efficient non-adaptive long code test with perfect completeness
Suguru Tamaki and Yuichi Yoshida
Random Structures & Algorithms      2014   [Refereed]
Satoru Fujishige, Shin-ichi Tanigawa, and Yuichi Yoshida
Discrete Optimization      Dec 2013   [Refereed]
Shin-ichi Tanigawa, Yuichi Yoshida
Algorithmica      Nov 2013   [Refereed]
Francois Le Gall and Yuichi Yoshida
Journal of Combinatorial Optimization   26(4) 636-654   Nov 2013   [Refereed][Invited]
Linear-Time Enumeration of Maximal k-Edge-Connected Subgraphs in Large Networks by Random Contraction
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida
Proc. 22nd ACM International Conference on Information and Knowledge Management (CIKM)   909-918   Oct 2013   [Refereed]
Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths
Yosuke Yano, Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida
Proc. 22nd ACM International Conference on Information and Knowledge Management (CIKM)   1601-1606   Oct 2013   [Refereed]
Eric Blais, Amit Weinstein, and Yuichi Yoshida
Combinatorics Probability and Computing   1-7   Oct 2013   [Refereed]
Danushka Bollegala, Mitsuru Kushimoto, Yuichi Yoshida, and Ken-ichi Kawarabayashi
Proc. 23rd International Joint Conference on Artificial Intelligence (IJCAI)      Aug 2013   [Refereed]
Arnab Bhattacharyya and Yuichi Yoshida
Proc. 40th International Colloquium on Automata, Languages and Programming (ICALP)   123-134   Jul 2013   [Refereed]
Karl Wimmer, Yuichi Yoshida
Proc. 40th International Colloquium on Automata, Languages and Programming (ICALP)   840-850   Jul 2013   [Refereed]
Testing Subdivision-Freeness: – Property Testing Meets Structural Graph Theory –
Ken-ichi Kawarabayashi and Yuichi Yoshida
Proc. 45th ACM Symposium on Theory of Computing (STOC)   437-446   Jun 2013   [Refereed]
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida
Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD)   349-360   Jun 2013   [Refereed]
See https://github.com/iwiwi/pruned-landmark-labeling for softwares
Iwata Yoichi and Yuichi Yoshida
Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS)   127-138   Feb 2013   [Refereed]
Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs
Mitsuru Kusumoto, Yuichi Yoshida, and Hiro Ito
International Journal of Networking and Computing   192-204   2013   [Refereed]
Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs
Mitsuru Kusumoto, Yuichi Yoshida, Hiro Ito
Proc. 3rd International Conference on Networking and Computing (ICNC)   (69) 1-6   Dec 2012   [Refereed]
Eric Blais, Amit Weinstein, Yuichi Yoshida
Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)   551-560   Oct 2012   [Refereed]
Suguru Tamaki, Yuichi Yoshida
Proc. 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)   313-324   Aug 2012   [Refereed]
Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida
Proc. 39th International Colloquium on Automata, Language and Programming (ICALP)   498-509   Jul 2012   [Refereed]
Algorithms and complexity of generalized river crossing problems
Stefan Langerman, Hiro Ito, Yuichi Yoshida
Proc. 6th International Conference on Fun with Algorithms (FUN)   235-244   Jun 2012   [Refereed]
Constant-time approximation algorithms for the knapsack problem
Hiro Ito, Susumu Kiyoshima, Yuichi Yoshida
Proc. 9th Annual Conference on Theory and Applications of Models of Computation (TAMC)   131-142   Jun 2012   [Refereed]
Yuichi Yoshida
Proc. 27th Annual IEEE Conference on Computational Complexity (CCC)   85-95   Jun 2012   [Refereed]
Linear programming, width-1 CSPs, and robust satisfaction
Gabor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou
Proc. 3rd Innovations in Theoretical Computer Science (ITCS)   484-495   Jan 2012   [Refereed]
Property testing on k-vertex connectivity of graphs
Yuichi Yoshida, Hiro Ito
Algorithmica   62(3) 701-712   2012   [Refereed]
Gábor Ivanyos, François Le Gall, Yuichi Yoshida
European Journal of Combinatorics   33(4) 474-476   2012   [Refereed]
Testing the (s, t)-disconnectivity of graphs and digraphs
Yusuke Kobayashi, Yuichi Yoshida
Theoretical Computer Science   434(25) 98-113   2012   [Refereed]
An almost optimal algorithm for Winkler’s sorting pairs in bins
Hiro Ito, Junichi Teruyama, Yuichi Yoshida
Progress in Informatics   9 3-7   2012   [Refereed]
Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
Yuichi Yoshida, Masaki Yamamoto, Hiro Ito
Siam Journal on Computing   41(4) 1074-1093   2012   [Refereed]
Algorithms for finding a maximum non-k-linked graph
Yusuke Kobayashi, Yuichi Yoshida
Proc. 20th European Symposia on Algorithms (ESA)   131-142   Sep 2011   [Refereed]
Property testing for cyclic groups and beyond
Francois Le Gall and Yuichi Yoshida
Proc. 17th Annual International Computing and Combinatorics Conference (COCOON)   432-443   Aug 2011   [Refereed]
Yuichi Yoshida
Proc. 43rd Annual ACM Symposium on Theory of Computing (STOC)   665-674   Jun 2011   [Refereed]
Yuichi Yoshida
Proc. 26th Annual IEEE Conference on Computational Complexity (CCC)   34-44   Jun 2011   [Refereed]
Testing algorithms for (k, l)-sparsity and (k, l)-edge-connected orientability
Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida
Proc. 7th Hungarian-Japanese Symposium on Discrete Math   447-456   May 2011
Testing outerplanarity of bounded degree graphs
Yuichi Yoshida, Hiro Ito
Proc. 14th International Workshop on Randomization and Computation (RANDOM)   642-665   Sep 2010   [Refereed]
A query efficient non-adaptive long code test with perfect completeness
Suguru Tamaki, Yuichi Yoshida
Proc. 14th International Workshop on Randomization and Computation (RANDOM)   738-751   Sep 2010   [Refereed]
Conjunctive filter: Breaking the entropy barrier
Daisuke Okanohara, Yuichi Yoshida
Proc. Workshop on Algorithm Engineering and Experiments (ALENEX)   77-83   Jan 2010   [Refereed]
Testing k-edge-connectivity of digraphs
Yuichi Yoshida, Hiro Ito
Journal of System Science and Complexity   23(1) 91-101   2010   [Refereed]
Query-number preserving reductions and linear lower bounds for testing
Yuichi Yoshida, Hiro Ito
IEICE Transactions on Information and Systems   93(2) 233-240   2010   [Refereed]
Shun Sakuraba and Yuichi Yoshida. Fast calculation of levenshtein distance on the cell processor
Shun Sakuraba, Yuichi Yoshida
Proc. 7th Annual Symposium on Advanced Computing Systems and Infrastructures (SACSIS)      May 2009   [Invited]
An improved constant-time approximation algorithm for maximum matchings
Yuichi Yoshida, Masaki Yamamoto, Hiro Ito
Proc. 41st Annual ACM Symposium on Theory of Computing (STOC)   225-234   May 2009   [Refereed]
Property testing on k-vertex connectivity of graphs
Yuichi Yoshida, Hiro Ito
Proc. 35th International Colloquium on Automata, Language and Programming (ICALP)   539-550   Jul 2008   [Refereed]

Misc

 
On A Generalization of River Crossing Problems
Hiro Ito, Stefan Langerman, Yuichi Yoshida
Proc. 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC)      Apr 2013   [Refereed]
Fast Exact Distance Queries on Large Networks by Pruned Shortest-Path Trees
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida
Proc. 3rd Workshop on Algorithms for Large-Scale Information Processing (ALSIP)      Nov 2012   [Refereed]
Constant-time approximation algorithms for the optimum branching problem on sparse graphs
Mitsuru Kusumoto, Yuichi Yoshida, Hiro Ito
Proc. 5th Annual Meeting of Asian Association for Algorithms and Computation (AAAC)      Apr 2012
Testing graph rigidity in constant time
Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida
Proc. 4th Annual Meeting of Asian Association for Algorithms and Computation (AAAC)      Apr 2011
ITO Hiro, KIYOSHIMA Susumu, YOSHIDA Yuichi
IEICE technical report. Theoretical foundations of Computing   110(464) 29-36   Mar 2011

Conference Activities & Talks

 
A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems
Yuichi Yoshida
ELC Mini-Workshop on Sublinear-Time Algorithms (A02)   6 Dec 2013   
Robust approximation of CSPs: Universal algebra meets optimization [Invited]
Yuichi Yoshida
ELC Tokyo Complexity Workshop   Mar 2013   
Testing Assignments of Boolean CSPs
Yuichi Yoshida
The Constraint Satisfaction Problem: Complexity and Approximability   Sep 2012   
Testing Juntas of Symmetric Functions [Invited]
Yuichi Yoshida
China Theory Week   Oct 2011   
Introduction to Randomized Algorithms [Invited]
Yuichi Yoshida
JOI Summer Seminar 2011   Aug 2011   

Works

 
Anthy Project (Japanese Input Method)
Yusuke Tabata, Yuichi Yoshida   Software   2004 - 2008

Research Grants & Projects

 
Research on approximation methods for isomorphism problems
JSPS: Grants-in-Aid for Research Activity Start-up
Project Year: Oct 2012 - Mar 2014    Investigator(s): Yuichi Yoshida
Sublinearize polynomial-time algorithms
Kayamori Foundation of Informational Science Advancement: Fellowships
Project Year: 2012 - Mar 2014    Investigator(s): Yuichi Yoshida
A Multifaceted Approach toward Understanding the Limitations of Computation
MEXT: Grant-in-Aid for Scientific Research on Innovative Areas
Project Year: 2012       Investigator(s): Osamu Watanabe
Japanese Input Environment on Embedded Systems
Information Technology Promotion Agency: Exploratory IT Human Resources Project
Project Year: Apr 2005 - Mar 2006    Investigator(s): Yuichi Yoshida