On the derandomization of the graph test for homomorphism over groups

DOI10.1016/j.tcs.2010.12.046zbMath1215.68113MaRDI QIDQ2430014

Lin-Qing Tang

Publication date: 5 April 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.12.046

zbMATH Keywords

random walk\(\lambda \)-biased setexpanding Cayley graphgraph testhomomorphism over groups

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60C05: Combinatorial probability

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

05C81: Random walks on graphs

Cites Work

• Unnamed Item
• \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
• Explicit construction of linear sized tolerant networks
• Self-testing/correcting with applications to numerical problems
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• A PCP characterization of NP with optimal amortized query complexity
• Derandomizing homomorphism testing in general groups
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• Efficient approximation of product distributions
• Simple analysis of graph tests for linearity and PCP
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The PCP theorem by gap amplification