Inapproximability results for equations over infinite groups

DOI10.1016/J.TCS.2010.03.010MaRDI QIDQ974745zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Wenbin Chen, Dengpan Yin, 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 complexitygroupsapproximationinfinite groupsNP-hardnessprobabilistically checkable proofscyclic groups

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1670809 (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 1759404 (Why is no real title available?)
• scientific article; zbMATH DE number 2086612 (Why is no real title available?)
• scientific article; zbMATH DE number 1833417 (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
• Approximate solution of NP optimization problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Interactive proofs and the hardness of approximating cliques
• On solutions of Equations in symmetric groups
• On the theory of equations in finite groups
• Some optimal inapproximability results
• The Poset of Conjugacy Classes and Decomposition of Products in the Symmetric Group
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The importance of being biased

Cited in

(3)

• Mathematical Foundations of Computer Science 2005
• Inapproximability results for equations over finite groups
• scientific article; zbMATH DE number 2086612 (Why is no real title available?)

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

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