Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.

Complexity Theory At Carnegie Mellon

youtube.com

5/ My and others' first reaction was that the paper is not well written. I've changed my mind on that. I spent >1hr on just the ~1-page proof overview. It is 𝐝𝐞𝐧𝐬𝐞 and 𝐭𝐞𝐫𝐬𝐞. It lacks helpful framing, but all key ideas are there. The paper's body is quite accessible!

"We're all worried," as what it means to do research (in my field, Theoretical CS) seems to be shifting, and shifting fast. What to do? Senior researchers must lead by example, knowing that not everything will pan out. What I'm suggesting below may not work everywhere, but here's my own advice: 1/

Yes, the result itself is very interesting (more on this below). From a skim, I agree with Noah that the paper is not well-written. Am I happy to see LLMs invade TCS? No, it's terrible. Is this the most impactful LLM result about lattices this week? Unclear. 1/

Clément Canonne@ccanonne.github.io · 2mo ago

(same thing for @huckbennett.bsky.social and @noahsd.bsky.social , regarding the CVP one... If you have the time and energy of course!)

Some initial thoughts, and a complicated mix of feelings. Wow. I mean, Erdos problems are cool (I genuinely mean that), I didn't know about the Jacobian conjecture before it got disproved. But this newest batch from OpenAI hits home in a way the previous announcements did not.

Chinmay Nirkhe, Mark Zhandry, John Bostanci, and Jonas Haferkamp blended ideas from cryptography, statistical physics, and other far-flung fields to show that quantum proofs are more powerful than classical ones. www.quantamagazine.org/researchers-...

Warm congratulations to Ilias, Gautam, Daniel, Jerry, Ankur, and Alistair!

Clément Canonne@ccanonne.github.io · 4mo ago

Huge congratulations to Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart on being awarded the Gödel prize for their breakthrough work on algorithmic robustness! www.sigact.org/prizes/g%C3%...

This is a great blog post about making academic talks (and where AI should or should not come into the picture).

Thatchaphol Saranurak@eigx.bsky.social · 4mo ago

I fully agree with this post by @gautamkamath.com on how preparing talks is one of the best ways to upgrade my own thinking. So, I certainly do not want to waste that opportunity by delegating it to AI. kamathematics.wordpress.com/2026/05/27/m...

The TheoryFest workshops at #STOC2026 have been announced! Including one on Property Testing, by Anindya De and @shivamnadimpalli.bsky.social ! acm-stoc.org/stoc2026/wor...

Out today in @quantamagazine.bsky.social — my latest dispatch from the very meta, mind-bending corners of CS theory research. It's about a new approach to cryptography in which secrecy stems from Gödel-esque unprovable statements!

How Unknowable Math Can Help Hide Secrets | Quanta Magazine

A graduate student recently harnessed the complexity of mathematical proofs to create a powerful new tool in cryptography.

quantamagazine.org

Sidhanth Mohanty now has a blog! sidhanthm.com/bubbles/john...

In this MURI project with Sebastian Will (Columbia), Yongshan Ding (Yale), Shruti Puri (Yale), and Daniel Grier (UCSD), we will explore the potential uses and benefits (and limitations!) of using quantum gates that can act on many qubits at a time.

The Data Science Institute at Columbia University@datascicolumbia.bsky.social · 6mo ago

Led by DSI member @henryyuen.bsky.social, a new multi-university grant from the Air Force Office of Scientific Research (AFOSR) will examine whether larger quantum operations could reduce errors and make future quantum computers more practical. More: datascience.columbia.edu/news/2026/tr...

FOCS 2026 will be held in New York City Nov 8 - 11! CFP is up (link below). Submit your best work in theoretical computer science by April 1, 5pm ET.

Congrats to Sloan fellows: @nyucourant.bsky.social colleagues Florian Schäfer and Joe Tassarotti, and theory colleagues @behnezhad.bsky.social, @surbhigoel.bsky.social, Aayush Jain, Anand Natarajan, @adtraghunathan.bsky.social, @soledadvillar.bsky.social, and John Wright! sloan.org/fellowships/...

2026 Fellows | Alfred P. Sloan Foundation

Our mission is to make the world a better place through the advancement of scientific knowledge.

sloan.org

I discuss fully quantum complexity theory with @benbenbrubaker.bsky.social. Although we're not really sure, it seems like our understanding of computing on quantum data needs new foundations. Transforming quantum data is less like solving a hard math problem, and more like doing an intricate dance.

Ben Brubaker@benbenbrubaker.bsky.social · 8mo ago

