Computer Science and Discrete Mathematics (CSDM)

Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc.

In this...

The notion of Schmidt rank/strength for a collection of m polynomials plays an important role in additive combinatorics, number theory and commutative algebra; high rank collections of polynomials are “psuedorandom”.  An arbitrary collection of...

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

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

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

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

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

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) distribution...

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

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