check
Basic Notions: Gil Kalai (HUJI) "Classical and quantum computation" | Einstein Institute of Mathematics

Basic Notions: Gil Kalai (HUJI) "Classical and quantum computation"

Date: 
Thu, 31/10/201916:00-17:15
Location: 
Ross 70
In the lecture I will describe basic notions of computational complexity:
Boolean functions, basic algorithmic tasks, Boolean circuits, P, NP, randomness, quantum circuits, noisy quantum circuits, bounded depth circuits, and more.
If time permits I will describe some (or more realistically one) mathematical challenge in the field and briefly
describe some examples (more realistically, one example) on how theory meets reality.