Inapproximability results for equations over finite groups

DOI10.1016/S0304-3975(03)00401-8zbMath1056.68089OpenAlexW2124413750MaRDI QIDQ1884871

Lars Engebretsen, Jonas Holmerin, Alexander Russell

Publication date: 27 October 2004

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00401-8

zbMATH Keywords

finite groupsapproximationNP-hardnessprobabilistically checkable proofs

Mathematics Subject Classification ID

Abstract finite groups (20D99) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Equivariant unification ⋮ Max-3-Lin over non-abelian groups with universal factor graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-uniform automata over groups
• Optimization, approximation, and complexity classes
• On solutions of Equations in symmetric groups
• Towards optimal lower bounds for clique and chromatic number.
• Fast multiplication of large numbers
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• A PCP characterization of NP with optimal amortized query complexity
• The importance of being biased
• Finite monoids and the fine structure of NC ¹
• On the theory of equations in finite groups
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• The Poset of Conjugacy Classes and Decomposition of Products in the Symmetric Group
• Some optimal inapproximability results

This page was built for publication: Inapproximability results for equations over finite groups