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:

Feb
13
2023

Computer Science/Discrete Mathematics Seminar I

Efficient Verification of Computation on Untrusted Platforms
Yael Kalai
11:15am|Simonyi 101 and Remote Access

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud...

Feb
14
2023

Computer Science/Discrete Mathematics Seminar II

Rainbow Matchings in Hypergraphs
10:30am|Simonyi Hall 101 and Remote Access

Suppose we are given matchings $M_1,....,M_N$ of size t in some r-uniform hypergraph, and let us think of each matching having a different color. How large does N need to be (in terms of t and r) such that we can always find a rainbow matching of...

Feb
20
2023

Computer Science/Discrete Mathematics Seminar I

Induced Subgraphs and Tree Decompositions
11:15am|Simonyi 101 and Remote Access

Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree...

Mar
06
2023

Computer Science/Discrete Mathematics Seminar I

Two (More) Algorithms for Set Cover
Anupam Gupta
11:15am|Simonyi 101 and Remote Access

In the minimum cost set cover problem, a set system is given as input, and the goal is to find a collection of sets with minimum cost whose union covers the universe. This NP-hard problem has long been known to admit logarithmic approximations...