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.