Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Random Struct. Algorithms

• Publication date

  2008-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/rsa.20182
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Derandomizing homomorphism testing in general groups

  2004cited by this paper
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

  2003cited by this paper
• Simple analysis of graph tests for linearity and PCP

  2001cited by this paper
• A PCP characterization of NP with optimal amortized query complexity

  2000cited by this paper
• Linearity testing in characteristic two

  1995cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990influential reference

• Homomorphism Testing with Resilience to Online Manipulations

  2025influential citation
• Biased Linearity Testing in the 1% Regime

  2025cites this paper
• Group Order is in QCMA

  2025cites this paper
• A General Framework for Low Soundness Homomorphism Testing

  2025cites this paper
• On Axis-Parallel Tests for Tensor Product Codes

  2020cites this paper
• Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

  2020cites this paper
• Distribution-Free Testing of Linear Functions on R^n

  2019cites this paper
• Testing Linearity against Non-signaling Strategies

  2018cites this paper
• Property Testing and Probability Distributions: New Techniques, New Models, and New Goals

  2017cites this paper
• Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

  2017cites this paper
• A Characterization of Testable Hypergraph Properties

  2017cites this paper
• The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

  2016cites this paper
• On Hardness of Approximating the Parameterized Clique Problem

  2016cites this paper
• Testing properties of functions on finite groups

  2015cites this paper
• Approximate Modularity

  2015cites this paper
• Sampling Correctors

  2015cites this paper
• Direct Sum Testing

  2015cites this paper
• Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups

  2015cites this paper
• Linearity and Group Homomorphism Testing / Testing Hadamard Codes

  2015cites this paper
• Carries, Group Theory, and Additive Combinatorics

  2013cites this paper
• On the derandomization of the graph test for homomorphism over groups

  2011cites this paper
• Sublinear Time Algorithms

  2011cites this paper
• Property testing for cyclic groups and beyond

  2011cites this paper
• On the distance between non-isomorphic groups

  2011cites this paper
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

  2009cites this paper
• Delegating computation reliably: paradigms and constructions

  2009cites this paper
• A (de)constructive approach to program checking

  2008cites this paper
• Linearity Testing/Testing Hadamard Codes

  2008cites this paper
• Derandomizing Graph Tests for Homomorphism

  2008cites this paper
• Quantum Property Testing of Group Solvability

  2007cites this paper
• 2 KEY RESULTS

  2007cites this paper
• Classical and quantum algorithms for algebraic problems

  2007cites this paper
• Local List Decoding of Homomorphisms by Elena Grigorescu

  2007cites this paper
• Error correcting codes: local testing, list decoding, and applications

  2007cites this paper
• Local Decoding and Testing for Homomorphisms

  2006cites this paper
• Quantum versus Classical Proofs and Advice

  2006cites this paper
• Quantum Property Testing for Solvable Groups

  2006cites this paper
• Local List Decoding of Homomorphisms

  2006cites this paper
• A combinatorial characterization of the testable graph properties: it's all about regularity

  2006cites this paper
• A Combinatorial Characterization of the Testable Graph Properties : It ’ s All About Regularity Extended Abstract + Appendix

  2006cites this paper
• Efficient testing of groups

  2005cites this paper