Deterministic TimeSpace Tradeoffs for kSUM Wednesday, June 8, 2016  4:00pm to 5:00pm Given a set of numbers, the kSUM problem asks for a subset of k numbers that sums to zero. 

Robust Estimators in High Dimensions without the Computational Intractability Wednesday, June 1, 2016  4:00am to 5:00am We study highdimensional 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 3SAT are known to be unsatisfiable with high probability when there at least 5N clauses. 

TALK: ZeroOne 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 signflips and coordinatepermutations), by relating this space complexity to the measureconcentration 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 superpolynomial lower bounds for deMorgan 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. 