Runaway Seminar: Polynomials in Computation
Jaikumar Radhakrishnan (ICTS-TIFR)
| Speaker |
Jaikumar Radhakrishnan (ICTS-TIFR)
|
|---|---|
| When |
Jan 08, 2025
from 09:00 AM to 09:45 AM |
| Where | LH-111, First Floor |
| Add event to calendar |
vCal
iCal
|
Abstract: Part 1: In the first part, we will introduce common notions in computational complexity theory, such as strings, languages, computational problems and time complexity. We will present the classes P and NP; in particular, we will interpret NP using the framework of efficient proof systems. We will end this part by showing how the algebraization of computation when combined with randomness seems to significantly enhance the power of interactive proof systems.