Publications

Conferences:

• Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, Ken-Ichi Kawarabayashi,
  Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations
  AAAI 2014, to appear.
• Yuichi Yoshida,
  A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems,
  STOC 2014, to appear.
  
• Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida,
  Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling,
  WWW 2014, to appear.
• Kazuo Iwama and Yuichi Yoshida.
  Parameterized Testability.
  ITCS 2014, pp. 507--516.
• Yuichi Yoshida and Yuan Zhou.
  Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems.
  ITCS 2014, pp. 423--438.
• Yoichi Iwata, Keigo Oka, and Yuichi Yoshida.
  Linear Time FPT Algorithms via Network Flow.
  SODA 2014, pp. 1749--1761.
• Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida,
  Linear-Time Enumeration of Maximal k-Edge-Connected Subgraphs in Large Networks by Random Contraction.
  CIKM 2013, pp. 909--918. (full paper)
• Yosuke Yano, Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida,
  Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths.
  CIKM 2013, pp. 1601--1606. (short paper)
• Karl Wimmer and Yuichi Yoshida,
  Testing Linear-Invariant Function Isomorphism.
  ICALP 2013, pp. 840--850.
• Arnab Bhattacharyya and Yuichi Yoshida,
  An Algebraic Characterization of Testable Boolean CSPs.
  ICALP 2013, pp. 123--134.
• Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida,
  Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling.
  SIGMOD 2013, pp. 349--360. [arXiv]
• Danushka Bollegala, Mitsuru Kusumoto, Yuichi Yoshida, and Ken-ichi Kawarabayashi,
  Mining for Analogous Tuples from an Entity-Relation Graph.
  IJCAI 2013, pp. 2064--2070
• Ken-ichi Kawarabayashi and Yuichi Yoshida.
  Testing Subdivision-Freeness: – Property Testing Meets Structural Graph Theory –.
  STOC 2013, pp. 437--446.
  
• Yoichi Iwata and Yuichi Yoshida,
  Exact and Approximation Algorithms for the Constraint Satisfaction Problem over the Point Algebra.
  STACS 2013, pp. 127--138.
  
• Mitsuru Kusumoto, Yuichi Yoshida, and Hiro Ito,
  Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs. ICNC 2012, 69:1--6.
  
• Eric Blais, Amit Weinstein, and Yuichi Yoshida,
  Partially Symmetric Functions are Efficiently Isomorphism-Testable.
  FOCS 2012, pp. 551--560. [arXiv]
• Suguru Tamaki and Yuichi Yoshida,
  Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues.
  APPROX 2012, pp. 313--324.
  
• Hiro Ito, Shin-ichi Tanigawa and Yuichi Yoshida,
  Constant-Time Algorithms for Sparsity Matroids.
  ICALP 2012, pp. 498--509. [arXiv]
• Yuichi Yoshida,
  Testing List H-Homomorphisms.
  CCC 2012, pp. 85--95. [arXiv]
• Hiro Ito, Stefan Langerman, and Yuichi Yoshida,
  Algorithms and Complexity of Generalized River Crossing Problems.
  FUN 2012, pp. 235--244.
• Hiro Ito, Susumu Kiyoshima, and Yuichi Yoshida,
  Constant-Time Approximation Algorithms for the Knapsack Problem.
  TAMC 2012, pp. 131--142.
• Gabor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou,
  Linear Programming, Width-1 CSPs, and Robust Satisfaction.
  ITCS 2012, pp. 484--495.
• Yusuke Kobayashi and Yuichi Yoshida,
  Algorithms for Finding a Maximum Non-k-linked Graph.
  ESA 2011, pp. 131--142.
• Francois Le Gall and Yuichi Yoshida,
  Property Testing for Cyclic Groups and Beyond.
  COCOON 2011, pp. 432--443. [arXiv]
• Yuichi Yoshida,
  Lower Bounds on the Query Complexity for Testing Bounded Degree CSPs.
  CCC 2011, pp. 34--44. [arXiv]
• Yuichi Yoshida,
  Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP.
  STOC 2011, pp. 665--674. [arXiv]
• Suguru Tamaki and Yuichi Yoshida,
  A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness.
  RANDOM 2010, pp. 738--751. [ECCC]
• Yuichi Yoshida and Hiro Ito,
  Testing Outerplanarity of Bounded Degree Graphs.
  RANDOM 2010, pp. 642--655.
• Daisuke Okanohara and Yuichi Yoshida,
  Conjunctive Filter: Breaking the Entropy Barrier.
  ALENEX 2010, pp. 77--83. [pdf]
• Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito,
  An Improved Constant-Time Approximation Algorithm for Maximum Matchings.
  STOC 2009, pp. 225--234. [pdf]
