# Computer Science and Discrete Mathematics (CSDM)

### 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...

### Many Nodal Domains in Random Regular Graphs

A nodal domain of a Laplacian eigenvector of a graph is a maximal connected component where it does not change sign.  Sparse random regular graphs have been proposed as discrete toy models of "quantum chaos", and it has accordingly been conjectured...

### The absorption method, and an application to an old Ramsey problem

The absorption method is a very simple yet surprisingly powerful idea coming from extremal combinatorics which allows one to convert asymptotic results into exact ones. It has produced a remarkable number of success stories in recent years with...