Lightnews — Scholar-powered news

Reposted by Ryan O'Donnell

Dr. Tom 7 Murphy VII Ph.D. ! @tomvii.bsky.social · 22d

Feeling depressed and anxious about the state of the world? Try working on a 375 year-old math problem from the Platonic realm, which should be completely psychologically safe . . .
youtu.be/QH4MviUE0_s

Rupert's Snub Cube and other Math Holes

YouTube video by suckerpinch

youtu.be

2 18 77

Ryan O'Donnell @booleananalysis.bsky.social · Aug 26

Please take a minute and nominate your favourite paper from FOCS 1995, 2005, or 2015 for the FOCS Test Of Time Award!

1995 papers: dblp.org/db/conf/focs...

2005 papers: dblp.org/db/conf/focs...

2015 papers: dblp.org/db/conf/focs...

Nomination instructions here:
tc.computer.org/tcmf/2025/08...

FOCS Test of Time Award - Call for Nominations 2025 - IEEE Computer Society Technical Committee on Mathematical Foundations of Computing

FOCS 2025 Test of Time Awards Call for Nominations The 2025 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of...

tc.computer.org

2

Reposted by Ryan O'Donnell

xenaproject.bsky.social @xenaproject.bsky.social · Aug 4

NSF announces funding for ICARM: the Institute for Computer-Aided Reasoning in Mathematics, based in Carnegie-Mellon . Amazing! Carnegie-Mellon press release here: www.cmu.edu/news/stories...

www.nsf.gov/news/nsf-inv...

NSF invests over $74 million in 6 mathematical sciences research institutes

The U.S. National Science Foundation is investing over $74 million in six research institutes focused on the mathematical sciences and their broad applications in all fields of science, technology and...

www.nsf.gov

1 7 16

Reposted by Ryan O'Donnell

John Watrous @johnwatrous.bsky.social · Jul 16

After 3 1/2 years of work my course on quantum computing is finally finished — the "Director's Cut" of Understanding Quantum Information and Computation is now available.

arxiv.org/abs/2507.11536

Understanding Quantum Information and Computation

This is a course on the theory of quantum computing. It consists of 16 lessons, each with a video and written component, covering the basics of quantum information, quantum algorithms (including query...

arxiv.org

5 35 150

Reposted by Ryan O'Donnell

Chirag Wadhwa @emose.bsky.social · Jul 9

New work with @booleananalysis.bsky.social! We prove instance-optimal bounds for quantum state certification when testers can measure all copies simultaneously, finding that the optimal copy complexity depends on how close to maximally mixed the hypothesis state is.

arxiv.org/abs/2507.06010

1/3

Screenshot of the title and abstract of https://arxiv.org/abs/2507.06010.

1 1 14

Ryan O'Donnell @booleananalysis.bsky.social · Jun 9

Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan--

cs.unibocconi.eu/call-nominat...

(Intent-to-nominate letters due by July 31.)

cs.unibocconi.eu

1 18 46

Ryan O'Donnell @booleananalysis.bsky.social · May 20

J-Live's Braggin' Writes has my top 'thesis' verse, though. ("I displays my credentials over instrumentals...")

1

Ryan O'Donnell @booleananalysis.bsky.social · May 17

This!

I like to say,

"Let p|A denote distribution p conditioned on event A.

Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.

Except you don't have to imagine, because it's literally our world!

Now explore probabilistic algorithms in this world."

1 4 32

Ryan O'Donnell @booleananalysis.bsky.social · Apr 4

There's a reason I called it Quantum Computer Programming in 100 Easy Lessons.

6

Ryan O'Donnell @booleananalysis.bsky.social · Apr 4

Meming aside, this looks like a cool paper...

1 3

Ryan O'Donnell @booleananalysis.bsky.social · Apr 2

Sigbovik's looking good this year. Come for the tom7/suckerpinch video preview, stay for Shor vs a random number generator...

Craig Gidney @craiggidney.bsky.social · Apr 1

For sigbovik, I factored all 8 bit ints (up to 255) with a quantum computer github.com/strilanc/fal...

I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.

It took 121 quantum samples to finish the entire task.

But...

4

Ryan O'Donnell @booleananalysis.bsky.social · Mar 14

I did not know this!

2

Ryan O'Donnell @booleananalysis.bsky.social · Mar 10

Also Aayush Jain!

1

Reposted by Ryan O'Donnell

Anupam Gupta @anupamg.bsky.social · Feb 27

#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th.

Apply here: stoc2025theoryfest.netlify.app

Vite + React + TS

stoc2025theoryfest.netlify.app

7 9

Reposted by Ryan O'Donnell

Ryan Williams @rrwilliams.bsky.social · Feb 21

New paper: Simulating Time With Square-Root Space

people.csail.mit.edu/rrw/time-vs-...

It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].

