Upcoming Events
Mathematics of Information seminar (CS286)
4:005:00 pm in Annenberg 314 (except where otherwise noted)
October 24, 2017
Rohit Gurjar
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
Rohit Gurjar
Derandomization: Polynomial Identity Testing and Isolation Lemma (Part 2 of 2)
November 14, 2017
Netanel Raviv
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 postquantum cryptography will be discussed.
November 28, 2017
Netanel Raviv
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.
February 13, 2018
Richard Kueng
Spherical tdesigns as a general purpose tool for partial derandomization (Part 1 of 2)
Spherical tdesigns are ensembles of vectors which reproduce the first 2t moments of the uniform distribution on the complex unit sphere. As such they provide notions of "evenly distributed" sets of vectors that range from tight frames (t=1) to the full sphere (as t approaches infinity). Such configurations have been studied in algebraic combinatorics, coding theory, and quantum information. Similar to twise independent functions, they are a general purpose tool for (partial) derandomization. To emphasize this, we will consider two applications:
i.) Optimally distinguishing quantum states: The optimal probability of correctly distinguishing two (biased) coins with a single coin toss is proportional to the total variational distance. This classical result has a quantum mechanical analogue: the optimal probability of correctly distinguishing two quantum states is proportional to the trace distance. In contrast to the classical result, achieving this bound requires choosing a particular type of quantum measurement that depends on the states to be distinguished. It is therefore natural to ask which universal quantum measurements are optimal in the sense that they perform well at distinguishing arbitrary pairs of quantum states. We will review pioneering work by Ambainis and Emerson who showed that spherical 4designs have this property.
ii.) Phase retrieval: The problem of retrieving phase information from amplitude measurements alone has appeared in many scientific disciplines over the last century. More recently, several new recovery algorithms have been proposed and rigorous performance guarantees have been established. The strongest results of this type are probabilistic in nature and require measurements that are chosen uniformly from the complex unit sphere. We will show that this result can be (partially) derandomized: choosing measurements independently from a spherical 4design already allows for drawing similar conclusions.
From a practical point of view, the usefulness of these concepts hinges on the availability of constructions for spherical designs. Despite nonconstructive existence proofs and approximate randomized constructions, exact families of spherical tdesigns are notoriously difficult to find. We will present a family of structured vectors that form spherical 3designs. These vectors, called stabilizer states, have a rich combinatorial structure and are ubiquitous in quantum information theory. What is more, they perform almost as well as spherical 4designs in various applications.
February 20, 2018
Richard Kueng
Spherical tdesigns as a general purpose tool for partial derandomization (Part 2 of 2)


201718 CMI Faculty Lunches
by invitation
December 14, 2017
Markus Meister
Neural Computations for Vision
The task of the human visual system is to extract from the onslaught of raw image information (~1 Gbit/s) the little knowledge that really matters to us (~20 bit/s). I will discuss what we are learning about this process in the early neural circuits of the visual system, and how the resulting insights can help devise prostheses for the blind.
January 11, 2018
Laura Doval
Whether or not to open Pandora's box
I study a singleagent sequential search problem as in Weitzman, "Optimal search for the best alternative." Contrary to Weitzman, conditional on stopping, the agent may take any uninspected box without first inspecting its contents. This introduces a new tradeoff. By taking a box without inspection, the agent saves on its inspection costs. However, by inspecting it, he may discover that its contents are lower than he anticipated. I identify sufficient conditions on the parameters of the environment under which I characterize the optimal policy. Both the order in which boxes are inspected and the stopping rule may differ from that in Weitzman's model. Moreover, I provide additional results that partially characterize the optimal policy when these conditions
fail.
February 8, 2018
Lior Pachter
MI in singlecell genomics
March 8, 2018
Federico Echenique
Markets equilibrium, fairness, and fractional allocation of discrete resources
We propose to use endowments as a policy instrument in market design. Endow ments give agents the right to enjoy certain resources. For example in school choice, one can ensure that lowincome families have a shot at highquality schools by endowing them with a chance of admission.
We propose to use endowments as a policy instrument in market design. Endow ments give agents the right to enjoy certain resources. For example in school choice, one can ensure that lowincome families have a shot at highquality schools by endowing them with a chance of admission.
For the CMI lunch, I will introduce the model of competitive markets as a method to probabilistically allocate discrete resources, and point out some of limitations of competitive equilibria in this model. Then I will propose a new notion of fairness, trying to make sense of fairness among unequal agents, and a new competitive solution. Time permitting I'll outline some of the main results.
April 12, 2018
Richard Murray
Rapprochement Between Formal Methods and Control Theory
In computer science, specifically software engineering and hardware engineering, formal methods are a particular kind of mathematicallybased techniques for the specification, development, and verification of software and hardware systems. The field of control provides the principles and methods used to design engineering systems that maintain desirable performance by automatically adapting to changes in the environment. It turns out that both of these fields have been solving similar problems using different mathematical languages for the past 50 years or so. Mani Chandy tried to explain this to me starting about 20 years go, but it took me about 15 years to figure out what he was talking about and I've only come to truly appreciate the connections in the last five years or so (since the last time I gave a CMI talk on this subject). It turns out the ideas are pretty intuitive, so in this talk I will attempt to explain what I have learned to whoever shows up in about 45 minutes or so. We'll see how it goes. I promise not to mention sparsity, matrix factorization, or mutual information, and I will try to avoid too much use of boxes, diamonds, and double turnstyles.
May 10, 2018
Omer Tamuz
The FurstenbergPoisson Boundary of Random Walks on Groups
The FurstenbergPoisson boundary of a random walk on a group captures the uncertainty in the walk's asymptotic behavior. I will define the boundary, give some examples, and explain how it reflects algebraic and geometric properties of groups, allowing us to study them using probabilistic tools. I will also present a recent result with Joshua Frisch, Yair Hartman and Pooya Vahidi Ferdowsi, which resolved a longstanding problem by giving a simple algebraic characterization of all groups for which there exists a random walk with a nontrivial boundary.
