By Amit Sahai

From revolutionaries and spies to ordinary citizens living under repressive regimes, for centuries people have had the need to hide operational secrets. By an operational secret, we mean a secret that must be kept safe, where the secret is also used to perform ordinary tasks. For example, someone may want to keep the amount of cash she has on-hand secret, but she also needs to refer to this information when making everyday purchases. Even secrets like the location of hidden refugees under one’s protection could be an operational secret, since the holder of the secret would want to plan her ordinary movements to avoid the secret location that she is protecting. Through many clever means, people throughout history managed to protect such secrets. Essential to such protection was the refuge of the human mind, the ultimate sanctuary where secrets can be pondered and processed without fear of loss.

But what if this most basic assumption proves false? What if an adversary can read someone’s mind while she is thinking about the secret she needs to protect? Indeed, it is hard to imagine how someone can protect secrets when the inner dialogue of her mind can betray her. Fortunately, this scenario remains science fiction when applied to humanity. However, if we replace humans by computer programs, this situation is all too common. Computer programs, with inbuilt databases of sensitive information, are routinely captured by adversarial entities. These adversaries can reverse-engineer these programs and see every detail of how the programs “think” about their secrets as they perform their calculations. Furthermore, adversaries can even modify the programs to alter their behavior, in order to coax secrets out of the original computer code. Because computer programs with inbuilt operational secrets are so useful, cryptographic researchers have pondered this challenge as far back as the classic work of Diffie and Hellman in 1976. For decades, however, our ability to suitably “obfuscate” programs in order to defend against these kinds of attacks was based on unsatisfying approaches that failed to provide security against even moderately skilled adversaries.

This changed in 2013, due to the work of Garg, Gentry, Halevi, Raykova, Sahai and Waters, which gave the first sound mathematical approach to this problem. This work enabling a mathematical approach to securing software has been hailed as, “a watershed moment for cryptography,” by the Simons Foundation’s Quanta magazine, and its ramifications were a major theme of the Simons Institute program on Cryptography in Summer 2015. To illustrate why this recent advance in obfuscation has caused such a stir in the cryptographic community, let us consider an analogy with the ancient problem of sending encrypted messages.

By Benjamin Rossman and Li-Yang Tan

Computational complexity theory is the branch of computer science that studies the nature and limits of efficient computation; an overarching goal in this area is the classification of computational problems according to their inherent difficulty. One of the most intensively studied such classifications is provided by the Polynomial Hierarchy, which was introduced by Albert Meyer and Larry Stockmeyer in 1972. This hierarchy classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of levels: problems at the zeroth level are the “easiest”, and for every integer k, problems at the (k+1)-st level have logical complexity “one notch higher” than those at level k. In this vignette we describe some recent work done at the Simons Institute, in collaboration with Rocco Servedio of Columbia University, which sheds new light on the structure of this hierarchy.

The polynomial hierarchy begins at the zeroth level with the class P of problems solvable in polynomial time — the easiest problems. In theoretical computer science P captures an elegant and robust notion of computational efficiency: polynomial-time algorithms are considered efficient, and problems in P are considered tractable. Examples of fundamental problems in P include Linear Programming, Matching, and Primality. At the first level above P in the hierarchy is NP, the class of problems solvable in nondeterministic polynomial time, meaning that a “yes” answer can be verified efficiently. Well-known examples of problems in NP include the Boolean Satisfiability and Traveling Salesman problems, among countless others that arise in surprisingly diverse contexts.

Clearly P ⊆ NP, since the answer to a computational problem can be verified efficiently if it can be determined efficiently. But is the converse true? No efficient algorithms are known for the hardest problems in NP, the so-called NP-complete problems: while a “yes” answer to these problems can be verified in polynomial time, to date our best algorithms for solving them — determining whether the answer is “yes” or “no” — all run in exponential time. Indeed, the famous P ≠ NP conjecture asserts that there do not exist efficient algorithms for solving NP-complete problems: any algorithm for these problems must run in super-polynomial time. In other words, the P ≠ NP conjecture asserts that first two levels of the Polynomial Hierarchy are distinct.

