Letter from the Director

Dear friends of the Simons Institute,

As I write this letter, the Simons Institute is hosting a vibrant program in Information Theory, a topic at the interface between electrical engineering and computer science, and we are looking forward to an exciting program in Cryptography this summer.

Increasingly, many of the greatest opportunities for advances in science and engineering occur at the interfaces between disciplines. In line with this trend, the Simons Institute endeavors to create programs that draw on several related disciplines, enabling each participant to gain new perspectives and form new collaborations.

Kristin Kane’s article in this newsletter describes the interdisciplinary character of some of our past programs. She discusses the interplay between materials science, quantum physics and complexity theory in the Spring 2014 Quantum Hamiltonian Complexity program, the links between Algebraic Geometry and Spectral Graph theory in our Fall 2014 programs, the spirited exchanges among biologists, physicists, statisticians, probabilists and theoretical computer scientists in our Spring 2014 program on Evolutionary Biology, and the complementary outlooks of computer scientists and statisticians in our Fall 2013 Big Data program.

The Research Vignettes and From the Inside essay in this newsletter also exemplify the interdisciplinary theme, presenting connections between discrete and continuous algorithms, links between geometry, optimization and statistics, and influences of information theory on statistics, combinatorics, computational complexity and machine learning .

In their Research Vignette, “Faster Algorithms for Linear Programming,” Yin Tat Lee and Aaron Sidford, members of the Spectral Graph Theory program, describe how methods from linear algebra can be used to set new records for the speed with which linear programming and network flow problems can be solved.

In her Research Vignette, “Semialgebraic Geometry of Ranks,” Kaie Kubjas, a member of the Algebraic Geometry program, discusses the concept of the nonnegative rank of a nonnegative matrix M, which arises in algebraic geometry but also relates to the complexity of certain combinatorial optimization problems, such as the traveling-salesman problem, and to the construction of mixture models in statistics.

Venkat Guruswami’s “From the Inside” piece on the Information Theory program describes how the original subject matter of information theory has broadened to meet the needs of a networked society dependent on massive data sets. Claude Shannon’s seminal 1948 paper dealt with the fundamental limits on the achievable rate of reliable communication over a noisy channel, and that work was followed by the development of error-correcting codes whose performance approaches the fundamental limit. Modern information theory deals with new codes adapted to diverse design requirements, as well as aspects of networked systems including multi-party communication and computation, streaming algorithms, iterative message passing and network coding. The three workshops in the program cover emerging trends in coding theory, and the influence of information theory on machine learning and big data applications, computational complexity theory and combinatorics.

The newsletter concludes with a preview of our Summer 2015 program on Cryptography, which begins late next month.

In closing, I hope this newsletter provides you with an appealing sampling of the diverse activities of the Simons Institute.

Best regards,
Dick Karp, Director

Related Articles:

Through the Computational Lens: Interdisciplinary Collaboration at the Simons Institute
From the Inside: Information Theory
Research Vignette: Faster Algorithms for Linear Programming
Research Vignette: Semialgebraic Geometry of Ranks
Program Preview: Cryptography