Paper Info
Title
Guest column: algebraic construction of projection PCPs
Abstract
In a projection PCP, also known as Label-Cover, the verifier makes two queries to the proof, and the answer to the first query determines at most one satisfying answer to the second query. Projection PCPs with low error probability are the basis of most NP-hardness of approximation results known today. In this essay we outline a construction of a projection PCP with low error and low blow-up. This yields sharp approximation thresholds and tight time lower bounds for approximation of a variety of problems, under an assumption on the time required for solving certain NP-hard problems exactly. The approach of the construction is algebraic, and it includes components such as low error, randomness-efficient low degree testing and composition of projection PCPs.
Year
DOI
Venue
2012
10.1145/2160649.2160669
SIGACT News
Keywords
Field
DocType
algebraic construction,randomness-efficient low degree testing,low error probability,projection pcps,yields sharp approximation threshold,projection pcp,approximation result,low error,tight time,guest column,satisfying answer,low blow-up,lower bound,np hard problem,hardness of approximation,satisfiability,error probability
Combinatorics,Algebraic number,Computer science,Algebraic construction,Probability of error
Journal
Volume
Issue
Citations 
43
1
0
PageRank 
References 
Authors
0.34
22
1
Name
Order
Citations
PageRank
Dana Moshkovitz136819.14