Inapproximability results for equations over infinite groups
type: Item
instance of: scholarly article
title: Inapproximability results for equations over infinite groups
zbMATH Open document ID: 1203.68054
author: Wenbin Chen
author: Dengpan Yin
author: Zhengzhang Chen
published in: Theoretical Computer Science
publication date: 2010-06-07T00:00:00Z
full work available at URL: http://www.lib.ncsu.edu/resolver/1840.2/2407
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 20B40
Mathematics Subject Classification ID: 20F70
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5717734
zbMATH Keywords: optimization
zbMATH Keywords: approximation
zbMATH Keywords: groups
zbMATH Keywords: infinite groups
zbMATH Keywords: cyclic groups
zbMATH Keywords: computational complexity
zbMATH Keywords: probabilistically checkable proofs
zbMATH Keywords: NP-hardness
MaRDI profile type: Publication
OpenAlex ID: W2077188862
Wikidata QID: Q57439771
cites work: The complexity and approximability of finding maximum feasible subsystems of linear relations
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Approximate solution of NP optimization problems
cites work: Q4536353
cites work: The Poset of Conjugacy Classes and Decomposition of Products in the Symmetric Group
cites work: The importance of being biased
cites work: Q4780798
cites work: Q2754129
cites work: Q4737146
cites work: A threshold of ln n for approximating set cover
cites work: Interactive proofs and the hardness of approximating cliques
cites work: On solutions of ''Equations in symmetric groups''
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Some optimal inapproximability results
cites work: A Parallel Repetition Theorem
cites work: A PCP characterization of NP with optimal amortized query complexity
cites work: Q4236280
cites work: On the theory of equations in finite groups
cites work: Q4250183
DBLP publication ID: journals/tcs/ChenYC10
DOI: 10.1016/J.TCS.2010.03.010
description: scientific article; zbMATH DE number 5717734