Inapproximability results for equations over infinite groups
DOI10.1016/J.TCS.2010.03.010zbMATH Open1203.68054DBLPjournals/tcs/ChenYC10OpenAlexW2077188862WikidataQ57439771 ScholiaQ57439771MaRDI QIDQ974745FDOQ974745
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
Recommendations
optimizationcomputational complexitygroupsapproximationinfinite groupsNP-hardnessprobabilistically checkable proofscyclic groups
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
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Interactive proofs and the hardness of approximating cliques
- Some optimal inapproximability results
- The Poset of Conjugacy Classes and Decomposition of Products in the Symmetric Group
- Approximate solution of NP optimization problems
- A PCP characterization of NP with optimal amortized query complexity
- A Parallel Repetition Theorem
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- The importance of being biased
- On the theory of equations in finite groups
- Title not available (Why is that?)
- On solutions of Equations in symmetric groups
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (2)
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)
