# Seminars

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar I

A planar set that contains a unit segment in every direction is called a Kakeya set. These sets have been studied intensively in geometric measure theory and harmonic analysis since the work of Besicovich (1919); we find a new connection to game...

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar I

How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive...

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar I

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental...

### Computer Science/Discrete Mathematics Seminar II

The P != NP conjecture doesn't tell us what runtime is needed to solve NP-hard problems like 3-SAT and Hamiltonian Path. While some clever algorithms are known, they all require exponential time, and some researchers suspect that this is unavoidable...

### Computer Science/Discrete Mathematics Seminar I

There has been substantial progress on algorithmic versions and generalizations of the Lovasz Local Lemma recently, with some of the main ideas getting simplified as well. I will survey some of the main ideas of Moser & Tardos, Pegden, and David...

### Computer Science/Discrete Mathematics Seminar II

Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to...