Looking Ahead: Data Science and Lower Bounds

by Luca Trevisan, Simons Institute, UC Berkeley

The Summer Cluster on Challenges in Quantum Computation is the Simons Institute's first experiment with a shorter-length program format. The cluster will run for eight weeks during the summer, and it will bring about thirty visitors to Berkeley, in addition to about twenty local participants; additional participants will come to Berkeley for a week-long workshop halfway through.This summer, the Simons Institute will host activities on Quantum Computing and on Algorithmic Fairness; and in the coming fall, we will host programs on Data Science and on Lower Bounds.

The cluster, organized by Andrew Childs, Ignacio Cirac, Umesh Vazirani and Thomas Vidick, is motivated by the announced developments of quantum computing devices of the scale of tens of qubits. Such devices may already be capable of performing computational tasks that are not feasible for existing classical computers. Testing such speed-ups involves combined insights from computational complexity, cryptography and physics: such a multi-disciplinary approach will be the focus of the cluster.

In the second half of the summer we will run a smaller cluster on algorithmic fairness, organized by Cynthia Dwork and Guy Rothblum. As algorithms make increasingly sensitive decisions about what information we see, what credit conditions we are offered, and so on, there is increasing concern about whether such algorithms are "fair," or if they replicate biases present in the data on which they were trained. To address such questions one must first have a precise definition of fairness, and a way to reason mathematically about it. Such a rigorous approach to fairness is the topic of this cluster.

The program on Foundations of Data Science, organized by Ken Clarkson, Ravi Kannan, Michael Mahoney, Andrea Montanari, Santosh Vempala, Rachel Ward and David Woodruff, is part of the ongoing effort by the Simons Institute to help build theoretical foundations for the developing field of data science, following our 2013 program on Theoretical Foundations of Big Data Analysis and our 2017 program on Foundations of Machine Learning. This new program will focus on algorithmic models and on statistical methods motivated by data science, including randomized methods to speed up numerical linear algebra calculations, robust statistics, dimension reduction, and streaming algorithms.

The program on Lower Bounds in Computational Complexity, organized by Russell Impagliazzo, Toni Pitassi, Anup Rao, Ben Rossman, Amir Yehudayoff, Avi Wigderson and Ryan Williams, will focus on unconditional impossibility results in various computational models, including communication complexity, boolean circuits, algebraic circuits, branching programs, and proof systems. Participants will study questions at the core of complexity theory, as well as questions that directly relate to the limitations of widely deployed types of algorithms. An example of the former is the VP versus VNP problem, the algebraic complexity analog of the P versus NP problem, which, unlike the P versus NP problem, might be provable via known mathematical techniques. Examples of the latter are lower bounds for streaming algorithms via communication complexity and impossibility results for linear programming (called "extension complexity" results) proved via proof complexity and communication complexity methods.

Related Articles

• Letter from the Director, June 2018
• The Mind, the Brain and the Computer
• From the Inside: Real-Time Decision Making
• From the Inside: The Brain and Computation
• Research Vignette: Optimization Against Adversarial Uncertainty