{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiafgq4s5ojvotqff7sdaq5k6vzgzlcxkyzoklvr6o2amk6v5hjyky",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3moustmkcc5q2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiefy6v52bj6jb6sns2yrjey76grkpot4elhvoh2vrzgtelsuhchwm"
    },
    "mimeType": "image/png",
    "size": 2092416
  },
  "path": "/2026/06/22/matching-in-nc-and-local-events/",
  "publishedAt": "2026-06-22T07:39:35.000Z",
  "site": "https://gilkalai.wordpress.com",
  "tags": [
    "bipartite matching is in NC",
    "this post",
    "“Groups, expanders, and codes",
    "after-dinner speech",
    "one-day conference",
    "two-day meeting",
    "students talk day",
    "devoting an evening",
    "Games, Rationality and Society",
    "Half a Century of Agreeing to Disagree",
    "agreement theorem",
    "course webpage"
  ],
  "textContent": "Matching is in NC\n\nMatching 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.\n\nThe 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).”\n\n(See also this post about matching theory and VVV.)\n\nLocal Mathematical Events Birthdays\n\nThere is a great deal of mathematical activity around (sometimes with conflicting schedules), but not many international visitors.\n\nLast 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.)\n\nTwo 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.)\n\nNoga 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.\n\nThe Israel Academy is devoting an evening to mark Hillel Furstenberg’s 90th birthday. It will take place on July 8.\n\nAI + Math event at TAU\n\nThe 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.\n\nItai Benjamini organized one of the discussion groups on AI and mathematical research and kindly invited me to participate. It was very interesting.\n\nYonatan Aumann on the centipede game\n\nYonatan 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.\n\nLast 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.\n\nKazhdan’s Hypercontractivity and Groups Seminar\n\nOur 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.\n\nI 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.\n\nTop 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.\n\nBy Gil Kalai",
  "title": "Matching in NC and Local Events"
}