For Aaronson-Ambainis, you have to remember that in quantum computing we say "query complexity" the way that biologists say "in mice."

As in "we can cure cancer in mice" or "we know the power of QCs in query complexity."

Excited to see that the Aaronson-Ambainis conjecture has apparently been proved! But depressed to see the amount of completely incorrect commentary on its implications, so here's an attempt to clear things up.

This is too strong of an interpretation, for a couple reasons. First, Aaronson-Ambainis compares quantum vs classical algorithms when they have access to an idealized, perfectly unstructured black box oracle. All cryptographic hash functions are not black box and definitely not unstructured (because their source code is succinct and public). We should be very wary about transferring conclusions about random oracles to concrete hash functions.

Second, Aaronson-Ambainis is about decision problems concerning the black box oracle. We now know there is no exponential quantum advantage for decision problems on unstructured oracles. On the other hand, search problems are a completely different story. We know there can be exponential quantum advantage for solving search problems related to unstructured oracles; this is the famous Yamakawa-Zhandry result from 2022.

This second item is particularly relevant to breaking hash functions, where you want to do things like "Find me a preimage -- any preimage -- of this hash value".

All that said: the complexity and theoretical cryptography community has significantly stronger confidence that there should exist some hash functions that are secure against quantum computers, as compared to the confidence about the security of post-quantum public-key encryption schemes (such as lattice-based schemes). For example, as far as I know it is very plausible that SHA256 remains secure against quantum computers.

Looking forward to tomorrow's TCS+AI Workshop at FOCS. @littmath will give a keynote, followed by a panel discussion with Dan Spielman, @littmath, @praveshkkothari, @B1ar2n3a, and Nikhil Srivastava. I'll moderate. Come with all of your questions, anxieties, and hopes!

We're now accepting applications for research interns at @a16zfrontier, for summer '27 in NYC! Application deadline is Nov 20th. You'd be working with me @skominers @SuccinctJT @ittaia @PGarimidi @jneu_net @ErtemNusretTas, as well as other interns, visitors, and our advisors ur interests are broader than ever---ambitious undergrads with a keen grasp of emerging technologies, grad students looking to transition to building and entrepreneurship, as well as PhD students pursuing a more traditional academic career.

Research areas of interest include AI and machine learning, agentic commerce, cryptography, security, distributed computing, hardware design, economics (micro, macro, and empirical), energy, material science, biology, incentives, quantitative finance, market and mechanism design, foundations of computing, and pure mathematics.

For more details and to apply, see jobs.a16z.com/jobs/andreesse…

Nice to see the Exponential Time Hypothesis discussed in the New York Times: nytimes.com/2026/11/06/sci…

Ah, another beautiful question in quantum complexity theory solved! This one is due to Scott Aaronson and @AAmbainis, about the necessity of structure in a problem for exponential quantum advantage. This question inspired a lot of research and we collectively learned a lot about quantum computing from it.

The problem seemed ripe; this year it felt like we were closing in on it. The most recent (human-written) papers on it had solved special cases showing that parallel quantum algorithms cannot achieve exponential speedups for unstructured problems.

What is the next beautiful question in quantum algorithms that will spur another generation of learning and understanding?

* Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, Quantum Speedups Require Structure or Depth (arxiv.org/abs/2608.19158)

* Qipeng Liu, Saachi Mutreja (my fantastic student!), Parallel Quantum Advantage with Limited Adaptivity Requires Structure (arxiv.org/abs/2608.20297)

@hodgecomputer has partnered with @prove2memath!

@prove2memath is an exciting platform for crowdsourced math formalization; they were used in an essential way by Anthropic during their formalization of FLT.

see our collection of cross-listed "missions": prove2.me/collections/ho…!

I finished the proof of "ETH false" (#3SAT in subexponential time) in my grad complexity class at CMU today (mod some easy exercises).

I think it's nice that it can be done just using classical complexity theory ingredients - it fits well in the course!

youtube.com/watch?v=3CdlC4…

AI has created an "abundance" of certain kinds of work, and it's hard adapting to an abundance mindset. If you told someone 100 years ago (electricity becoming common in urban homes) how ubiquitous electricity would be, they probably still wouldn't think of grow lamps. So now(1/)

STOC 2027 received 1665 submissions. In a bold new experiment, all submissions (and author identities) are immediately made public. This is the most immediate and revealing posting of any conference I am aware of.

Take a look and see what you find!

stoc2027.sigact-ec.workers.dev

How much can classical algorithms tell us about entangled quantum systems?

Deep research, demanding proofs. Our Quantum Max-Cut campaign brings researchers and AI agents together on Prove2Me to formalize approximation guarantees in Lean—and build toward stronger bounds.

prove2.me/campaigns/quan…

E.g., Aparna Gupte @aparna_gupte is maintaining a spreadsheet of new cryptographic algorithms being derived from the ETH refutation. Find the spreadsheet here docs.google.com/spreadsheets/d… and add more applications as they are found here docs.google.com/forms/d/e/1FAI…

Dana, my PhD advisor, decodes the alien proof of the Uniques Games Theorem. I think I can count with one hand the number of people who have thought about UGC as much as she has. This should be a treat.

Assistance is needed at the self-checkout counter at Costco. Also this is one of the coolest Halloween costumes I have ever seen! 😂😂

The future of #ArtificialIntelligence is not pre-determined. As a technology developed by human beings, its future depends on the choices we make. We therefore have the responsibility to guide, change and, when necessary, reject its applications. A reliable system that serves the human person is of greater value than one that is exceptionally powerful but whose consequences cannot be adequately foreseen or controlled.

We made it to @TheOnion midterm highlights, folks.

Famous last words.