iiinova — where your digital self keeps evolving

Reposted by Henry Yuen

Aviad Rubinstein @aviad-rubinstein.bsky.social · 08/10/2026

I've heard a lot of sad voices in our community who are "depressed" and "completely crushed" by the new wave of AI results. I'm actually very optimistic. I don't have particularly good rationales, but emotionally speaking, let me try to infect you with a bit of my optimism if you need it. 1/n

1323

Henry Yuen @henryyuen.bsky.social · 28/09/2026

I know this is not the intended effect but I am getting an intense wave of nostalgia.

030

Henry Yuen @henryyuen.bsky.social · 15/09/2026

"... one might strive further to get the best of both worlds: "Rich" 2-to-1 with perfect completeness (eccc.weizmann.ac.il/report/2019/...). That would imply both results. Perhaps the rumors might concern this?"

eccc.weizmann.ac.il

ECCC - TR19-141

010

Henry Yuen @henryyuen.bsky.social · 15/09/2026

"Then it's true that UGC is somewhat different, being stronger in one sense (1-to-1) and weaker in another (imperfect completeness). But..."

100

Henry Yuen @henryyuen.bsky.social · 15/09/2026

I asked Ryan O'Donnell on the *other* social media site: "I guess this result is morally close to 2-to-1 Conjecture with perfect completeness. (Maybe with tweaking you can get 4->2, who knows.) "

130

Reposted by Henry Yuen

Ryan O'Donnell @booleananalysis.bsky.social · 10/09/2026

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.

youtube.com

Complexity Theory At Carnegie Mellon

05717

Reposted by Henry Yuen

Chris Peikert @chrispeikert.bsky.social · 02/08/2026

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!

1164

Reposted by Henry Yuen

Clément Canonne @ccanonne.github.io · 01/08/2026

"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/

620451

Reposted by Henry Yuen

Huck Bennett @huckbennett.bsky.social · 02/08/2026

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/

1276

Henry Yuen @henryyuen.bsky.social · 01/08/2026

There's a lot more to say here, but I think we mathematicians and theoreticians will have our work cut out for us: to keep a leash on these collossi of thought and reasoning, and to keep their abilities intelligible to humankind.

6913

Henry Yuen @henryyuen.bsky.social · 01/08/2026

What happens when AI has answered the handful of my favorite problems that I've spent the last 15 years thinking about? There are a lot of nice problems that I like, but it's not so easy to find a *favorite* problem.

2696

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I'm in awe, and excited to see what other things we will learn from the AIs. There are a number of problems I've spent a long time thinking about, and maybe I will learn how to answer them soon. But -- what then?

1491

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I wish OpenAI had spent a couple more prompts to clean up the writeup (I haven't had a chance to look at the other writeups so can't comment on their writing quality). Yes, there's a Lean proof. But that doesn't give me any understanding. That will just take time, I guess.

2491

Henry Yuen @henryyuen.bsky.social · 01/08/2026

Normally, when I read a paper like this, I get immediately suspicious. What are they trying to hide by not explaining the new ideas up front and center?

1462

Henry Yuen @henryyuen.bsky.social · 01/08/2026

the particular Uhlmann transformation/dilation used to "align" all the states together. The technically interesting parts are buried deep into the paper, in Section 4, and introduced without any fuss or fanfare, as if this were the obvious thing to do.

2520

Henry Yuen @henryyuen.bsky.social · 01/08/2026

It writes in a way that's characteristic of a lot of ChatGPT-generated proofs, in which it elaborates at length on "boilerplate" setup, but then nonchalantly introduces what I consider to be the technical crux of the result:

