Matching in NC and Local Events

Matching is in NC

Matching theory is one of the richest gold mines of ideas and results in mathematics, computer science, and beyond. Recently, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Thomas Thierauf proved that bipartite matching is in NC. Namely, there is a polynomial-time algorithm of polylogarithmic depth that decides whether a bipartite graph has a perfect matching. This problem has long been regarded as a holy grail of complexity theory. Congratulations to Abhranil, Sumanta, Rohit, Roshan, and Thomas.

The authors write in the abstract that “the techniques are based on the polynomial method, inspired by a construction of subspace designs by Guruswami and Kopparty (Combinatorica, 2016).”

(See also this post about matching theory and VVV.)

Local Mathematical Events

Birthdays

There is a great deal of mathematical activity around (sometimes with conflicting schedules), but not many international visitors.

Last week there was a week-long school (Midrasha) on “Groups, expanders, and codes,” marking Alex Lubotzky’s 70th birthday. (See this post for my after-dinner speech for Alex ten years ago.)

Two weeks ago there was a lovely one-day conference celebrating Yaron Ostrover’s 50th birthday, where I gave a talk on the conjecture. (See this post.)

Noga Alon and I are organizing a session celebrating Micha Perles’ 90th birthday, featuring, besides the two of us, Nati Linial, Ron Adin, and Rom Pinchasi. It will take place on July 6 and will be part of the two-day meeting of the Israel Mathematical Union at Bar-Ilan University on July 5-6. On July 7 there will be our traditional students talk day.

The Israel Academy is devoting an evening to mark Hillel Furstenberg’s 90th birthday. It will take place on July 8.

AI + Math event at TAU

The mathematics department at TAU organized a special day devoted to AI and mathematics, featuring Ronen Eldan (OpenAI and the Weizmann Institute) as the main speaker.

Itai Benjamini organized one of the discussion groups on AI and mathematical research and kindly invited me to participate. It was very interesting.

Yonatan Aumann on the centipede game

Yonatan Aumann gave a beautiful lecture presenting an approach, developed jointly with his father Robert Aumann, for dealing with the centipede game. The occasion was a one-day workshop “Games, Rationality and Society” marking the 20th anniversary of Robert Aumann’s Nobel Prize, which included many other lovely lectures.

Last week, many friends of mine participated in a conference in Paris “Half a Century of Agreeing to Disagree” celebrating the 50th anniversary of Aumann’s celebrated agreement theorem.

Kazhdan’s Hypercontractivity and Groups Seminar

Our Kazhdan’s seminar on hypercontractivity and representation theory is approaching its final weeks. After a few introductory lectures, most of the talks were given by Noam Lifshitz and were devoted to hypercontractivity and group representations.

I gave two lectures in which I summarized some early applications of hypercontractivity in other directions and discussed several open problems. Had we had more time, we could also have discussed additional applications of hypercontractivity to global functions, and I may add some material on this topic to the course webpage. Nati Linial is a dominant participant in the seminar and asked some great questions about representation theory that led to wonderful micro-lectures by David.

Top row: Old friends celebrating Yael and Arnon’s wedding; David taking the chalk to give a one-minute introduction to étale cohomology, at Nati’s request. Middle row: RUNI’s new robot; Eden Ben-Zaken performing at RUNI; bottom row: Shira Tanny lecturing at Yaron Ostrover’s day; Ronen Eldan lecturing about things mathematicians should know about LLMs.