Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Approximating the edit distance to within a constant factor in truly subquadratic time.

Mike Saks
Rutgers University
October 22, 2018
Edit distance is a widely used measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a classical dynamic programming algorithm that runs in quadratic time.

Asymptotic spectra and their applications II

Jeroen Zuiddam
Member, School of Mathematics
October 16, 2018
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.

Asymptotic spectra and their applications I

Jeroen Zuiddam
Member, School of Mathematics
October 9, 2018
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.

Tensor rank

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
October 2, 2018
Tensors occur throughout mathematics. Their rank, defined in analogy with matrix rank, is however much more poorly understood, both from a structural and algorithmic viewpoints.

Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem.

Ehud Friedgut
The Weizmann Institute of Science
September 24, 2018

The EKR theorem, which is the cornerstone of extremal combinatorics, characterizes maximal intersecting families of sets. Its setting fixes a ground set of size n, and then studies the size and structure of intersecting families of subsets of fixed size k. A setting which many might consider no less natural, is considering the Boolean lattice of all subsets of {1,...,n} endowed with a product measure, and studying the structure and measure of maximal intersecting families.