3.4k citations · 3.9k across the 67 of their papers we have counts for
5 papers · 1 filter
Partially Symmetric Functions are Efficiently Isomorphism-Testable
Eric Blais, Amit Weinstein, Yuichi Yoshida
Given a function f: {0,1}^n \to {0,1}, the f-isomorphism testing problem requires a randomized algorithm to distinguish functions that are identical to f up to relabeling of the in…
On the distance between non-isomorphic groups
Gábor Ivanyos, François Le Gall, Yuichi Yoshida
A result of Ben-Or, Coppersmith, Luby and Rubinfeld on testing whether a map be two groups is close to a homomorphism implies a tight lower bound on the distance between the multip…
Testing List H-Homomorphisms
Yuichi Yoshida
Let be an undirected graph. In the List -Homomorphism Problem, given an undirected graph with a list constraint for each variable , the…
Property Testing for Cyclic Groups and Beyond
Francois Le Gall, Yuichi Yoshida
This paper studies the problem of testing if an input (Gamma,*), where Gamma is a finite set of unknown size and * is a binary operation over Gamma given as an oracle, is close to…
Constant-Time Algorithms for Sparsity Matroids
Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida
A graph is called -full if contains a subgraph of edges such that, for any non-empty , hol…