Computer Science/Discrete Mathematics

Date:
Apr
01
2024

Computer Science/Discrete Mathematics Seminar I

Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
Huacheng Yu
11:00am|Simonyi 101 and Remote Access

A dictionary data structure maintains a set of at most $n$ keys from the universe $[U]$ under key insertions and deletions, such that given a query $x\in[U]$, it returns if $x$ is in the set. Some variants also store values associated to the keys...

Apr
02
2024

Computer Science/Discrete Mathematics Seminar II

New Derandomized Agreement Testers
10:30am|Simonyi Hall 101 and Remote Access

Agreement testing (aka direct product testing), checks if consistent local information reveals global structure. Beyond its theoretical connections to probabilistic checkable proofs (PCPs), constructing agreement testers is a fundamental...

Apr
08
2024

Computer Science/Discrete Mathematics Seminar I

Polynomial Capacity and its Applications: To TSP and Beyond
Jonathan Leake
11:00am|Simonyi 101 and Remote Access

About 20 years ago, Gurvits developed the notion of polynomial capacity to give a simple proof of the famous van der Waerden lower bound on the permanent of a doubly stochastic matrix. Since then, similar techniques have led to various other...

Apr
09
2024

Computer Science/Discrete Mathematics Seminar II

The Method of Hypergraph Containers
Wojciech Samotij
10:30am|Simonyi Hall 101 and Remote Access

The method of hypergraph containers is a widely-applicable technique in probabilistic combinatorics. The method enables one to gain control over the independent sets of many `interesting' hypergraphs by exploiting the fact that these sets exhibit a...

Apr
15
2024

Computer Science/Discrete Mathematics Seminar I

Graphs, CSPs and Codes
Madhu Sudan
11:00am|Simonyi 101 and Remote Access

A sparsification of a structure, with respect to a class of queries, produces a compressed representation of the structure while answering every query in the class approximately correctly. The seminal example of sparsification is "graph...