Noga Alon, Princeton
Title: Moni, adjacency labeling and induced universal graphs
Abstract: The equivalence between economical adjacency labeling schemes and small universal graphs for given families, established by Kannan, Naor and Rudich (KNR) more than 30 years ago, led to extensive subsequent research. I will discuss the topic, focusing on recent developments including the asymptotic solution of a fifty years old problem of Moon and the study of universal graphs for hereditary families with modest growth, suggested in the KNR paper.
Manuel Blum, CMU and UCB
Title: A Theoretical CS Approach to the Hard Problem: Insights from the Conscious Turing Machine (CTM)
Authors: Manuel and Lenore Blum
Abstract: The Easy and Hard Problems of consciousness (David Chalmers, 1995) can be defined as follows: The Easy Problem: Make a robot that simulates feelings. The Hard Problem: Make a robot that truly experiences feelings.
This talk introduces the Conscious Turing Machine (CTM), and uses it to outline a Theoretical Computer Science (TCS) approach to the hard problem.
Irit Dinur, Weizmann Insititute of Science
Title: Expanders in higher dimensions.
Abstract: Expander graphs have been studied in many areas of mathematics and computer science with versatile applications, including coding theory, networking, computational complexity and geometry.
High-dimensional expanders are a generalization that has been studied in recent years and their promise is beginning to bear fruit.
In the talk, I will survey some powerful local to global properties of high-dimensional expanders, and describe several interesting applications, ranging from convergence of random walks to construction of locally testable codes that prove the $c^3$ conjecture (namely, codes with {\bf c}onstant rate, {\bf c}onstant distance, and {\bf c}onstant locality).
Kobbi Nissim, Georgetown University
Title: Can we reconcile the computer science and legal views of privacy?
Abstract: Law and computer science interact in critical ways within sociotechnical systems, and recognition is growing among computer scientists, legal scholars, and practitioners of significant gaps between these disciplines that create potential risks for privacy and data protection. These gaps need to be bridged to ensure in the future both that computer systems are designed and implemented to correctly address applicable legal requirements and that interpretations of legal concepts accurately reflect the capabilities and limitations of technical systems. We will discuss some directions in which the gaps between the legal and technical views of privacy may be reconciled.
Omer Reingold, Stanford University
Title: Where is Moni?
Abstract: Moni's research is multifaceted to the extent that it cannot be encapsulated by any of his disciples. But we can all try. In this talk I will reflect on Moni lessons that I internalized and those that I didn’t.
Alon Rosen, Bocconi / Reichman
Title: Public-Key Encryption from Continuous LWE
Abstract: The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known.
We present new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE, using a Statistical Zero-Knowledge oracle.
Joint work with Andrej Bogdanov, Miguel Cueto Noval, and Charlotte Hoffmann.