Seminars

Oct
07
2013

Computer Science/Discrete Mathematics Seminar I

Stanley-Wilf limits are typically exponential
Jacob Fox
11:15am|S-101

For a permutation \(p\), let \(S_n(p)\) be the number of permutations on \(n\) letters avoiding \(p\). Stanley and Wilf conjectured that, for each permutation \(p\), \(S_n(p)^{1/n}\) tends to a finite limit \(L(p)\). Marcus and Tardos proved the...

Oct
01
2013

Computer Science/Discrete Mathematics Seminar II

Small set expander flows
10:30am|S-101

A common way for lower bounding the expansion of a graph is by looking the second smallest eigenvalue of its Laplacian matrix. Also known as the easy direction of Cheeger's inequality, this bound becomes too weak when the expansion is \(o(1)\). In...

Sep
30
2013

Computer Science/Discrete Mathematics Seminar I

Some provable bounds for deep learning
11:15am|S-101

Deep learning, a modern version of neural nets, is increasingly seen as a promising way to implement AI tasks such as speech recognition and image recognition. Most current algorithms are heuristic and have no provable guarantees. This talk will...

Sep
24
2013

Computer Science/Discrete Mathematics Seminar II

Finite Field Restriction Estimates
10:30am|S-101

The Kakeya and restriction conjectures are two of the central open problems in Euclidean Fourier analysis (with the second logically implying the first, and progress on the first typically implying progress on the second). Both of these have...

Sep
23
2013

Computer Science/Discrete Mathematics Seminar I

Using the DFS Algorithm for Finding Long Paths in Random and Pseudo-Random Graphs
11:15am|S-101

The Depth First Search (DFS) algorithm is one of the most standard graph exploration algorithms, used normally to find the connected components of an input graph. Though perhaps less popular than its sister algorithm, Breadth First Search (BFS), the...