Computer Science/Discrete Mathematics

Date:
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...

Mar
07
2023

Computer Science/Discrete Mathematics Seminar II

Recent Progress in Randomness Extraction
10:30am|Simonyi Hall 101 and Remote Access

Randomness is a vital resource in computation, with many applications in areas such as cryptography, data-structures and algorithm design, sampling, distributed computing, etc. However generating truly random bits is expensive, and most sources in...