Computer Science and Discrete Mathematics (CSDM)

In this work, we exploit the ill-posedness of linear inverse
problems to design algoithms to release differentially private data or
measurements of the physical system. We discuss the spectral
requirements on a matrix such that only a small amount of...

Extremal set theory typically asks for the largest collection of sets satisfying certain constraints. In the first talk of these series, I'll cover some of the classical results and methods in extremal set theory. In particular, I'll cover the...

A (k,m)-Furstenberg set K in F^n, where F is a finite field, is a set such that any k-dimensional subspace of F^n can be shifted so that it intersects K in at least m points. Such sets generalize in a natural way finite field Kakeya sets (in which k...

Scaling problems, such as operator scaling and tensor scaling, have recently found several applications in diverse areas of math and CS. They have been used to give efficient algorithms for non-commutative rational identity testing, compute the...

The problem of learning arithmetic circuits is the following: given a polynomial as a black box that is promised to have a small arithmetic circuit computing it, can we find this arithmetic circuit? This problem is hard in the worst case and so...

In this second lecture in my series on asymptotic spectra we will focus on one application: the matrix multiplication problem. We will use the asymptotic spectrum of tensors to prove that a very general method (that includes the methods used to...

The choiceless computation model of Blass, Gurevich and Shelah (1999, 2002) is an algorithmic framework for computing isomorphism-invariant properties of unordered structures. Machines in this model have the power of parallel execution, but lack...

The first lecture in this series is an introduction to the theory of asymptotic spectra. This theory describes asymptotic behavior of basic objects in mathematics like graphs and tensors. Example applications that we will see are the matrix...

A sunflower with $r$ petals is a collection of $r$ sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least...

Worst-case analysis of algorithms has been the central method of theoretical computer science for the last 60 years, leading to great discoveries in algorithm design and a beautiful theory of computational hardness. However, worst-case analysis...