Yael Tauman Kalai: Delegating Computation via No-Signaling Strategies.
Ladies and Gentelmen, Here is, exclusively for our readers, Yael Tauman Kalai’s ICM2018 paper: Delegating Computation via No-Signaling Strategies.
The opportunity to present the paper arose when a week ago I attended a great lecture on game theory by Yair Tauman and met there Adam Kalai, Yael, and Yoyo.
Here are slides of a related talk by Yael on the evolution of proofs in computer science. Vidotaped lectures by her at the Simons Institute (Lecture 1, Lecture 2), and blog posts by Yael on Windows to Theory: The evolution of proofs; Challenges in Outsourcing Computation; and with Guy Rothblum: Progress and Challenges in Code Obfuscation (part 1 and part 2).
With Adam, Yael, and Maya, Atlanta, 2007.
My ICM2018 paper, spectral sequences and cryptography
Many thanks for all the comments to the three thirds of my paper. Here is the combined and corrected version: Three puzzles on mathematics, computations, and games. Corrections and comments welcome.
Due to space limitation I did not include the following planned comment/footnote:
“Allan Hatcher wrote in the preface of his legendary textbook on algebraic topology:
Not included in this book is the important but somewhat more sophisticated topic of spectral sequences. It was very tempting to include something about this marvelous tool here, but spectral sequences are such a big topic that it seemed best to start with them afresh in a new volume.
A similar story can be told about the marvelous area of cryptography in the context of my paper. We talked about P and NP, graph algorithms, randomized algorithms, complexity of linear programming, computational geometry, algorithmic game theory, Papadimitriou’s classes, circuit complexity, bounded depth computation, parallel computing (a little), distributed computing and collective coin flipping, probabilistically checkable proofs (PCP) and hardness of approximations, property testing, quantum computing, Hamiltonian complexity, quantum fault-tolerance, efficient learnability, sampling complexity, primality and factoring. But for similar reasons to Hatcher’s it seems best that connections with cryptography will wait to a fresh new paper … (by a different author).”
In hindsight I could have even said “by a different Kalai”. Yael’s paper is centered around cryptography, and it has some tangent points with my paper: it talks about the new types of proofs appearing in the theory of computing, mentions games with provers and verifier, and connections to the quantum world via the non-signaling property.
Towards Kalai, Kalai, Kalai, and Kalai paper
There is an ongoing plan for writing a paper coauthored by Adam, Ehud, Gil and Yael Kalai involving learnability, game theory, algorithms, and cryptography.
Trivia question (thanks to Joan Feigenbaum): Who said and in what context: tangents have rights too!