# Seminars

### Computer Science/Discrete Mathematics Seminar II

The discrete Fourier transform is a widely used tool in the analysis of Boolean functions. One can view the Fourier transform of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ as a distribution over sets $S \subseteq [n]$. The Fourier-tail at level $k...

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar II

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a...

### Computer Science/Discrete Mathematics Seminar I

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \\geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a...

### Computer Science/Discrete Mathematics Seminar I

### Computer Science/Discrete Mathematics Seminar II

### Computer Science/Discrete Mathematics Seminar I

Tensor decompositions have been the key algorithmic components in provable learning of a wide range of hidden variable models such as topic models, Gaussian mixture models, independent component analysis, dictionary learning. Despite its success...

### Computer Science/Discrete Mathematics Seminar II

Proof systems pervade all areas of mathematics (often in disguise: e.g. Reidemeister moves is a sound and complete proof system for proving the equivalence of knots given by their diagrams). Proof complexity seeks to to understand the minimal...