Derandomizing homomorphism testing in general groups

DOI10.1145/1007352.1007421MaRDI QIDQ3580987zbMATH OpenOpenAlexFDO

Authors Amir Shpilka, A. Wigderson

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007421

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Software, source code, etc. for problems pertaining to group theory (20-04)

Recommendations

• Derandomizing Homomorphism Testing in General Groups
• On the derandomization of the graph test for homomorphism over groups
• Derandomizing Graph Tests for Homomorphism
• Local Decoding and Testing for Homomorphisms
• Efficient testing of groups

Cited in

(10)

• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• Derandomizing Homomorphism Testing in General Groups
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithmic testing for dense orbits of Borel subgroups
• Derandomizing Graph Tests for Homomorphism
• Direct sum testing
• A self-tester for linear functions over the integers with an elementary proof of correctness
• On the derandomization of the graph test for homomorphism over groups

This page was built for publication: Derandomizing homomorphism testing in general groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580987)