Algorithms and Complexity Seminars

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 large-scale 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 (Max-IP), 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 Ta-Shma:Parity samplers and explicit, epsilon-balanced 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/2-epsilon and relative rate about epsilon^2. This comes close to the Gilbert-Varshamov 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 single-source-reachability (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 well-separated high-dimensional 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: Instance-optimal 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.

Pages

Subscribe to Algorithms and Complexity Seminars