Tuesday, April 19, 2016 - 1:25pm - 2:25pm
Katherine Kinnaird (Macalester College)
We present aligned hierarchies, a low-dimensional representation for sequential data streams. The aligned hierarchies encode all hierarchical decompositions of repeated elements from a high-dimensional and noisy sequential data stream in one object. These aligned hierarchies can be embedded into a classification space with a natural notion of distance. We motivate our discussion through the lens of Music Information Retrieval (MIR), constructing aligned hierarchies by finding, encoding, and synthesizing all repeated structure present in a song.
Monday, May 16, 2016 - 9:00am - 9:50am
Ankur Moitra (Massachusetts Institute of Technology)
Planted clique is a basic problem in average-case analysis that has found numerous applications, including in discovering motifs in biological networks, computing the best Nash equilibrium, property testing, sparse PCA, compressed sensing, cryptography and mathematical finance. In this work, we prove a nearly optimal lower bound against the Sum-of-Squares hierarchy for it. Previously, it was possible that the Sum-of-Squares hierarchy might be able to find planted cliques of size $n^{epsilon}$ for any $epsilon > 0$ in polynomial time.
Subscribe to RSS - Hierarchies