Monday, September 30th, 2019

This Summer at the Simons Institute

by Luca Trevisan (Simons Institute, UC Berkeley)

This summer, the Simons Institute hosted one program and two clusters.

Foundations of Deep Learning

Samy Bengio, Aleksander Mądry, Elchanan Mossel, and Matus Telgarsky led a program on Foundations of Deep Learning, which ran for eleven weeks. The four themes of this program were: optimization techniques used to solve loss-minimization problems and train neural networks; the rigorous study of why neural networks generalize, even when the number of parameters is large compared with the size of the training data; the rigorous study of the robustness of the learned models, particularly against adversarially selected examples; and the model of generative adversarial networks as a means of learning representations of distributions from samples.

The program featured a boot camp and two workshops. The first workshop dealt with challenges in the aforementioned four areas of interest, and the second workshop explored new directions and offered an opportunity for participants to report on work carried out during the program.

Fairness cluster

Cynthia Dwork, Sampath Kannan, and Jamie Morgenstern organized a cluster on algorithmic fairness, which ran for six weeks during the first half of the summer. The Fairness cluster was motivated by widespread concern that automated decision-making systems reflect biases present in the data on which they are trained, thus entrenching discrimination in job offerings, determination of creditworthiness, sentencing, and so on. Resolving such issues may run into inevitable trade-offs between different fairness goals, as well as computational and information-theoretic impossibilities. At present, the extent of such limitations is not clear, and even completely satisfactory definitions of fairness goals have not yet been developed. The goal of this cluster was to make progress on such questions. The cluster did not include a boot camp but featured two workshops, one focusing on racial discrimination and one on frontiers of research on fairness.

Error-Correcting Codes and High-Dimensional Expansion

Irit Dinur and Prahladh Harsha led a cluster on Error-Correcting Codes and High-Dimensional Expansion, a generalization of the notion of expanders to simplicial complexes (a kind of hypergraph). The cluster focused on connections between high-dimensional expanders and the constructions of the locally testable and locally decodable error-correcting codes that underlie constructions of probabilistically checkable proofs in complexity theory. The cluster ran for four weeks in the second half of the summer and had a boot camp but no topical workshops.

Online and Matching-Based Market Design

This fall, Itai Ashlagi, Federico Echenique, Nicole Immorlica, Vijay Vazirani, and Leeat Yariv are running a program on Online and Matching-Based Market Design during the first six weeks of the semester. The program is studying, from a computational point of view, online markets for indivisible goods, such as markets for ride-sharing, vacation homes, and online dating.

Proofs, Consensus, and Decentralizing Society

Eli Ben-Sasson, Alessandro Chiesa, Yael Kalai, Rafael Pass, and Michael Walfish are running a program on Proofs, Consensus, and Decentralizing Society. The program looks at decentralized consensus mechanisms, such as blockchains; it studies the mathematical and complexity-theoretic techniques that go into the realization and applications of blockchains; and it considers the social, economic, ethical, and legal implications of such techniques.

This is my last article for the Simons Institute newsletter for the foreseeable future. Goodbye, readers, and hope to see you in Milan.

Related Articles