Inapproximability results for equations over infinite groups

DOI10.1016/j.tcs.2010.03.010zbMath1203.68054OpenAlexW2077188862WikidataQ57439771 ScholiaQ57439771MaRDI QIDQ974745

Dengpan Yin, Wenbin Chen, Zhengzhang Chen

Publication date: 7 June 2010

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

Full work available at URL: http://www.lib.ncsu.edu/resolver/1840.2/2407

zbMATH Keywords

optimizationcomputational complexitygroupsapproximationcyclic groupsinfinite groupsNP-hardnessprobabilistically checkable proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algebraic geometry over groups; equations over groups (20F70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate solution of NP optimization problems
• On solutions of Equations in symmetric groups
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A threshold of ln n for approximating set cover
• A PCP characterization of NP with optimal amortized query complexity
• The importance of being biased
• On the theory of equations in finite groups
• Interactive proofs and the hardness of approximating cliques
• A Parallel Repetition Theorem
• The Poset of Conjugacy Classes and Decomposition of Products in the Symmetric Group
• Some optimal inapproximability results