Kyle Fox: Optimal Cuts in Surface Imbedded Graphs Wednesday, April 2, 2014  4:30pm to 5:30pm In this talk, I will describe some recent algorithmic results related to computing optimal flows and cuts in surface embedded graphs. These results are motivated by a desire to bring our understanding of efficient planar flow and cut algorithms to more general classes of graphs. 

Matt Coudron: Infinite Randomness Expansion with a Constant Number of Devices Thursday, January 23, 2014  4:00pm to 5:00pm We present a deviceindependent randomness expansion protocol, involving only a constant number of non signaling quantum devices, that achieves inﬁnite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certiﬁed randomness that is exp(−Ω 

Michael Kapralov: Approximating Matching Size from Random Streams Wednesday, December 18, 2013  4:00pm to 5:00pm We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. 

Arnab Bhattacharyya: Algorithmic regularity for polynomials and applications Friday, December 13, 2013  1:30pm to 2:30pm In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a collection of polynomials F={P1,...,Pm} to a new collection F′, so that the polynomials in F′ are “pseudorandom”. 

Ankit Sharma: Multiway Cut Monday, November 25, 2013  4:00pm to 5:00pm Multiway cut is a generalization of the mincut problem to one with more than two terminals. 

Mohammad Bavarian: Beyond XOR Games: Information causality, SzemerédiTrotter and Algebraic Variants of CHSH Wednesday, December 11, 2013  4:00pm to 5:00pm CHSH_q is the following simple twoplayer game: two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q$ without communicating to the other. The players objective is to maximize the probability that their outputs satisfy a+b=xy in F_q. 

Daniel Kane: Pseudorandom Generators for Polynomial Threshold Functions Monday, November 18, 2013  4:00pm to 5:00pm We study several developments in the construction of explicit pseudorandom generators for polynomial threshold functions, with particular emphasis on a recent result producing a seed length subpolynomial in the error parameter. 

Thomas Steinke: Pseudorandomness for Regular Branching Programs via Fourier Analysis Wednesday, December 4, 2013  4:00pm to 5:00pm We present an explicit pseudorandom generator for oblivious, readonce, permutation branching programs of constant width that can read their input bits in any order. The seed length is O(log2n), where n is the length of the branching program. 

Michael Forbes : Pseudorandomness for Multilinear ReadOnce Algebraic Branching Programs, in any Order Thursday, October 31, 2013  4:00pm to 5:00pm It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for readonce oblivious branching programs. 

Ilya Razenshteyn: Beyond LocalitySensitive Hashing Wednesday, November 20, 2013  4:00pm to 5:00pm We present a new data structure for the capproximate near neighbor problem (ANN) in the Euclidean space. For n points in Rd, our algorithm achieves Oc(dnρ) query time and Oc(n1+ρ+nd) space, where ρ≤7/(8c2)+O(1/c3)+oc(1). 