Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the approximation resistance of a random predicate
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2007 (English)In: Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques / [ed] Charikar, M; Reingold, O; Jansen, K; Rolim, JDP, BERLIN: SPRINGER-VERLAG BERLIN , 2007, Vol. 4627, 149-163 p.Conference paper, Published paper (Other academic)
Abstract [en]

A predicate is approximation resistant if no probabilistic polynomial time approximation algorithm can do significantly better then the naive algorithm that picks an assignment uniformly at random. Assuming that the Unique Games Conjecture is true we prove that most Boolean predicates are approximation resistant.

Place, publisher, year, edition, pages
BERLIN: SPRINGER-VERLAG BERLIN , 2007. Vol. 4627, 149-163 p.
Series
LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 4627
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-39446ISI: 000250357100011Scopus ID: 2-s2.0-38049019444ISBN: 978-3-540-74207-4 (print)OAI: oai:DiVA.org:kth-39446DiVA: diva2:440111
Conference
10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/11th International Workshop on Randomization and Computation. Princeton Univ, Princeton, NJ. AUG 20-22, 2007
Note

QC 20110911

Available from: 2011-09-12 Created: 2011-09-09 Last updated: 2013-04-05Bibliographically approved

Open Access in DiVA

No full text

Scopus

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 40 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf