From the Previous ’20s Decade to This One

Bruce Arden and Juris Hartmanis both passed away at age 94. Bruce actually left us in December 2021, but I am pointing to a February 2022 obit on Princeton’s website. Juris’s Cornell obit came just a few days afterward, on August 4.

Today in the news I am reading about the passing of Barbara Walters age 93 and Pope Benedict age 95. Not to mention Elizabeth Windsor last September at 96. All were born in the 1920s. Now we are deep into the 2020s.

Bruce was the initial chair at Princeton’s computer department. He recruited me there from Berkeley—I always thought he was a wonderful chair.

Juris was the founding chair of Cornell’s Department of Computer Science. I met him when I was a junior faculty—before I was at Princeton. Cornell held a wonderful celebration on November 4, which Lance Fortnow and Bill Gasarch covered here on their wonderful blog. I regret being unable to travel because of my hip, and Ken because of heavy teaching on Fridays and the snowballing Hans Niemann case, which is still causing him much more work than the public sees.

Best CS for Year MMXXII

Lance and Bill have already selected their best paper for 2022: “NP-Hardness of Learning Programs and Partial MCSP” by Shuichi Hirahara.

Visiting Simons in the new year

The title requires a little parsing as two different areas are represented: complexity of learning and complexity of standard decision problems. The part about the Minimum Circuit Size Problem (MCSP) interests us most, for reasons we covered here and here. The partial MCSP asks whether there is an -input circuit of a specified size that agrees with a given function on inputs such that . He proves it NP-hard under polynomial-time randomized reductions. Derandomizing the reductions would have significant consequences.

We mention Lance and Bill’s runner-up paper, “Maximum Flow and Minimum-Cost Flow in Almost-Linear Time,” because of what Lance wrote next:

The title speaks for itself.

That’s a reference to a famous statement “The chess speaks for itself” by Niemann after he defeated Magnus Carlsen in a fast-chess game in Miami in August. This quote was already notorious before the September 4 win over Carlsen that precipitated the current scandal.

Ken and I think, widening the field to include combinatorics, that this paper might be an alternative choice: “A Proof of the Kahn-Kalai Conjecture” by Jinyoung Park and Huy Tuan Pham.

Not only does the title speak for itself, the entire abstract speaks exactly what the title speaks:

We prove the “expectation-threshold” conjecture of Kahn and Kalai.

In a few more words, this paper makes progress on open questions in probabilistic combinatorics, including thresholds for perfect hypergraph matchings, bounded-degree spanning trees, and bounded-degree spanning graphs. The paper itself is only 5 pages plus references. It gives a crisp definition of the conjecture of Jeff Kahn and Gil Kalai:

The conjecture is about systems of subsets of a finite set that are closed under superset, a stronger condition than the closure under union in Péter Frankl’s conjecture which we just mentioned. What do you all think?

Open Problems

Ken and I wish you all the best for the new year 2023. May you all have a wonderful and productive year.

[fixed Arden in photo at top, some word changes]