2022-2023 Seminars

Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree...

Suppose we are given matchings $M_1,....,M_N$ of size t in some r-uniform hypergraph, and let us think of each matching having a different color. How large does N need to be (in terms of t and r) such that we can always find a rainbow matching of...

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud...

In this talk, I'll first give a broad overview of the history of combinatorial auctions within TCS, and then discuss some recent results.

Combinatorial auctions center around the following problem: There is a set M of m items, and N of n bidders...

Let K be a convex body in $R^n$. In some cases (say when K is a cube), we can tile $R^n$ using translates of K. However, in general (say when K is a ball) this is impossible. Nevertheless, we show that one can always cover space "smoothly" using...

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges...

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that matrices can be multiplied in nearly-linear time. If true, this conjecture would yield similarly-fast...

A Locally Decodable Codes (LDC) is an error correcting code which allows the decoding of a single message symbol from a few queries to a possibly corrupted encoding.  LDCs can be constructed, for example, from low degree polynomials over a finite...

Over a high-dimensional vector space $F_p^n $over a fixed finite field $F_p$, the inverse theorem for the Gowers norm asserts that a bounded function f on this space that has a large Gowers $U^{k+1}$ norm, must necessarily correlate with a phase...

A seminal result in learning theory characterizes the PAC learnability of binary classes through the VC dimension. Extending this characterization to the general multiclass setting has been open since the late 1980s.

We resolve this problem by...