If you value quality over quantity, consider signing the TCS hiring statement. Bean counting is obsolete. No point in pushing students to produce more and more AI-generated papers.
njbergam.github.io/tcs-hirin…
i’m increasingly of the opinion that almost everyone agrees with this, but a big fraction of people aren’t comfortable saying it in public, because of what it implies for the bean counting mechanism the whole machine is built on (for awards/promo/hiring/etc).
In 1966, Paul Cohen won the Fields medal for showing the independence of: the continuum hypothesis and the axiom of choice.
Gödel reacted to Cohen’s Fields medal by saying that he had already proved the result in the 1940s. Yet when pushed for a proof by his peers, Gödel was unable to reconstruct one from his notes.
"The first task von Plato set Claude was to discover if Gödel’s workbooks had a proof of the independence of the axiom of choice, which would reveal that Gödel had been telling the truth in 1966.
The answer came back: yes, almost. “He was just one step away,”"
Ruben and I are thankful for the support of Microsoft Quantum to do fundamental research on the capabilities of measurement-based quantum computing. In particular, we really want to understand how intermediate classical processing can help (or not) with steering a quantum computation. Ruben and I come from very different backgrounds -- he's a condensed matter theorist, and I'm a computer scientist -- but we've realized that we care a lot about the same questions. An example of a question we are really interested in is how the computational power of the classical processor can affect what kinds of quantum states can be prepared by shallow, dynamic quantum circuits.
"Columbia Computer Scientist Henry Yuen Is Looking to Make the Most of Microsoft’s Quantum Hardware
Yuen and University of Chicago's Ruben Verresen have received $100,000 from the company’s Quantum Pioneers Program."
quantum.columbia.edu/news/co…@ColumbiaQuantum@EE_ColumbiaSEAS
I've been skeptical of various efforts involving the publicly-made STOC 2027 submissions, but this is cool. Trying to contribute to it wrt my own submission.
🚀 STOC 2027, a flagship conference in theoretical computer science, made all 1,665 submissions publicly available. So we launched the STOC 2027 Formalization Initiative on Prove2Me!
Our AI agents have translated the main theorems and supporting lemmas of 1,496 submissions into Lean 4 statements!
Some already have completed proof formalizations, with many more awaiting contributions.
You don't need to know Lean or fully understand the underlying mathematics to get started! If you know how to work with AI agents, you can help formalize proofs.
We invite authors, researchers, and the broader community to explore these formalized statements, check them against the original papers, and contribute proof formalizations!
📊 Explore the initiative: stoc2027formalization.vercel…
🤝 Contribute proof formalizations: prove2.me/collections/acm-st…
🚀 STOC 2027, a flagship conference in theoretical computer science, made all 1,665 submissions publicly available. So we launched the STOC 2027 Formalization Initiative on Prove2Me!
Our AI agents have translated the main theorems and supporting lemmas of 1,496 submissions into Lean 4 statements!
Some already have completed proof formalizations, with many more awaiting contributions.
You don't need to know Lean or fully understand the underlying mathematics to get started! If you know how to work with AI agents, you can help formalize proofs.
We invite authors, researchers, and the broader community to explore these formalized statements, check them against the original papers, and contribute proof formalizations!
📊 Explore the initiative: stoc2027formalization.vercel…
🤝 Contribute proof formalizations: prove2.me/collections/acm-st…
🚀 STOC 2027, a flagship conference in theoretical computer science, made all 1,665 submissions publicly available. So we launched the STOC 2027 Formalization Initiative on Prove2Me!
Our AI agents have translated the main theorems and supporting lemmas of 1,496 submissions into Lean 4 statements!
Some already have completed proof formalizations, with many more awaiting contributions.
You don't need to know Lean or fully understand the underlying mathematics to get started! If you know how to work with AI agents, you can help formalize proofs.
We invite authors, researchers, and the broader community to explore these formalized statements, check them against the original papers, and contribute proof formalizations!
📊 Explore the initiative: stoc2027formalization.vercel…
🤝 Contribute proof formalizations: prove2.me/collections/acm-st…
You can test whether n is prime deterministically and in polynomial time in 10 lines of Python. This algorithm is Gary Miller's from 50 years ago. But the proof requires OpenAI's recent quasi-GRH result!
The AKS primality test was a huge deal (Gödel and Fulkerson prizes in 2006) but now it's obsolete. Crazy times.
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.
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.
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".
I think this result strongly suggests that quantum computers do *not* have an exponential advantage when attempting to break secure hash functions. Gg, CRQCs.
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 (such as @danboneh).
Our 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…