Past Events

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We give an explicit binary tree code with constant

I will discuss recent advances in the technique we call "the method of interlacing polynomials'' --- a technique that uses polynomials as a way to prove existence theorems in linear

In principle it is easy to find a solution of a Boolean formula--just try out all possibilities. In practice however, the problem is not so simple, because the number of

Motivated by machine learning problems over large data sets and distributed optimization over networks, we consider the problem of minimizing the sum of a large number of convex component functions.

It is common to represent data in the form of a matrix, and a large set of data analytic tasks rely on obtaining a low-rank approximation of the data matrix.

In honor of the Super Bowl, I will be talking about the classic Angel problem by Conway. (Feel free to decide for yourself which team is the Devil). This problem

Let a(n, p), where 0 < p < 1, be the number of tilings of n-by-n square with dimers and monomers, such that dimers occupy approximately p of the area.

I'll talk about a few different simple-looking problems in percolation and random walks that all ask for the same innocuous thing-- monotone behaviour. I'll also say a few words about

The container theorem allows us to analyze the independent sets of a hypergraph by collecting each independent set in a small number of containers. This technique has led to many

Ellis and Narayanan showed, verifying a conjecture of Frankl, that any 3-wise intersecting family of subsets of {1,2,...,n} admitting a transitive automorphism group has cardinality o(2^n), while a construction of

The lecture has 3 sections: (1) Given functions u,f:D → D ⊂ ℝ , if u(x)=1-f(x)/f'(x) for all x in D , we call f the inverse Newton transform of

For years, there has been discussion about physical security in the maritime transportation system (MTS). That discussion has led to standards, regulations, etc. In recent years, there has been an

Consider a dense Erdos--Renyi random graph $G(n,p)$ with $p>0$ fixed. Can we partition the graph into two nonempty sets such that every vertex has more neighbors in its own set

I will revisit the (super classical) notion of recurrence and expected return time for an example of a classical walk and then define these notions for (unitary) quantum walks. We

This talk reports the results of a research project with undergraduate student Renna Yi this past Summer. What was meant as a warm-up problem for understanding what "Steve Smale's 7th

A lot of well-studied problems in CS Theory are about making “sketches” of graphs that occupy much less space than the graph itself, but where the shortest path distances of

The chromatic number of the Kneser graph (conjectured in 1955) was a seemingly difficult open problem until it was solved by Lovasz in 1978 by using quite non-trivial ideas from

Probability theory rests on seemingly firm axioms, yet simple questions continue to confound philosophers and intrigue the public. We'll examine some of these questions and try to determine whether they

This presentation describes joint work with Ian Mertz and Yuanhao Wei