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!
Updates: Here is the final version of my ICM paper, and Yael’s videotaped lecture. https://youtu.be/0vDbztbUbMo
Combinatorics and more 
We say that a X^n paper is a paper written by n people with last name X [1]. Now what is the record for a X^n paper?
There are many X^2 papers and the best, which I can recall, is a X^3 paper, where X=Bannai [2]. Is there a paper with n > 3? Besides the highly anticipated Kalai^4 paper?
[1] It is tempting to add additional constraints. For example one could require that there are no additional authors or the authors are biologically related.
[2] https://arxiv.org/abs/1304.5760v1
There is Horodecki^4
https://arxiv.org/abs/quant-ph/0702225
Here is Katona^3 :
Gyula O. H. Katona, Gyula Y. Katona, Zsolt Katona:
Most Probably Intersecting Families of Subsets. Combinatorics, Probability and Computing 21(1-2): 219-227 (2012).
Father and 2 sons
Another “Father and 2 sons” paper is
André Hirschowitz, Michel Hirschowitz, Tom Hirschowitz:
Contraction-free Proofs and Finitary Games for Linear Logic. Electr. Notes Theor. Comput. Sci. 249: 287-305 (2009)
(They have at least another paper the three of them together.)
Here are two contributions in group theory (the first is with additional coauthor):
Baumslag, Gilbert; Neumann, B. H.; Neumann, Hanna; Neumann, Peter M. On varieties generated by a finitely generated group. Math. Z. 86 1964 93–122.
Neumann, B. H.; Neumann, Hanna; Neumann, Peter M. Wreath products and varieties of groups. Math. Z. 80 1962 44–62.
‘There is an ongoing plan for writing a paper coauthored by Adam, Ehud, Gil and Yael Kalai involving learnability, game theory, algorithms, and cryptography.’
Working title: Superkalaifragilisticexpialidocious?
Pingback: Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson’s problem. | Combinatorics and more
Here is another great videotaped lecture by Yael Kalai, and this time a relation with PPAD-hardness is discussed.
Pingback: Greatest Hits 2015-2022, Part I | Combinatorics and more
Yael was just awarded the ACM prize for computing! congratulations, Yael! https://awards.acm.org/about/2022-acm-prize
Pingback: ACM Prize to Yael Kalai | Gödel's Lost Letter and P=NP