Mathematics of Information
4:00-5:00 pm in Annenberg 314
(except where otherwise noted)
October 24, 2017
Derandomization: Polynomial Identity Testing and Isolation Lemma(Part 1 of 2)
Derandomization is one of the central questions in theory of computing. The question asks if all problems with efficient randomized algorithms also have deterministic algorithms with comparable time complexity. The question also has connections with circuit lower bounds.
One of the randomized solutions for PIT goes via the Isolation Lemma.
The lemma states that given a family F of subsets of set E, assigning random weights to the elements of E ensures there is a unique minimum weight set in the family F.
Derandomizing the Isolation Lemma means constructing such weights in a deterministic way. One of the many applications of PIT and Isolation Lemma is a randomized parallel algorithm for the graph matching problem.
Recently, we gave a geometric approach for derandomizing the Isolation Lemma. Applying it to a specific case gives a deterministic parallel algorithm for bipartite matching.
The first talk will give an introduction to these topics. In the second talk, I will describe our isolation approach which works for totally unimodular polytopes. I will end with an open question about short vectors in lattices, which tells in which all settings our isolation approach works.
October 31, 2017
Derandomization: Polynomial Identity Testing and Isolation Lemma(Part 2 of 2)
November 14, 2017
From Network Coding to Sidon Spaces
Network coding is an efficient method for data transmission in networks. However, in many networks even a single hardware failure might render an entire transmission unreadable. Hence, in order to combat errors and erasures in network coding, subspace codes were introduced.
A subspace code is a family of subspaces over a finite field that intersect mutually in a small dimension. Since the set of all linear subspaces lacks a linear structure, cyclic subspace codes were defined through the natural action of the group of invertible matrices.
In this talk, several constructions of cyclic subspaces codes will be presented. A particular attention will be given to Sidon spaces, a newly defined algebraic notion, and their potential applications in post-quantum cryptography will be discussed.
November 28, 2017
Gradient coding - When coding theory and distributed computing meet
Gradient Descent, and its variants, are a popular method for solving empirical risk minimization problems in machine learning. However, if the size of the training set is large, a computational bottleneck is the computation of the gradient, and hence, it is common to distribute the training set among worker nodes. Doing this in a synchronous fashion faces yet another challenge of stragglers (i.e., slow or unavailable nodes), which might cause a considerable delay. Hence, schemes for mitigation of stragglers are essential.
It was recently shown by Tandon et al. that stragglers can be avoided by carefully assigning redundant computations to the worker nodes and coding across partial gradients, and a randomized construction for the coding matrix was given. In this talk we present a more efficient deterministic scheme by employing cyclic MDS codes over the real or complex field. In addition, we propose to replace the exact computation of the gradient with an approximate one; a technique which drastically increases the straggler tolerance, and stems from adjacency matrices of expander graphs.
December 5, 2017
December 12, 2017
CMI Faculty Lunches
December 14, 2017
January 11, 2018
February 8, 2018
March 8, 2018
April 12, 2018
May 10, 2018