To appear in STOC. Comments are very welcome!

people.csail.mit.edu

17 74 270

Ryan O'Donnell @booleananalysis.bsky.social · Feb 10

[...] "x1 += x2" and "x1 += x3". Similarly for "x2 -= x4".

Finally, we posit: Doing "x1 += x2" 256 times in a row is equivalent to doing nothing
(maybe shoulda called it "x1 += x2 mod 256")
and sim. for doing "x2 += x3", "x3 += x4" 256x in a row.

Can you prove "x1 -= x3" commutes with "x2 -= x4"?

1

Ryan O'Donnell @booleananalysis.bsky.social · Feb 10

PL puzzle. Say we have instructions called
"x1 += x2", "x2 += x3", "x3 += x4",
and versions with "-=" that cancel them.

We define a program
"x1 += x2"
"x2 += x3"
"x1 -= x2"
"x2 -= x3",
and abbreviate it "x1 -= x3". We similarly define "x2 -= x4".

We posit that "x1 -= x3" commutes with [...]

1 1

Ryan O'Donnell @booleananalysis.bsky.social · Feb 8

Group theory puzzle. We have symbols ♀️,🏁,♂️.
Also define ♕=♀️🏁♀️⁻¹🏁⁻¹ and ♔=♂️🏁♂️⁻¹🏁⁻¹.

We posit:
♀️♕=♕♀️ and 🏁♕=♕🏁 and ♂️♔=♔♂️ and 🏁♔=♔🏁.
And we posit:
♀️²⁰²⁵=🏁²⁰²⁵=♂️²⁰²⁵=1 (identity).

Can you prove ♕♔=♔♕?

3

Ryan O'Donnell @booleananalysis.bsky.social · Jan 14

Wow, very cool question!

2

Ryan O'Donnell @booleananalysis.bsky.social · Jan 9

... which is to formalize the analogous theorems for the B_3 case (specifically, Sec. 8 of my recent paper with Noah: arxiv.org/pdf/2411.05916).

The proofs there are 70 pages of Noah solving the word problem by hand. So it will be nice to have a computer check his work -- a team is being assembled!

arxiv.org

7

Ryan O'Donnell @booleananalysis.bsky.social · Jan 9

Cayden Codel & Noah Singer have formalized in Lean the climactic theorems of the Kaufman-Oppenheim paper that shows the A_3-type coset complex HDXs are cosystolic expanders! (I.e., Sec. 7.2 of arxiv.org/abs/1907.01259)

It's a warmup for the main project...

arxiv.org

1 1 9

Ryan O'Donnell @booleananalysis.bsky.social · Jan 8

Bravo to 1st-year undergraduate Tyler Yang at CMU, who was the first person to write up and make videos for all* 100 exercises in my "Quantum Computer Programming in 100 Easy Lessons" series! (www.youtube.com/watch?v=XtDJ...)

*more or less all

#1/100: Toggling qubits || Quantum Computer Programming in 100 Easy Lessons

YouTube video by Ryan O'Donnell

www.youtube.com

1 14

Ryan O'Donnell @booleananalysis.bsky.social · Dec 31

Random d-regular graphs are (2-sided) Ramanujan with probability 69%:

arxiv.org/pdf/2412.20263 by Jiaoyang Huang, Theo Mckenzie, HT Yau.

In particular, infinitely many 7-regular Ramanujan graphs exist.

8 23

Ryan O'Donnell @booleananalysis.bsky.social · Dec 20

There's a nice recentish paper that finds the longest increasing subsequence in space O(S) and time O~(n^2/S) provides S is at least sqrt(n). An open question I like: Is there a poly-time algorithm with S=o(sqrt n)?

1

Ryan O'Donnell @booleananalysis.bsky.social · Dec 20

This is a great book! If you're not at the beach, keep it at your bedside table for some nighttime reading.

3