Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Asymptotic spectra and Applications II

Jeroen Zuiddam
Member, School of Mathematics
October 15, 2019

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 obtain the currently best algorithms) cannot give faster matrix multiplication algorithms. Keywords are Shannon entropy, representation theory and moment polytopes, but prior knowledge of these is not assumed.

Asymptotic spectra and Applications I

Jeroen Zuiddam
Member, School of Mathematics
October 8, 2019

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 multiplication problem, the cap set problem, the sunflower problem, the quantum entanglement problem, and the problem of efficient communication over a noisy channel. We will start from scratch.

On the possibility of an instance-based complexity theory.

Boaz Barak
Harvard University
April 15, 2019
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 can be sometimes too rigid, and lead to an discrepancy between the "real world" complexity of a problem and its theoretical analysis, as well as fail to shed light on theoretically fascinating questions arising in connections with statistical physics, machine learning, and other areas.

Collective Coin-Flipping Protocols and Influences of Coalitions

Hamed Hatami
University of McGill
April 8, 2019
The seminal result of Kahn, Kalai and Linial implies that a coalition of a small number of players can bias the outcome of a Boolean function with respect to the uniform measure. We extend this result to arbitrary product measures, by combining their argument with a completely different argument that handles very biased coordinates.

Fooling polytopes

Li-Yang Tan
Stanford University
April 1, 2019

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program. Joint work with Ryan O'Donnell and Rocco Servedio.

Factors of sparse polynomials: structural results and some algorithms

Shubhangi Saraf
Member, School of Mathematics
March 26, 2019
Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general.

    In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials when the polynomial has each variable appearing only with bounded degree. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem.

    On the Approximation Resistance of Balanced Linear Threshold Functions

    Aaron Potechin
    University of Chicago
    March 25, 2019
    Constraint satisfaction problems (CSPs) are a central topic of study in computer science. A fundamental question about CSPs is as follows. Given a CSP where each constraint has the form of some predicate P and almost all of the constraints can be satisfied, is there a randomized polynomial time algorithm which is guaranteed to do significantly better in expectation than a random assignment? If so, then we say that the predicate P is approximable. If not, then we say that P is approximation resistant.

    A Brief Tour of Proof Complexity: Lower Bounds and Open Problems

    Toniann Pitassi
    University of Toronto; Visiting Professor, School of Mathematics
    March 19, 2019

    I will give a tour of some of the key concepts and ideas in proof complexity. First, I will define all standard propositional proof systems using the sequent calculus which gives rise to a clean characterization of proofs as computationally limited two-player games. I will also define algebraic and semi-algebraic systems (SOS, IPS, Polynomial Calculus).