How can we make sense of computational problems that we don’t even have the language to describe? I spoke to @henryyuen.bsky.social about what’s missing from the standard approach to quantum complexity theory — read more in @quantamagazine.bsky.social!

How to turn off Gmail's ability to read your emails to train its bots: www.malwarebytes.com/blog/news/20...

Gmail can read your emails and attachments to train its AI, unless you opt out

A new Gmail update may allow Google to use your private messages and attachments for AI training. Here's how to turn it off.

malwarebytes.com

My student @johnbostanci.bsky.social, Chinmay Nirkhe, Jonas Haferkamp, and Mark Zhandry have put out a tour-de-force paper that shows, relative to a classical oracle, QMA is stronger than QCMA -- i.e., quantum proofs >> classical proofs. Congratulations to the authors! arxiv.org/abs/2511.09551

Separating QMA from QCMA with a classical oracle

We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decid...

arxiv.org

The list of accepted papers for #QIP2026 is now online at qip2026.lu.lv/programme/ac...

You could also work with Debbie Leung, Richard Cleve, David Gosset, Luke Schaefer, Ashwin Nayak, Norbert Lutkenhaus, Mike Mosca, Christine Muschik or some combination of us if you do theory.

Graeme Smith@graemesmith.bsky.social · 11mo ago

If you are interested in doing a postdoc with me, please apply to the IQC postdoctoral fellowship here: iqc-uwaterloo.slideroom.com#/login/progr...

I do phase estimation without QFT in my undergrad course. youtu.be/CMqPutlG59c?... It's just Hadamard test plus binary search.

#60/100: 1-qubit Rotation Estimation: Overview || Quantum Computer Programming in 100 Easy Lessons

YouTube video by Ryan O'Donnell

youtu.be

Academics in Assyria in the 7th c BC complain that admin is preventing them from doing research and teaching

Tomorrow I am teaching quantum phase estimation in my Intro to Quantum Computing Class for the seventh time. I was prepared to teach it the standard, textbook, Nielsen and Chuang way: applied controlled unitaries and their powers thereof, apply inverse QFT to the ancillas.

Dr. Jane Goodall filmed an interview with Netflix in March 2025 that she understood would only be released after her death.

The submission server for #ITCS2026 (which will take place at Bocconi University, Milan, in January 2026) is open! Submission deadline: Sep 4 (abstracts), Sep 6 (papers) itcs-conf.org

How fast can (pseudo)random unitaries be implemented on a quantum computer? O(1) time suffices (provided you can do things like intermediate measurements)! This -and more- is thanks to a superfun collaboration with Ben Foxman, @nat-parham.bsky.social, and @franvasco.bsky.social (all PhD students!).

Francisca Vasconcelos@franvasco.bsky.social · last yr.

In exciting new work with Ben Foxman, @nat-parham.bsky.social , and @henryyuen.bsky.social we show that t-designs and pseudorandom unitaries are implementable in constant (quantum) time! arxiv.org/abs/2508.11487

Donation link here: www.ipam.ucla.edu/news/nsf-fun...

IPAM NSF funding is currently suspended - IPAM

Frequently asked questions: 1. What is the effect on IPAM programs?We are committed to continuing our programs for the immediate future and at this time we are not cancelling activities or invitations...

ipam.ucla.edu

Terence Tao@teorth.bsky.social · last yr.

#IPAM (the institute for pure and applied mathematics) is facing a critical shortfall for operating expenses due to an unexpected suspension of NSF funding www.ipam.ucla.edu/news/nsf-fun... . Donations for emergency continuity of operations funding can be made at giving.ucla.edu/Campaign/Donat

the scenario we all feared

Come for the iconic papers and eye-wateringly beautiful textbooks, stay for the stories "from the trenches" (of which I hope John posts more of!). Keep writing, @johnwatrous.bsky.social !

John Watrous@johnwatrous.bsky.social · last yr.

Bluehost seems to be holding my domain name hostage, I gather in an effort to sell me more products and services. Avoid them at all costs. But see if I care. Hereafter you can find my web page at jhwatrous.github.io in case you're looking for it.

Out today in @quantamagazine.bsky.social: a new path toward building quantum cryptography on much harder problems than the ones used for classical encryption. Fascinating stuff!

Quantum Scientists Have Built a New Math of Cryptography | Quanta Magazine

In theory, quantum physics can bypass the hard mathematical problems at the root of modern encryption. A new proof shows how.

quantamagazine.org

From our very thoughtful law school colleague, David Pozen, a first take on the Columbia deal. balkin.blogspot.com/2025/07/regu...