# Computer Science and Discrete Mathematics (CSDM)

### Making Proofs More Constructive, and Algorithms Less Random

Oliver Korten

central topic in the theory of computation is derandomization: say we have an algorithm which flips coins to achieve some goal, and succeeds with high probability. Can we transform this algorithm into a deterministic procedure, while maintaining...

### Graphs as geometric objects

Nathan Linial

It may seem quite obvious that graphs carry a lot of geometric structure.  Don't we learn in algorithm classes how to solve all-pairs-shortest-paths, minimum spanning trees etc.?  However, in this talk, I will try to impress on you the idea that...

### Association schemes and codes II: Completeness of the hierarchy of high-order Hamming schemes

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). One of the main methods...

### A Proof of the Kahn-Kalai Conjecture

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas.  In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is...

### Association schemes and codes I: The Delsarte linear program

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). On the existential side...

### Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs

Kunal Mittal

Understanding the behavior of multi-player (multi-prover) games under parallel repetition is an important problem in theoretical computer science.

In a k-player game G, a referee chooses questions (x1,...,xk) from a (publicly known)...

### A Tutorial on Gaussian Elimination

Gaussian elimination is one of the oldest and most well-known algorithms for solving a linear system. In this talk, we give a basic, yet thorough overview of the algorithm, its variants, and standard error and conditioning estimates. In addition, a...

### Set Chasing, with an application to online shortest path

Sébastien Bubeck

Since the late 19th century, mathematicians have realized the importance and generality of selection problems: given a collection of sets, select an element in each set, possibly in a nice” way.  Of particular importance in computer science is the...

### Multi-group fairness, loss minimization and indistinguishability

Parikshit Gopalan

Training a predictor to minimize a loss function fixed in advance is the dominant paradigm in machine learning. However, loss minimization by itself might not guarantee desiderata like fairness and accuracy that one could reasonably expect from a...

### A magnetic interpretation of the nodal count on graphs

The study of nodal sets, i.e. zero sets of eigenfunctions, on geometric objects can be traced back to De Vinci, Galileo, Hook, and Chladni. Today it is a central subject of spectral geometry. Sturm (1836) showed that the n-th eigenfunction of the...