Anshumali Shrivastava: Hashing Algorithms for Extreme Scale Machine Learning Wednesday, September 12, 2018  3:00pm to 4:00pm In this talk, I will discuss some of my recent and surprising findings on the use of hashing algorithms for largescale estimations. 

Lijie Chen: On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product Thursday, May 24, 2018  4:00pm to 5:00pm In this paper we study the (Bichromatic) Maximum Inner Product Problem (MaxIP), in which we are given sets A and B of vectors, and the goal is to find a in A and b in B maximizing inner product between a and b. 

Venkat Guruswami: Improved Bounds for Perfect Hashing Thursday, May 17, 2018  4:30pm to 5:30pm


Sitan Chen: Learning Mixtures of Product Distributions via Higher Multilinear Moments Wednesday, May 9, 2018  4:00pm to 5:00pm Abstract: Learning mixtures of k binary product distributions is a central problem in computational learning theory, but one where there are wide gaps between the best known algorithms and lower bounds (even for restricted fami 

Yuval Dagan: Detecting Correlations with Little Memory and Communication Wednesday, March 21, 2018  4:00pm to 5:00pm We study the problem of identifying correlations in multivariate data, under information constraints: Either on the amount of memory that can be used by the algorithm, or the amount of communication when the data is distributed across several machines. 

Amnon TaShma:Parity samplers and explicit, epsilonbalanced codes close to the GV Bound Thursday, February 15, 2018  4:00pm to 5:00pm I will show an explicit construction of a binary error correcting code with relative distance 1/2epsilon and relative rate about epsilon^2. This comes close to the GilbertVarshamov bound and theLP lower bound. 

Keerti Choudhary: Fault Tolerant Data Structures Tuesday, January 17, 2017  4:00pm to 5:00pm In this talk, we look at the problem of singlesourcereachability (SSR) in presence of failures of vertices and edges. In the static setting, it can be solved in O(V+E) time, for any directed graph G=(V, E). 

Jerry Li: Mixture Models, Robustness, and Sum of Squares Proofs Monday, November 5, 2018  4:00pm to Friday, November 30, 2018  5:00pm We use the Sum of Squares (SoS) method to develop a new efficient algorithm for clustering and mean estimation in wellseparated highdimensional mixture models, substantially improving upon the statistical guarantees achieved by previous efficient algorithms. 

Slobodan Mitrovic: Matchings in MPC frameworks Wednesday, November 29, 2017  4:00pm to 5:00pm The last decade has witnessed the success of a number of \emph{massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. These frameworks allow for much more local computation, compared to the classical PRAM models. 

Jiantao Jiao: Instanceoptimal learning of the total variation distance Thursday, November 16, 2017  4:00pm to 5:00pm The total variation distance (statistical distance) plays fundamental roles in statistics, machine learning, and theoretical computer science. 