Seminars

The Theoretical Computer Science and Discrete Mathematics Seminars will take place every Monday at 10:30 a.m. - 11:30 a.m. and every Tuesday at 10:30 a.m. - 12:30 p.m. at the Institute for Advanced Study. The lectures will be held in S-101, the seminar room in Simonyi Hall, unless stated otherwise.

If you are interested in attending future seminars and are not already on our mailing list from previous years, please send an e-mail to Andrea Lass and ask to be added.

alass email

 

Upcoming Seminar Titles Include:

Nov
25
2024

Computer Science/Discrete Mathematics Seminar I

Dot-Product Proofs
Yuval Ishai
10:30am|Simonyi 101 and Remote Access

A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear...

Nov
26
2024

Computer Science/Discrete Mathematics Seminar II

Simple High Dimensional Expanders from Cayley Graphs
Yotam Dikstein
10:30am|Simonyi 101 and Remote Access

Expander graphs are a staple of theoretical computer science. These are graphs which are both sparse and well connected. They are simple to construct and modify. Therefore they are a central gadget in numerous applications in TCS and combinatorics...

Dec
02
2024

Computer Science/Discrete Mathematics Seminar I

QMA vs. QCMA and Pseudorandomness
Henry Yuen
10:30am|Simonyi 101 and Remote Access

In quantum complexity theory, QMA and QCMA represent two different generalizations of NP. Both are defined as sets of languages whose Yes instances can be efficiently checked by a quantum verifier that is given a witness. With QMA the witness can be...

Dec
09
2024

Computer Science/Discrete Mathematics Seminar I

Efficient Batch Verification: Recent Progress and Challenges
Ron Rothblum
10:30am|Simonyi 101 and Remote Access

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send the k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication? This is the...

More Events