School of Mathematics

Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers

Toniann Pitassi
University of Toronto; Visiting Professor, School of Mathematics
March 2, 2020
In this talk I will discuss the Sunflower Lemma and similar lemmas that prove (in various contexts) that a set/distribution can be partitioned into a structured part and a "random-looking" part. I will introduce communication complexity as a key model for understanding computation and more generally for reasoning about information bottlenecks.

Preference Modeling with Context-Dependent Salient Features

Laura Balzano
University of Michigan; Member, School of Mathematics
February 27, 2020
This talk considers the preference modeling problem and addresses the fact that pairwise comparison data often reflects irrational choice, e.g. intransitivity. Our key observation is that two items compared in isolation from other items may be compared based on only a salient subset of features. Formalizing this idea, I will introduce our proposal for a “salient feature preference model” and discuss sample complexity results for learning the parameters of our model and the underlying ranking with maximum likelihood estimation.

Is the variety of singular tuples of matrices a null cone?

Viswambhara Makam
February 25, 2020

The following multi-determinantal algebraic variety plays an important role in algebra and computational complexity theory: SING_{n,m}, consisting of all m-tuples of n x n complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING_{n,m} will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation. <br>

Learning from Multiple Biased Sources

Clayton Scott
University of Michigan
February 25, 2020
When high-quality labeled training data are unavailable, an alternative is to learn from training sources that are biased in some way. This talk will cover my group’s recent work on three problems where a learner has access to multiple biased sources. First, we consider the problem of classification given multiple training data sets corrupted by label noise, and describe a weighted empirical risk minimization strategy where the weights are optimized according to the degree of corruption of each source.

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Lijie Chen
Massachusetts Institute of Technology
February 24, 2020

We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2] circuits. As a straightforward application, we obtain an infinitely often non-deterministic pseudorandom generator for poly-size ACC^0 circuits with seed length 2^{log^eps n}, for all eps > 0.

Direct and dual Information Bottleneck frameworks for Deep Learning

Tali Tishby
The Hebrew University of Jerusalem
February 24, 2020

The Information Bottleneck (IB) is an information theoretic framework for optimal representation learning. It stems from the problem of finding minimal sufficient statistics in supervised learning, but has insightful implications for Deep Learning. In particular, its the only theory that gives concrete predictions on the different representations in each layer and their potential computational benefit. I will review the theory and its new version, the dual Information Bottleneck, related to the variational Information Bottleneck which is gaining practical popularity.

Classification of n-component links with Khovanov homology of rank 2^n

Boyu Zhang
February 24, 2020

Suppose L is a link with n components and the rank of Kh(L;Z/2) is 2^n, we show that L can be obtained by disjoint unions and connected sums of Hopf links and unknots. This result gives a positive answer to a question asked by Batson-Seed, and generalizes the unlink detection theorem of Khovanov homology by Hedden-Ni and Batson-Seed. The proof relies on a new excision formula for the singular instanton Floer homology introduced by Kronheimer and Mrowka.

This is joint work with Yi Xie.