On the derandomization of the graph test for homomorphism over groups
From MaRDI portal
Publication:2430014
DOI10.1016/j.tcs.2010.12.046zbMath1215.68113MaRDI QIDQ2430014
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
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