• Yuichi Yoshida and Hiro Ito,
  Property Testing on k-Vertex Connectivity of Graphs.
  ICALP 2008, LNCS 5125, Springer, pp. 539--550. [pdf]

Articles:

• Satoru Fujishige, Shin-ichi Tanigawa and Yuichi Yoshida,
  Generalized Skew Bisubmodularity: A Characterization and a Min–Max Theorem
  Discrete Optimization, to appear.
• Shin-ichi Tanigawa and Yuichi Yoshida,
  Testing the Supermodular-cut Condition.
  Algorithmica, to appear.
• Eric Blais, Amit Weinstein and Yuichi Yoshida,
  Semi-Strong Coloring of Intersecting Hypergraphs.
  Combinatorics, Probability and Computing, to appear. [arXiv]
• Mitsuru Kusumoto, Yuichi Yoshida, and Hiro Ito,
  Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs,
  International Journal of Networking and Computing, 3(2), 192--204, 2013.
• Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito,
  Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems.
  SIAM Journal on Computing, 41(4), pp. 1074--1093, 2012.
  
• Yusuke Kobayashi and Yuichi Yoshida,
  Algorithms for Finding a Maximum Non-k-linked Graph.
  SIAM Journal on Discrete Mathematics, 26, pp. 591--604, 2012.
• Yuichi Yoshida and Yusuke Kobayashi,
  Testing the (s,t)-Disconnectivity of Graphs and Digraphs.
  Theoretical Computer Science, 434(25), pp. 98--113, 2012.
• Francois Le Gall and Yuichi Yoshida,
  Property Testing for Cyclic Groups and Beyond.
  Journal of Combinatorial Optimization, to appear.
• Ito Hiro, Teruyama Junichi, and Yoshida Yuichi,
  An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins.
  Progress in Informatics, 9, pp. 3--7, 2012. [pdf]
• Gábor Ivanyos, François Le Gall, Yuichi Yoshida, 
  On the Distance between Non-Isomorphic Groups.
  European Journal of Combinatorics, 33(4), pp. 474--476, 2012. [arXiv]
• Yuichi Yoshida and Hiro Ito,
  Property Testing on k-Vertex Connectivity of Graphs.
  Algorithmica, 62(3), pp. 701--712, 2012.
• Yuichi Yoshida and Hiro Ito,
  Query-Number Preserving Reductions and Linear Lower Bounds for Testing.
  IEICE Transactions on Information and Systems, 93(2), pp. 233--240, 2010.
• Yuichi Yoshida and Hiro Ito,
  Testing k-Edge-Connectivity of Digraphs.
  Journal of System Science and Complexity, 23(1), pp. 91--101, 2010. [pdf]

Others:

• Hiro Ito, Stefan Langerman, and Yuichi Yoshida, On A Generalization of River Crossing Problems. AAAC 2013.
• Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida, Fast Exact Distance Queries on Large Networks by Pruned Shortest-Path Trees, ALSIP 2012.
  
• Mitsuru Kusumoto, Yuichi Yoshida, and Hiro Ito, Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs, AAAC 2012.
• Hiro Ito, Shin-ichi Tanigawa and Yuichi Yoshida, Testing Algorithms for (k,l)-Sparsity and (k,l)-Edge-Connected Orientability. Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2011.
• Hiro Ito, Shin-ichi Tanigawa and Yuichi Yoshida, Testing Graph Rigidity in Constant Time, AAAC 2011.
• Hiro Ito, Junichi Teruyama and Yuichi Yoshida, An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins, AAAC 2010.
• Shun Sakuraba and Yuichi Yoshida, Fast Calculation of Levenshtein Distance on the Cell Processor, SACSIS 2009. (invited)
• Yuichi Yoshida, Masaki Yamamoto and Hiro Ito, Constant-Time Approximations Using Minimum Value Search for Independent Sets and Matchings, AAAC 2009. [pptx]
• Yuichi Yoshida and Hiro Ito, On k-Connectivity Testing in Degree-Bounded Graphs, AAAC 2008.

Manuscripts:

• Taro Takaguchi, Takehisa Hasegawa, and Yuichi Yoshida. Suppressing epidemics on networks by exploiting observer nodes. [arXiv]
• Satoru Fujishige, Shin-ichi Tanigawa, and Yuichi Yoshida. Minimizing and Maximizing α-bisubmodular functions.
• Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSPs.
• Yu Wu, Yuichi Yoshida, Yuan Zhou, and Aravindan Vijayaraghavan. Graph Isomorphism: Approximate and Robust.
• Yoichi Iwata, Keigo Oka, and Yuichi Yoshida, Faster Algorithms for Graphs of Bounded Branch-Width Imply Faster Algorithms for Max 2-SAT.