Academics

  /  

Courses

  /  

Descriptions

COMP_SCI 496: Graduate Complexity

VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

Ph Ds studetns / (Undergrad/Grad permission by instructor)

Description

This graduate course is an introduction to computational complexity. Computational complexity studies the limits and capabilities of efficient computation, as well as tradeoffs between different computational resources. Except the central P versus NP question, we explore a variety of other fascinating topics, including the connection between learning theory and average-case complexity, hardness versus randomness (the BPP versus P question), and the surprising equivalence of probabilistically checkable proofs (PCPs) and the hardness of approximating certain optimization problems. 

INSTRUCTOR: Email Prof. Xue