Lecture 5:3/3 - Utilizing Randomness in Computer Science
A lecture by Nicolas Schabanel at MPRI Paris Master of Computer Science (Université Paris Diderot) on January 26, 2011, from 16:15 to 19:15, focusing on the concept of guessing through sampling and its applications.
🔥 Related Trending Topics
LIVE TRENDSThis video may be related to current global trending topics. Click any trend to explore more videos about what's hot right now!
THIS VIDEO IS TRENDING!
This video is currently trending in Thailand under the topic 'สภาพอากาศ'.
About this video
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
Video Information
Views
37
Total views since publication
Duration
48:11
Video length
Published
Jan 31, 2011
Release date