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

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.

Date: 

Thu, 31/10/2019 - 16:00 to 17:15

Location: 

Ross 70