2019-2020 Seminars

We will discuss some of the basic principles and results in the study of Boolean-valued functions over the discrete hypercube using discrete Fourier analysis. In particular, we will talk about basic concepts, the hypercontractive inequality and the...

Given a separation oracle for a convex set $K \subset \mathbb{R}^n$ that is contained in a box of radius $R$, the goal is to either compute a point in $K$ or prove that $K$ does not contain a ball of radius $\epsilon$. We propose a new cutting plane...

We say a probability distribution µ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if µ is spectrally independent, then the...

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...

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...

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...

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]...

Protein-based drugs are becoming some of the most important drugs of the XXI century. The typical mechanism of action of these drugs is a strong protein-protein interaction (PPI) between surfaces with complementary geometry and chemistry. Over the...

This (mostly expository) talk will be about invariant theory viewed through the lens of computational complexity. Invariant theory is the study of symmetries, captured by group actions, by polynomials that are “invariant.” Invariant theory has had a...

We recently proposed the "Lottery Ticket Hypothesis," which conjectures that the dense neural networks we typically train have much smaller subnetworks capable of training in isolation to the same accuracy starting from the original initialization...