Algorithms and Complexity Seminar

Robust Estimators in High Dimensions without the Computational Intractability
Wednesday, June 1, 2016 - 4:00am to 5:00am

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science.

Strongly Refuting Random CSPs Below the Spectral Threshold
Wednesday, May 25, 2016 - 4:00pm to 5:00pm

Random instances of 3-SAT are known to be unsatisfiable with high probability when there at least 5N clauses.

TALK: Zero-One Laws for Sliding Windows and Universal Sketches
Tuesday, January 19, 2016 - 2:00pm to 3:00pm

Streaming algorithms serve an important role in analyzing vast amounts of data, especially when it is infeasible to store a large part of the input in memory.

Lin Yang: Streaming Symmetric Norms via Measure Concentration
Wednesday, December 16, 2015 - 4:00pm to 5:00pm
We characterize the streaming space complexity of every symmetric norm l (a norm on R^n invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of l.
Towards the KRW conjecture: Cubic Lower Bounds via Communication Complexity
Wednesday, December 9, 2015 - 4:00pm to 5:00pm

Abstract: One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas.

Generalizations of the Gate Elimination Method
Wednesday, December 2, 2015 - 4:00pm to 5:00pm

Abstract:  In this talk we consider Boolean circuits over the full binary basis. It is known that almost all Boolean functions of $n$ variables require circuits of size $\Theta(2^n/n)$.

Arnab Bhattacharyya: An Optimal Algorithm for Heavy Hitters in Insertion Streams and Related Problems
Wednesday, October 28, 2015 - 4:00pm to 5:00pm
We give the first optimal bounds for returning the heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem.
Luke Schaeffer: Classification of Reversible Bit Operations
Wednesday, October 7, 2015 - 4:00pm to 5:00pm

Abstract:  We present a complete classification of all possible sets of classical reversible gates acting on bits,in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free.

Talk: Barna Saha: Language Edit Distance and Connection to Fundamental Graph Problems
Thursday, October 8, 2015 - 4:45pm to 5:45pm

Abstract: In this presentation we will discuss two fundamental problems that generalize string edit distance computation and parsing of context free grammars.

Amir Shpilka: Reed-Muller Codes for Random Erasures and Errors
Wednesday, September 30, 2015 - 4:00pm to 5:00pm


Subscribe to Algorithms and Complexity Seminar