To infinity and beyond
The Polynomial Hierarchy extends beyond P and NP to include an infinite number of classes of increasing logical complexity: just as NP generalizes P, the second level of the hierarchy generalizes NP, the third generalizes the second, and so on ad infinitum. To understand this hierarchy it is convenient to think of problems in NP as asking questions with a single existential quantifier. For example, the Boolean Satisfiability problem asks if there exists a satisfying assignment to a Boolean formula, and the Traveling Salesman problem asks if there exists a short tour visiting every city exactly once. Problems at the k-th level of the hierarchy allow for questions with not just one existential quantifier, but k alternating quantifiers:

Does there exist X, such that for all Y, there exists Z such that…?

By Henry Pfister, Yury Polyanskiy, Rüdiger Urbanke and Yihong Wu

1 Information Theory

The publication of Shannon’s 1948 paper [Sha48] is widely recognized as the inception of information theory as a field of study. A key result in Shannon’s paper is that messages can be transmitted reliably over a noisy channel if and only if a sufficient amount of redundancy is added to correct errors. In particular, the error probability after decoding can be made to vanish as the message length increases if the rate R (i.e., the number of information bits per channel use) is less than the Shannon capacity C of the channel. Shannon’s proof relies on a randomly chosen codebook and does not lend itself to the practical construction of good codes. Thus, the 1948 paper also marks the beginning of the search for deterministic code constructions that achieve the Shannon capacity.

First, we consider a simple model of point-to-point communication. The binary erasure channel is a noisy channel with input alphabet {0, 1} and output alphabet {0, 1, ?}. During each time step, the transmitter sends an arbitrary element of the input alphabet, X, and the receiver observes a random channel output, Y, whose distribution is given by

The Shannon capacity of the channel is C = 1 − ϵ bits per channel use.

In wireless networks, the point-to-point model of communication does not capture the true complexity of the problem. One may also consider how much redundancy is required for pairs of transmitters and receivers to communicate reliably when their transmissions interfere with one another. The mathematical model of this problem is known as the interference channel [Car75]. In this case, the challenge is to determine the minimal amount of redundancy that each transmitter must add to their message. Characterizing the capacity region of the interference channel, namely, the set of rate pairs that allow reliable communication, is among the most significant open problems in information theory.

In the two sections below, we will describe recent advances in the understanding of these two problems.

By Kaie Kubjas

The rank of a matrix M is a fundamental notion in linear algebra. While usually defined as the dimension of the span of the rows or the span of the columns, it could also be defined as the minimal number r such that the matrix M admits a factorization as M=AB, where A has r columns and B has r rows. If all entries of the matrix M are nonnegative, then such a factorization can be pictured as a pair of nested polytopes: the outer one is given by the inequalities Ax≥0, and the inner one by the convex hull of the columns of B. Up to an affine transformation, this picture is independent of the specific factorization AB.

In many applications, we are interested in factorizations of a certain particular form. For example, we can study factorizations M=AB where A,B have nonnegative entries. The minimal r as above for which such a factorization exists is called the nonnegative rank. Cohen and Rothblum formulated this definition geometrically: a nonnegative matrix M has nonnegative rank at most r if and only if there exists a polytope with r vertices that can be fitted between two nested polytopes associated with the matrix.

The interest in the nonnegative rank started in the combinatorial optimization community with the work of Yannakakis at the end of the 1980s. A linear program aims to minimize or maximize a linear function over a region that is given by linear constraints, i.e., a polyhedron or a polytope. Yannakakis showed that the minimal number of variables and constraints needed to express a linear program over a polytope is closely related to the nonnegative rank of a matrix associated to this polytope. 

One line of research that started with the seminal paper of Yannakakis studies lower bounds on the nonnegative rank, and later also on the positive semidefinite rank, for different polytopes that appear in combinatorial optimization. For example, the Traveling Salesman Problem (TSP) asks: Given a list of cities, what is the shortest cycle that visits every city exactly once? It can be formulated as a linear program over a region which is called the TSP polytope. The TSP problem is NP-hard, and some of the attempts to prove P=NP aimed to give polynomial formulations of the TSP polytope. This motivated Yannakakis to look for superpolynomial lower bounds on the nonnegative rank of the TSP polytope, which was completed by Fiorini et al. in 2012.

