@booleananalysis.bsky.social
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...
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
Screenshot of the title and abstract of https://arxiv.org/abs/2507.06010.
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
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.)
J-Live's Braggin' Writes has my top 'thesis' verse, though. ("I displays my credentials over instrumentals...")
20.05.2025 02:42 — 👍 1 🔁 0 💬 0 📌 0This!
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."
There's a reason I called it Quantum Computer Programming in 100 Easy Lessons.
04.04.2025 11:13 — 👍 6 🔁 0 💬 0 📌 0Meming aside, this looks like a cool paper...
04.04.2025 11:11 — 👍 3 🔁 0 💬 1 📌 0Sigbovik's looking good this year. Come for the tom7/suckerpinch video preview, stay for Shor vs a random number generator...
02.04.2025 11:24 — 👍 4 🔁 0 💬 0 📌 0I did not know this!
14.03.2025 21:57 — 👍 2 🔁 0 💬 0 📌 0Also Aayush Jain!
10.03.2025 21:43 — 👍 0 🔁 0 💬 1 📌 0#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th.
Apply here: stoc2025theoryfest.netlify.app
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!
[...] "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"?
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 [...]
Group theory puzzle. We have symbols ♀️,🏁,♂️.
Also define ♕=♀️🏁♀️⁻¹🏁⁻¹ and ♔=♂️🏁♂️⁻¹🏁⁻¹.
We posit:
♀️♕=♕♀️ and 🏁♕=♕🏁 and ♂️♔=♔♂️ and 🏁♔=♔🏁.
And we posit:
♀️²⁰²⁵=🏁²⁰²⁵=♂️²⁰²⁵=1 (identity).
Can you prove ♕♔=♔♕?
Wow, very cool question!
14.01.2025 19:11 — 👍 2 🔁 0 💬 0 📌 0... 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!
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...
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
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.
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)?
20.12.2024 14:51 — 👍 1 🔁 0 💬 0 📌 0This is a great book! If you're not at the beach, keep it at your bedside table for some nighttime reading.
20.12.2024 14:20 — 👍 3 🔁 0 💬 0 📌 0
Some old photos, of JK, ME, DB, and SD.
In case you're in Cambridge, MA on Tue. Dec. 10, I'll give a talk at 4pm (MIT 32-G449) about coboundary expansion in high-dimensional expanders.
It's kind of about group theory, though.
toc.csail.mit.edu/node/1671
Besides coauthor Noah Singer (@singerng_), here's the cast of characters:
Never going to let you down:https://www.cs.cmu.edu/~odonnell/slides/time-travel.ppsx
(Warning, 10MB PowerPoint file.)
If you're into this stuff, I got a new one. With time-traveling (qu)bits, you can solve all problems reducible to the Halting problem.
Or, for spoilsports, getting an (approximate) sample from a Markov chain (/quantum channel) given by a Turing Machine is Delta_2-complete.
arxiv.org/abs/1609.05507
Bhangale, Khot, Liu, and Minzer improved the bounds for combinatorial lines of length 3, established in the Polymath project on the Hales-Jewett problem. Interestingly, this is done from a TCS perspective using pseudorandomness and inverse theorems for CSPs.
eccc.weizmann.ac.il/report/2024/...
Great new quantum algorithm for approximate polynomial interpolation on the arXiv today:
"given a uniformly random vector y of F_q^q, some integers k<q and u < q/2, find a polynomial P(x) of degree <k such that
|P(i)-y_i| < u for all i".
quantum computers can help here (1/4)