Teaching & PhD
Doctoral program in computer and communication sciences
- Complexity classes (time, space, nondeterminism)
- Space complexity (Logspace, L vs NL)
- Boolean circuits and nonuniform computation
- Power of randomness (interactive proofs)
- Lower bounds for concrete models of computation: Decision trees, communication protocols, propositional proofs.