The notion of nonnegative rank also appears in statistics: The set of stochastic matrices of nonnegative rank at most r is called the r-th mixture model. It represents the joint probabilities of two random variables that are independent given a third random variable with r possible values. Given a data matrix that is obtained by an opinion poll or a measurement, one would like to estimate the parameters of the true probability distribution that the data come from. Specifically, the maximum likelihood estimate of a data matrix is a matrix in the r-th mixture model that maximizes a specific function, called the likelihood function. There are several ways for numerically solving the maximum likelihood estimation in practice. These methods, however, do not provide a certificate for having found the global optimum.

In my recent research together with Eggermont, Horobeţ, Robeva, and Sturmfels (Robeva and Sturmfels attended the Algebraic Geometry program, and Horobeţ participated in one of the workshops at the Simons Insitute), we have been interested in exact descriptions of the sets of matrices of nonnegative rank at most r. They are semialgebraic sets, which means that they can be characterized by Boolean combinations of polynomial equations and inequalities. Knowing quantifier-free semialgebraic descriptions of these sets would give an exact method for checking if a matrix lies in them. It would be also an essential step towards computing maximum likelihood estimates with certificate.

By Yin Tat Lee and Aaron Sidford

Interior Point Methods and Algorithmic Spectral Graph Theory

Linear programming has long stood as one of the key pillars of computer science. In practice, problems are often reformulated as linear programs to take advantage of fast implementations of linear programming algorithms. And in theory, the best running times for solving many problems are achieved by using the theoretical guarantees of these algorithms. Moreover, new algorithms for linear programming have tended to cause ripples across the field, yielding not just faster running times but new algorithmic frameworks and a new lens on the structure of difficult problems.

Recently, state-of-the-art linear programming techniques known as interior point methods have been making waves in the area of Algorithmic Spectral Graph Theory, which uses linear algebraic properties of graphs to improve algorithm design. Like many iterative methods for optimization, interior point methods reduce solving difficult problems, like linear programming, to solving a sequence of simpler problems — in this case, solving a system of linear equations. When solving classic network optimization problems like maximum flow and minimum cost flow using interior point algorithms, these linear systems are highly structured. To solve them, it suffices to solve linear systems in the combinatorial Laplacian of a graph, one of the central mathematical objects in spectral graph theory. Consequently, standard interior point methods provide an algorithmic framework that naturally facilitates the leveraging of spectral properties of graphs to obtain fast running times for network optimization problems.

Over the past decade, studying such problems at this boundary of continuous and discrete optimization has been an incredibly fruitful area of research. Building off work of Vaidya in 1991, in 2004 Spielman and Teng produced the first algorithm to solve these Laplacian systems in time nearly-linear in the size of the associated graph. This result influenced a decade of research in algorithmic spectral graph theory, prompted numerous breakthroughs in combinatorial optimization, and ultimately helped inspire much of the research in the Simons Institute’s Fall 2014 program on Algorithmic Spectral Graph Theory.

Moreover, Spielman and Teng’s result implied that iterations of standard interior point methods can be implemented in nearly linear time when solving common network optimization problems. In 2008, Daitch and Spielman proved that such an algorithm not only nearly matches the running time of the state-of-the-art 1998 algorithm of Goldberg and Rao for solving the maximum flow problem, but actually improves upon the previous best known algorithms for solving the minimum cost flow problem. Even more excitingly, over the past two years, modified interior point schemes and fast Laplacian system solvers have been used to improve the running time for exactly solving the maximum flow problem. In 2013, Aleksander Madry provided a faster algorithm for solving sparse unit capacity instances of maximum flow, and in 2014 we provided a new interior point scheme with a faster convergence rate that yielded faster algorithms for solving dense instances of the maximum flow and the minimum cost flow problems.

This interplay between algorithms for continuous optimization and the discrete structure of graphs was one of the central themes of the Simons Institute’s Fall 2014 Program on Algorithmic Spectral Graph Theory. Interior point methods and fast Laplacian system solvers are simply one illustration. Both in recent years and during the program there has been extensive work on using new iterative machinery and new structural properties of graphs to design faster and better algorithms for solving various graph problems. During the semester we enjoyed exploring multiple research questions in this direction and discussing the exciting work of visitors and long term participants. In the remainder of this vignette we will discuss one recent success story in this line of work.

For Lent, the Simons Institute is giving up not having a blog.