Seminars

May
03
2016

Computer Science/Discrete Mathematics Seminar II

Fourier tails for Boolean functions and their applications
10:30am|S-101

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

Apr
26
2016

Computer Science/Discrete Mathematics Seminar II

Reed-Muller codes for random erasures and errors
Amir Shpilka
10:30am|S-101
Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$. Its distance is $2^{m-r}$ and so it cannot correct more than that many errors/erasures in the worst case. For random errors one may hope...
Apr
19
2016

Computer Science/Discrete Mathematics Seminar II

A characterization of functions with vanishing averages over products of disjoint sets
10:30am|S-101
We characterize all complex-valued (Lebesgue) integrable functions $f$ on $[0,1]^m$ such that $f$ vanishes when integrated over the product of $m$ measurable sets which partition $[0,1]$ and have prescribed Lebesgue measures $\\alpha_1,\\ldots,\...
Apr
05
2016

Computer Science/Discrete Mathematics Seminar II

An average-case depth hierarchy theorem for Boolean circuits II
Li-Yang Tan
10:30am|S-101

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

Apr
04
2016

Computer Science/Discrete Mathematics Seminar I

An average-case depth hierarchy theorem for Boolean circuits I
Li-Yang Tan
11:15am|S-101

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

Mar
28
2016

Computer Science/Discrete Mathematics Seminar I

A local central limit theorem for triangles in a random graph
11:15am|West Building Lecture Hall
What is the distribution of the number of triangles in the random graph $G(n, 1/2)$? It was known for a long time that this distribution obeys a central limit theorem: from the point of view of large intervals (~ standard-deviation length), the...
Mar
22
2016

Computer Science/Discrete Mathematics Seminar II

The Resolution proof system
10:30am|S-101
The Resolution proof system is perhaps the simplest and most universally used in verification system and automated theorem proving. It was introduced by Davis and Putnam in 1960. The study of its efficiency, both in terms of proof length of natural...
Mar
21
2016

Computer Science/Discrete Mathematics Seminar I

Polynomial-time tensor decompositions via sum-of-squares
Tengyu Ma
11:15am|S-101

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

Mar
15
2016

Computer Science/Discrete Mathematics Seminar II

Proof complexity - an introduction
10:30am|S-101

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

Mar
14
2016

Computer Science/Discrete Mathematics Seminar I

Lower bounds for homogeneous depth-5 arithmetic circuits over finite fields
Mrinal Kumar
11:15am|S-101
The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth-4 arithmetic circuits. Even though these results seem to come close to resolving the VP vs VNP question, it seems likely that the...