Loading...
Please wait, while we are loading the content...
Similar Documents
CSE 533 : The PCP Theorem and Hardness of Approximation ( Autumn 2005 ) Lecture 5 : PCP Theorem proof : Gap Amplification
| Content Provider | Semantic Scholar |
|---|---|
| Author | Donnell, Ryan P. O’ |
| Copyright Year | 2005 |
| Abstract | 2 Powering Stage (Sketch) 2.1 Parameter Effects In this section, we will be sketchy about some details. Entering the powering stage, we have an input constraint graph denoted (G, C). G is an a (n, d, λ)-expander, with λ < d universal constants, and the constraints are over some fixed constant alphabet Σ = Σ0. Our goal is to produce a new constraint graph (G′, C ′) with a larger gap. We will denote parameters of (G, C) (e.g. size) in the input without a prime, and constraint graph parameters of (G′, C ′) in the output with a prime (e.g.. size′). Our goal for gap′ is as below: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://courses.cs.washington.edu/courses/cse533/05au/lecture5.pdf |
| Alternate Webpage(s) | http://courses.cs.washington.edu/courses/cse533/05au/lecture19.pdf |
| Alternate Webpage(s) | https://courses.cs.washington.edu/courses/cse533/05au/lecture19.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
