[Lecture 5:1/3] Using Randomness in Computer Science
Nicolas Schabanel
2011-01-31
Views 81
Lecture @ MPRI Paris Master of Computer Science (Université Paris Diderot) by Nicolas Schabanel
Jan 26, 2011 - 16:15-19:15 - Guessing by sampling 2
• Application of linearity testing and self-correcting: NP is in PCP(poly(n),1)
- QUADEQ is NP-complete
- A PCP(n^2,1)-verifier for QUADEQ
• A constant time (1+ε)-approximation for the size of a maximal matching in a constant degree graph
Jan 26, 2011 - 16:15-19:15 - Guessing by sampling 2
• Application of linearity testing and self-correcting: NP is in PCP(poly(n),1)
- QUADEQ is NP-complete
- A PCP(n^2,1)-verifier for QUADEQ
• A constant time (1+ε)-approximation for the size of a maximal matching in a constant degree graph
Report form
RELATED VIDEOS
