Seminars

The Theoretical Computer Science and Discrete Mathematics Seminars will take place every Monday at 11:15 a.m. - 12:15 p.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:

Oct
03
2022

Computer Science/Discrete Mathematics Seminar I

Relative rank and regularity
11:15am|Simonyi 101 and Remote Access

The notion of Schmidt rank/strength for a collection of m polynomials plays an important role in additive combinatorics, number theory and commutative algebra; high rank collections of polynomials are “psuedorandom”.  An arbitrary collection of...

Oct
04
2022

Computer Science/Discrete Mathematics Seminar II

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
10:30am|Simonyi Hall 101 and Remote Access

Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc.

In this talk...

Oct
10
2022

Computer Science/Discrete Mathematics Seminar I

Is your distribution in shape?
Ronitt Rubinfeld
11:15am|Simonyi 101 and Remote Access

Algorithms for understanding data generated from distributions over large discrete domains are of fundamental importance.  In this talk, we consider the sample complexity of *property testing algorithms* that seek to to distinguish whether or not an...

Oct
11
2022

Computer Science/Discrete Mathematics Seminar II

Superfast Derandomization of Interactive Proof Systems
10:30am|Simonyi Hall 101 and Remote Access

The lifeblood of interactive proof systems is randomness, without which interaction becomes redundant. Thus, a natural long-standing question is which types of proof systems can indeed be derandomized and collapsed to a single-message NP-type...

Oct
17
2022

Computer Science/Discrete Mathematics Seminar I

The Optimal Error Resilience of Interactive Communication over the Binary Alphabet
Rachel Zhang
11:15am|Simonyi 101 and Remote Access

In interactive coding, Alice and Bob wish to compute some function f of their private inputs x and y. They do this by engaging in a non-adaptive (fixed speaking order, fixed length) protocol to jointly compute f(x,y). The goal is to do this in an...