Shayan Oveis Gharan wins the 2026 Abacus Medal for TSP approximation and sampling. www.mathunion.org/im... Quanta: www.quantamagazine.o... Fields Medalists: Yu Deng, John Pardon, Jacob Tsimerman and Hong Wang

I bring back the Complexity Class of the Week to talk about L_2^P, the set of problems reducible to finding the minimum element of a total linear order.

The new OSTP reports "Science: A New Golden Age" is not great for universities but here is a silver lining for the theory community. Report: www.whitehouse.gov/s... WSJ Gifted Article: www.wsj.com/politics...

Every time there is some new major theorem proved by AI, I start seeing posts that a resolution of P v NP is right around the corner. This is your regular reminder that no, it isn't.

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching.

Bipartite Perfect Matching in Deterministic NC

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterje...

blog.computationalcomplexity.org

ACM is considering giving large language models access to the papers in their digital library. cacm.acm.org/opinion... You can give feedback here: docs.google.com/form...

FOCS Accepted Papers sanjeevkhanna.org/FO...

Herman Chernoff passed on July 6, shortly after turning 103 years old.

Herman Chernoff (1923-2026)

Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th birth...

blog.computationalcomplexity.org

Don't get Bill started with "and so on"

Does it seem like we're seeing an acceleration in new theorems, especially in combinatorics. Some proved by AI, some assisted by AI, some inspired by AI and some by humans trying to prove what they can before AI takes over.

Whenever I typed "y" into any textbox anywhere on my computer, my ChatGPT app would shut down. Turns out the new windows ChatGPT had a Mac shortcut "Command+Y" and the "Command" is ignored in windows. ChatGPT Work found and fixed its own bug, on the third try.

Two CACM editorial talk about the the need for ACM to take charge at a time that AI is disrupting computing itself and what it means to be a computer scientist Jim Larus cacm.acm.org/opinion... Moshe Vardi cacm.acm.org/opinion... Blog Post blog.computationalco...

After 20 years, researchers finally have strong evidence that “quantum proofs” are more powerful than ordinary classical ones. The results suggest that at least in computation, there’s no way around the complexity of the quantum world. Read more in @quantamagazine.bsky.social:

Researchers Reveal the Power of ‘Quantum Proofs’ | Quanta Magazine

When checking that solutions to certain problems are correct, it turns out, you can’t get around the inherent complexity of the quantum world.

quantamagazine.org

You won't believe which actor tricked Bill!

I asked Claude Fable about Range Avoidance and it bounced me down to Opus. I didn't know computational complexity can be such a security risk.

With Claude Fable only available until July 7 without extra payments, I feel like I have a genie with a limited amount of wishes. Which open problems can I give it with some hope of finding a solution?

Cynthia Dwork guest posts on Scott's blog about a recent presidential action that would remove privacy protection tools from the 2030 census.

An American privacy emergency: Guest post from Cynthia Dwork et al.

Scott’s foreword: Cynthia Dwork is Gordon McKay Professor of Computer Science at Harvard, and a pioneer in the fields of differential privacy and algorithmic fairness. On my recent travels to…

scottaaronson.blog

Tim Roughgarden will become a professor at the Institute of Advanced Study.

Algorithmic Game Theorist Tim Roughgarden Appointed to IAS Faculty

Tim Roughgarden, a world-renowned authority in the field of algorithmic game theory (AGT), has joined the Institute for Advanced Study as a Professor in the School of Mathematics, effective July 1, 2026. Roughgarden comes to IAS from Columbia University, where he served as a Professor in the Computer Science Department.

ias.edu

I've been using AI to give new and nicely formatted translations. Honestly better than mathematicians translating. For today's blog post, new translations of the Gödel's P v NP letter lance.fortnow.com/bl... and Leibniz's The True Method lance.fortnow.com/bl...

Did Leibniz anticipate P v NP and Machine Learning in 1677?

So Meta has created "America's Workforce Academy" to provide free training for workers to develop the skills needed to build new data centers.

Introducing America's Workforce Academy (AWA)

America’s Workforce Academy is a first-of-its-kind program to train people for skilled jobs building the AI infrastructure that will power America’s future.

meta.com

Celebration for Avi Wigderson's retirement together with 30 years of the Computer Science and Discrete Mathematics (CSDM) program at the Institute for Advanced Study next June. www.ias.edu/math/eve...

Former NSF theory program director Peter Brass dissects the proposed OMB rules for federal grants making. Is it as political as it seems?

If the frontier AI models have limited rollouts, will we see two tiers of mathematicians and scientists, those who have access, and those who don't?

If an open math problem gnaws at you, embrace the zone before you embrace AI.

CRA on the new OMB regulations that will give political review of grant proposals and require pre-approval for conference travel, among other challenges.

OMB Proposes Sweeping Overhaul of Federal Grant Rules - GovAffairs

Explainer article on the Trump Administration's OMB proposed Regulation for Federal Financial Assistance and how it could impact the computing research community. Explainer article on the Trump Administration's OMB proposed Regulation for Federal Financial Assistance and how it could impact the computing research community.

cra.org

I had though we weren't getting Waymo in Chicago because of the weather. Turns out it is the unions. www.nytimes.com/2026...

Bill write about Bradač's new bounds on the off-diagonal Ramsey numbers.

I ran into the Finsler-Hadwinger theorem about squares in geometry, and asked Chatty to create an interactive demo. This is way too easy. lance.fortnow.com/Fi...

Domagoj Bradač gives a tight exponent for the smallest n, such that any graph on n vertices has either a clique of size s or an independent set of size k. For fixed s and large k, n is k^{s-1} up to polylog factors. A major result in Ramsey theory.

Off-diagonal Ramsey numbers

For positive integers $s$ and $k$, the Ramsey number $r(s,k)$ is the minimum integer $n$ such that any graph on $n$ vertices contains a clique of size $s$ or an independent set of size $k$. We...

arxiv.org