# Algorithms and Complexity Seminar

 Deterministic Time-Space Tradeoffs for k-SUMWednesday, June 8, 2016 - 4:00pm to 5:00pmGiven a set of numbers, the k-SUM problem asks for a subset of k numbers that sums to zero. Robust Estimators in High Dimensions without the Computational IntractabilityWednesday, June 1, 2016 - 4:00am to 5:00amWe 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 ThresholdWednesday, May 25, 2016 - 4:00pm to 5:00pmRandom 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 SketchesTuesday, January 19, 2016 - 2:00pm to 3:00pmStreaming 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:00pmWe 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 ComplexityWednesday, December 9, 2015 - 4:00pm to 5:00pmAbstract: 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 MethodWednesday, December 2, 2015 - 4:00pm to 5:00pmAbstract:  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 ProblemsWednesday, October 28, 2015 - 4:00pm to 5:00pmWe 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 OperationsWednesday, October 7, 2015 - 4:00pm to 5:00pmAbstract:  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 ProblemsThursday, October 8, 2015 - 4:45pm to 5:45pmAbstract: In this presentation we will discuss two fundamental problems that generalize string edit distance computation and parsing of context free grammars.