On the hardness of approximating label-cover
type: Item
instance of: scholarly article
title: On the hardness of approximating label-cover
zbMATH Open document ID: 1178.68676
author: Irit Dinur
author: Shmuel Safra
published in: Information Processing Letters
publication date: 2009-07-09T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5576949
zbMATH Keywords: computational complexity
zbMATH Keywords: hardness of approximation
zbMATH Keywords: PCP
zbMATH Keywords: label-cover
MaRDI profile type: Publication
full work available at URL: j.ipl.2003.11.007
OpenAlex ID: W2070989606
cites work: Q4218098
cites work: PCP characterizations of NP: towards a polynomially-small error-probability
cites work: Intractability of assembly sequencing: Unit disks in the plane
cites work: Approximation algorithms for combinatorial problems
cites work: On the ratio of optimal integral and fractional covers
cites work: On the hardness of approximating minimization problems
cites work: A Parallel Repetition Theorem
cites work: Q4527015
DOI: 10.1016/J.IPL.2003.11.007
description: scientific article; zbMATH DE number 5576949