Inapproximability results for equations over finite groups

DOI10.1016/S0304-3975(03)00401-8MaRDI QIDQ1884871zbMATH OpenOpenAlexFDO

Authors 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

approximationfinite groupsNP-hardnessprobabilistically checkable proofs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086612
• Inapproximability results for equations over infinite groups
• The complexity of solving equations over finite groups
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 1834675

Cites work

• scientific article; zbMATH DE number 4002273 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• scientific article; zbMATH DE number 1318047 (Why is no real title available?)
• scientific article; zbMATH DE number 1759404 (Why is no real title available?)
• scientific article; zbMATH DE number 1833417 (Why is no real title available?)
• scientific article; zbMATH DE number 3382976 (Why is no real title available?)
• A PCP characterization of NP with optimal amortized query complexity
• A Parallel Repetition Theorem
• A threshold of ln n for approximating set cover
• Fast multiplication of large numbers
• Finite monoids and the fine structure of NC ¹
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Non-uniform automata over groups
• On solutions of Equations in symmetric groups
• On the theory of equations in finite groups
• Optimization, approximation, and complexity classes
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• The Poset of Conjugacy Classes and Decomposition of Products in the Symmetric Group
• The importance of being biased
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Towards optimal lower bounds for clique and chromatic number.

Cited in

(7)

• scientific article; zbMATH DE number 2086612 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Inapproximability results for equations over infinite groups
• Constrained inhomogeneous spherical equations: average-case hardness
• Max-3-Lin over non-abelian groups with universal factor graphs
• Equivariant unification
• Hard constraint satisfaction problems have hard gaps at location 1

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

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