Next week Igor Pak will give the 2018 Erdős Lectures (delayed from June)
Here is the poster
Here is the poster
The study of Probabilistically Checkable Proofs, starting with the discovery of the PCP Theorem, is a cornerstone of modern computer science, with impact on complexity theory, algorithms, and cryptography. Born as a purely theoretical notion, mostly used to prove hardness of approximation results, PCPs are now becoming a widely deployed tool in blockchain platforms. The workshop will touch the past, the state of the art, and future of PCPs. Topics will include: hardness of approximation, PCPs in cryptography and blockchains, no-signaling PCPs, PCPs in P, and Boolean function analysis.
Boaz Barak, Shafi Goldwasser, Eli Ben Sasson, Gil Kalai, Yael Kalai, Guy Kindler, Elchanan Mossel, Christos Papadimitriou, Aviad Rubinstein, Ran Raz, Ronitt Rubinfeld, Oded Schwartz, Irit Dinur, Andrew Yao, and Avi Wigderson.
Nir Bitansky, Esty Kelman, Subhash Khot, Dor Minzer, and Muli Safra
Let me mention two talks with very promising news by friends of the blog, Karim Adiprasito and Noam Lifshitz. As always, with the beginning of the academic year there are a lot of exciting activities, things are rather hectic around, and I hear a lot of exciting things (both news and things I was supposed to know long ago). I am quite sure that we will return to the topics of the two lectures in later posts and I also welcome discussing them in the comment section. (A few related older posts for Karim’s talk and seminar: F ≤ 4E; Beyond the g-conjecture. and for Noam’s seminar: Influence, Threshold and Noise; Boolean functions: Influence, threshold and noise; .)
HUJI Thu, 25/10/2018 – 14:30 to 15:30; TAU 29/10/2018 12:15-13:15
Abstract: Consider a simplicial complex that allows for an embedding into . How many faces of dimension or higher can it have? How dense can they be? This basic question goes back to Descartes. Using it and other rather fundamental combinatorial problems, I will motivate and introduce a version of Grothendieck’s “standard conjectures” beyond positivity (which will be explored in detail in the Sunday Seminar). All notions used will be explained in the talk (I will make an effort to be very elementary)
Sunday’s seminar refer to a HUJI Kazhdan seminar given by Karim on this topic. (3-5 Ross building’s seminar room.) This is a good opportunity to congratulate Karim Adiprasito and June Huh on receiving the New Horizon Prize, and congratulations also to Vincent Lafforgue who received the breakthrough prize and to all the other winners!
When: Monday Oct.29, 11:00–12:45
Where: Rothberg CS building, room B500, Safra campus, Givat Ram
The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy, where , and is the probability that on an input with independent coordinates, each taking the value 1 with probability p.
The dense regime, where , is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.
In this talk we show that if a monotone Boolean function f with satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval , with . More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Θ(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find such that .
At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influences’. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where
We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of Huang–Loh–Sudakov and Furedi–Jiang for a new wide range of the parameters.
Alef: Koebe’s Karnaf
The artist behind Aleph’s corner has now a website offering over 100 T-shirt designs. In addition to a few pictures related to mathematics there are many in a few other categories: “Jazz,” “Urban,” “Nature,” “Signature design,” and “Sea”. Here are a few of my favorites
This post is my third report from ICM 2018. You may remember that I had planned to live-blog on the last four days of the congress but on Monday evening I realized that this was an unrealistic task and decided instead to blog only on a single day – Monday. A little later I realized this was also unrealistic and decided to limit my blogging to a single lecture by Peter Kronheimer and Tomasz Mrowka on Knots, three-manifolds and instantons. But in the end I did not live-blog at all and in this post I will briefly described Tuesday’s morning lectures and give a belated report on Peter and Tomasz’s lecture. I actually arrived in Rio very early on Saturday morning and attended many talks on Saturday, but this was not part of my planned blogging and I was relaxed and did not take lecture notes. Sunday was a day off and I had a great time with friends.
I greatly enjoyed all of Monday’s morning lectures. The first very inspiring lecture by my friend and colleague Rafi (Ronald) Coifman was entitled Harmonic analytic geometry in high dimensions – Empirical models (click for the video). Rafi’s research spans across a wide range of areas many of which he himself created and goes from the very applied (e.g., applications of harmonic analysis to pluming, biology, and finance) to the very pure (e.g., applications of wavelets to classical problems in harmonic analysis). The lecture covered a lot of ground, starting with Fourier’s original ideas and his perception that he had discovered the “language of nature” and continuing with wide applications to structural and multi-scale analysis of high dimensional data, and to the possibility, pushing Fourier’s vision one step further, of automatically learning the laws of physics from data.
Toward the third lecture on the history of mathematics by Catherine Goldstein I thought that I could relax and listen to a historical lecture that does not require much mathematical efforts. To my surprise, it was very demanding for me (but fully worth the effort) to follow the mathematics itself. The historical discussion and insights were great. The title of the lecture was Long-term history and ephemeral configurations (click for the video) and it started with a famous quote of Poincaré: Mathematics is the art of giving the same name to different things (Poincaré gave the examples of “groups” and “uniform convergence”.) At the center of the talk was Charles Hermite and the lecture dealt, among other things, with the very interesting question: Is mathematics a natural science? For Hermite the answer was: Yes! Altogether there were a lot of great insights and great lines. (Pictures from these two lectures at the end of the post.)
The talk was fantastic, it had great results, the slides were great, the presentation was great, thoughtful, with a lot of food for thought, both for the large audience and (I think) also for experts. A main famous theorem by the speakers is:
Theorem: Knots with vanishing Instanton Floer homology and (therefore) also knots with trivial Khovanov’s homology are unknots.
Khovanov’s homology are invariants of groups that refine the famous Jones polynomials and, of course, two problems naturally arise. First, is it the case that the Jones polynomial itself determines unknots? (This is a famous open problem.) And also does Khovanov’s homology or Floer’s homology distinguish different knots? (Maybe the answer for the second bold question is known to be negative…) The lecture had four parts
I was surprised that I had the feeling that I understood everything in the first part. It started with a quick pictorial introduction to what knots are, then looking at the complement of a knot, followed by Dehn’s lemma that was proved by Papakyriakopoulos. (I think but am not sure that Papakyriakopoulos’s proof is still needed for all the stronger results that follow.)
So Papakyriakopoulos’ theorem tells you that the fundamental group of the complement of a non-trivial knot is not Abelian, but could we say something stronger? Peter mentioned that for most, but not all non-trivial small knots the fundamental group maps onto a dihedral group. And the main result is that for all non trivial knots the fundamental group maps onto SO (3). There were two delicate yet important points that were mentioned. The first is that often SO(3) can or should be replaced by its double cover SU(2), and the second is that there is also a crucial condition (that makes the theorem stronger) about the images of “meridians” (small circles around a point on the knot in its complement).
The second part was about ideas, notions and tools needed for the proof of the main theorem. Naturally it was more difficult and for various things I only just pleasantly got a general impression together with some pointers on notions that I should (finally) learn. Connections, flat connections, Chern-Simons functionals, Young-Mills equations and their solutions called “instantons”, and the Floer’s (instanton) homology, … . As you can see from the fourth slide the list of tools that are actually needed for the proof extends even further and Peter and Tomasz also mentioned connections with Ozsváth and Szabo theory of Heegard Floer homology.
Surprisingly, the third part dealt with notions that were somewhat easier for me than those of the second part. The Khovanov homology is a refinement of another famous knot-invariant the Jones polynomial.
I remember hearing a few talks about Khovanov homology in the early 2000. Dror Bar Nathan showed how they appear very naturally and how it is a straight forward matter to compute them (alas, not efficiently). In a different talk some years later David Kazhdan showed how, taking a different point of view, those invariants depend on a sequence of amazing miracles. In any case, the Khovanov homology groups are finite dimensional and the Jones polynomial are just the alternating sums of their dimensions (or Euler characteristics). Like the Jones polynomial themselves there is also some connection (“skein relations“) between the Khovanov homologies of knots when you apply two simple operations on the knots.
The skein relations for Khovanov homology are given in terms of a long exact sequence, and similar relations hold for the Floer homology. Moreover there is some relation (a spectral sequence) between these two exact sequences which shows that when Khovanov homology is not trivial then Floer (instanton) homology is also non trivial and hence from what we already know about Floer homology the knot is not trivial.
and when part IV came I expected that the discussion will be aimed at real experts in the audience and that I could relax and think about other things. However this was not the case. Below the fold I will tell you about the surprising fourth part, and then proceed to talk about various other really interesting things. Statistics tell me that only about a third of the readers read below the fold but this time I truly recommend it.
Two dear friends, and great geometers, Ricky Pollack and Branko Grünbaum passed away a few weeks ago. Ricky was a close friend that both Mazi my wife and I loved, and we were both fascinated by his wisdom, charm and love of life. Branko was my academic grand father and I met him through his writings many years before I had the privilege and pleasure to meet in person. Here are some pictures of Ricky and Branko. (If you have more, send me and I will add them.)
In future posts I will tell you a little about their mathematics. See also these posts about stories and math related to Ricky ( A Discrepancy Problem for Planar Configurations; Many triangulated three-spheres!; Academic Degrees and Sex; GLL: Polls and prediction and P=NP . ) and to Branko ( My Copy of Branko Grünbaum’s Convex Polytopes; The World of Michael Burt: When Architecture, Mathematics, and Art meet; Coloring Simple Polytopes and Triangulations; Budapest, Seattle, New Haven ; How the g-Conjecture Came About; GLL: What are proofs for , anyway.) (Links for blog posts on other blogs are welcome.)
Branko with Janos Pach
The legendary mathematical partnership and friendship of Ricky and Eli Goodman is rare in mathematics.
Five generations in Seattle: Branko was the advisor of Micha A Perles (and also of Joram Lindenstrauss, Moshe Rosenfeld, Joseph Zaks and many others). Micha was my advisor (and also of Meir Katchalski, Michael Kallay, Nati Linial Noga Alon and many others). Isabella Novik was my student and here we are with four student of Isabella: Michael Goff, Kurt Luoto, Andy Frohmaderand, and Steven Klee. (From left to right.)
Saugata Basu, Ricky Pollack and Marie-Francois Roy’s book Algorithms in real algebraic geometry.
The Video of my ICM2018 lecture is now on the air
Here are the (slightly improved) slides.
I made the mistake of trying to improve my slides in the evening before the lecture and in the morning I discovered that the file disappeared (of course, after the lecture it reappeared) and I had to reconstruct it from an earlier version.
And here is the playlist of all plenary lectures:
Alef’s previous corner: There is still a small gap in the proof.
With Peter Sarnak, Stas Smirnov, and Tadashi Tokieda at Sugar Loaf (Pão de Açúcar), Rio.
At Sugar Loaf with Stas and Edward Dunne
This is my second report from ICM 2018. Some acronyms are used in this post. ICM = International Congress of Mathematicians; IMU = International Mathematical Union, an organization running the ICMs’ GA = General assembly (of the IMU) a body of representatives from the member countries of the IMU.
And a special bonus at the end of the post: Test your intuition question.
Here is a post from the ICM 2018 web-site about my lecture: Kalai plenary ponders possibilities of quantum computing. And here is the link to the ICM 2018 site itself.
The IMU Leelavati Prize is an award for outstanding contribution to public outreach in mathematics. Unlike most prizes “Leelavati” is not a name of a person (a man in most cases) but rather the name of 12th-century Indian mathematical treatise. The story of this year’s laureate, the Turkish mathematicians Ali Nesin and Sevan Nişanyan who built together a mathematical village to educate and advance children, is moving and quite amazing.
A rare standing ovation for Nasin, and Nişanyan
Nesin (left) and Nişanyan
Atiyah, Nesin, and Nişanyan
Some members of the Russian delegation after Saint Petersburg was announced as the winner (left), Stas Smirnov and François Loeser shake hands after the announcement. Both François and Stas were stars of my Hyderabad ICM 2010 reports. (I,II).
Mathematicians love sequences – here is the sequence of cities of post WWII ICMs
Cambridge (MA); Amsterdam, Edinburgh, Stockholm, Moscow, Nice, Vancouver, Helsinki, Warsaw, Berkeley, Kyoto, Zurich, Berlin, Beijing, Madrid, Hyderabad, Seoul, Rio,…
What is the law governing these choices? All these countries have good mathematics and a few have superb mathematics. Some of these cities represented democratic countries and some did not, and there are many shades of grey. The hosting countries also differ in terms of economic systems, human rights, foreign policies and various other things. If there is an emerging law for the sequence of cities it is that first, except for extreme cases, it is largely politically blind, and second, that an attempt is made to outreach and make ICMs s truly world wide experience. (The second item also characterizes other important activities of the IMU.)
This time the choice was between two fantastic cities, Paris and Saint Petersburg. The IMU executive committee had chosen Saint Petersburg, but this was challenged (for the first time, as far as I know) and at the end the GA democratically voted 83:63 (4 abstentions) for Saint Petersburg. For the full list of resolutions of the GA see this page. My feeling is that also many mathematicians from Russia and the former Soviet Union who live abroad (many also in Israel) were happy with this opportunity of a “mathematical reunion” in 2022. There was one additional GA resolution that caused some controversy that maybe I will mention in a future post.
Anyway, another exciting moment at the closing ceremony was
Andrei Okounkov and Stas Smirnov came with matching casual clothes and declared that this was because it was time for them to start working. I first met Andrei and Stas in Saint Petersburg in a 2004 conference celebrating Anatoly (Tolya) Vershik’s 70th birthday. (Here is a link to Vershik’s amazing home page.) (Picture: ICM 2018 site)
The Guardian (yesterday)
With the landmark decision (Thursday, yesterday) of the Indian supreme court, homosexual sexual activity is now legal in every country that ever hosted the ICM.
The paper An Improved Bound for Weak Epsilon-Nets in the Plane, by Nathan Rubin is now on the arxive. we mentioned the result in this post, and the problem in this post (my very first) over Tao’s blog What’s New.
Abstract: We show that for any finite set P of points in the plane and ϵ>0 there exist points in , for arbitrary small γ>0, that pierce every convex set K with |K∩P|≥ϵ|P|.
This is the first improvement of the bound of that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.