2621

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I would love to hear from experts who find these calculations familiar. I might write about this again when I understand better. I am disappointed by the writeup of this proof (sorry Lijie -- I should've taken a look at it earlier!).

2530

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I spent about an hour this morning asking ChatGPT these questions, but it's somewhat frustrating because it speaks with a mishmash of physicist, operator algebraist, quantum information theorist-lingo, plus the usual LLM breezy lilt that annoys everybody.

1802

Henry Yuen @henryyuen.bsky.social · 01/08/2026

Is there some broader context or theory within which this would've been the obvious thing to do? What other results can be proven using these techniques? What is it telling us about quantum information or operator theory? I have no idea.

1702

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I don't understand it yet. Maybe it'll take me an afternoon to check all the calculations, but what would still be missing is why this was an approach that would've made sense in the first place.

2742

Henry Yuen @henryyuen.bsky.social · 01/08/2026

The reasoning document furnished by OpenAI is interesting but opaque: it states the problem, and then there's a leap of intuition on how to find the right purification using the "resolvent", and then does some exotic matrix entropy calculations to show that it works out.

2521

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I am gratified that it starts from where my paper left off, but goes beyond the limitations of my proof strategy by using some tricks and techniques that are probably known, in some collective fashion, to operator theorists and functional analysts.

1533

Henry Yuen @henryyuen.bsky.social · 01/08/2026

Life was busy so I didn't get a chance to look, but I guess now the cat's out of the bag so I probably should opine a bit. I presume the proof is correct (there's supposedly a Lean formalization, after all), but it will take me some time to digest it.

2510

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I always intended to come back to it. Actually, a month ago I tried to set GPT 5.5 on it, and it didn't make very much progress. A couple days ago Lijie Chen sent me and a couple others a writeup.

1470

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I wouldn't want to trade that experience for anything. Now, to the math. In 2016 I proved a polynomial-decay theorem; the exponential-decay theorem was left open and has since remained one of my favorite problems.

1560

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I learned a lot of mathematics from it, and most importantly I learned that I could solve hard problems that (some) people cared about. I wouldn't say it's anywhere close to the most important problems in quantum information theory -- but nonetheless I fell in love with it as a grad student.

1730

Henry Yuen @henryyuen.bsky.social · 01/08/2026

I spent many hours, days, nights, weekends in cafes, in my office, at home, trying to understand Ran Raz's classical parallel repetition theorem and whether I could prove a quantum version of it. This period of struggle was important for me.

1835

Henry Yuen @henryyuen.bsky.social · 01/08/2026

feel their importance in my bones; I deeply care about the answers to these questions. And then -- the kicker -- something that I personally spent a couple years on in grad school, leading to some of my proudest work: quantum parallel repetition theorems.

1632

Henry Yuen @henryyuen.bsky.social · 01/08/2026

New circuit lower bounds? A simple, easy-to-describe non-sofic group? Hardness of approximation for CVP without needing a unique games-like conjecture? I didn't just hear about these problems from my friends or from seminars.

1662

Henry Yuen @henryyuen.bsky.social · 01/08/2026

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.

233072

Henry Yuen @henryyuen.bsky.social · 30/07/2026

I would very much like to watch a screenplay or a play written by you about this.

010

Reposted by Henry Yuen

Quanta Magazine @quantamagazine.org · 08/07/2026

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-...

0359

Henry Yuen @henryyuen.bsky.social · 04/06/2026

This sounds exciting! I don't know the context/history of this problem, do you have any recommendations for papers/references that give a good summary?

020

Henry Yuen @henryyuen.bsky.social · 04/06/2026

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

0201

Henry Yuen @henryyuen.bsky.social · 28/05/2026

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

0101

Reposted by Henry Yuen

Clément Canonne @ccanonne.github.io · 12/05/2026

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...

The following seven STOC TheoryFest 2026 workshops will take place during the morning sessions from Monday through Friday:
Machine Learning for Algorithms
Organizers: Nina Balcan, Avrim Blum, Piotr Indyk, Ali Vakilian
Dates: June 22-24
The Random Purification Channel in Quantum Tomography
Organizers: Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright
Dates: June 22-24
The Role of Theory in Trustworthy and Interpretable AI
Organizers: Noah Golowich, Allen Liu, Abhishek Shetty
Dates: June 22-24
Algorithmic Frontiers of Graph and Hypergraph Problems via Global Queries
Organizers: Deeparnab Chakrabarty and Sagnik Mukhopadhyay
Dates: June 22-24
Understanding Large Language Models via a TCS Lens
Organizers: Anay Mehrotra, Amin Saberi, Grigoris Velegkas
Dates: June 25-26
Building New Algorithmic Foundations for Cryptography
Organizers: Aayush Jain, Amit Sahai
Dates: June 25-26
Testing in the Modern World
Organizer: Anindya De
Dates: June 25-26
The following STOC TheoryFest 2026 workshop will be held all day Saturday:
Can AI do Theory?
Organizer: Pritish Kamath, Pravesh Kothari, Mariana Raykova, Abhradeep Thakurta, Nikhil Vyas
Date: June 27

0113

Reposted by Henry Yuen

Ben Brubaker @benbenbrubaker.bsky.social · 11/05/2026

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!

quantamagazine.org

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.

071

Henry Yuen @henryyuen.bsky.social · 27/04/2026

Congratulations Gautam! Really well deserved!

020

Henry Yuen @henryyuen.bsky.social · 10/04/2026

We thank Air Force Office of Scientific Research (AFOSR) for their enthusiastic support of basic, fundamental research.

000

Henry Yuen @henryyuen.bsky.social · 10/04/2026

Could there be algorithmic or fault tolerance benefits to using such higher order quantum operations? We'll be looking at this from a theory, systems, and experimental angle. This is a great opportunity to explore unconventional approaches to designing quantum computers.

140

Henry Yuen @henryyuen.bsky.social · 10/04/2026

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.

1111

Henry Yuen @henryyuen.bsky.social · 25/03/2026

Congrats Sophie, that's very exciting!

131

Henry Yuen @henryyuen.bsky.social · 02/03/2026

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.

1177

Henry Yuen @henryyuen.bsky.social · 18/02/2026

I remember the summer of 2007 after freshman year. I was lucky to land a summer internship with CACS, to redesign the group website. I was pretty intimidated to be sharing an office with you. One day, I snuck a glance back at you and relaxed when I saw that you were browsing guitars on craigslist.

110

Henry Yuen @henryyuen.bsky.social · 17/02/2026

My thoughts: "how much longer is he going to ask me to stand here looking off into the distance?"

190

Henry Yuen @henryyuen.bsky.social · 17/02/2026

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.

1303