Derandomizing homomorphism testing in general groups

DOI10.1145/1007352.1007421zbMATH Open1192.68378OpenAlexW2022424731MaRDI QIDQ3580987FDOQ3580987

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

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

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)

Cited In (10)

• Derandomizing Homomorphism Testing in General Groups
• Title not available (Why is that?)
• 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
• Direct sum testing
• Derandomizing Graph Tests for Homomorphism
• 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
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

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)