this is great: a unified and transparent exposition of the recent breakthroughs on the decoding of Reed-Solomon codes.
eccc.weizmann.ac.il/report/2026/23…
eccc.weizmann.ac.il/report/2026/23…
0 5 1 32 4.9K 12
Ryan O'Donnell
@BooleanAnalysis
Videos: youtube.com/ryanodonnellte…
7.7KFollowers
0Following
739Posts
234Media
1.5KLikes
@BooleanAnalysis reposted
@BooleanAnalysis reposted
The what now?!
arxiv.org/abs/2610.06783…
arxiv.org/abs/2610.06783…
58 196 142 1.9K 1M 1.3K
STOC 2027 Call for Papers is out:
acm-stoc.org/stoc2027/stoc2…
Note quite a lot of changes from previous STOC CfPs.
acm-stoc.org/stoc2027/stoc2…
Note quite a lot of changes from previous STOC CfPs.
4 19 4 117 35.7K 21
Outstanding progress towards the Unique Games Conjecture posted by Yumou Fei, Dor Minzer, and Shuo Wang: eccc.weizmann.ac.il/report/2026/17…
👀
👀
4 35 3 214 46.5K 76
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 youtube.com/@ComplexityThe… which will later also feature student videos.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
7 99 10 661 72.9K 486
I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group:
youtu.be/uOQvzLjJK6c
youtu.be/uOQvzLjJK6c
3 23 4 165 48.3K 80
FOCS 2026 Test of Time call for nominations is out:
tc.computer.org/tcmf/2026/05/1…
Please submit your nominations! More info on the award here:
tc.computer.org/tcmf/focs-test…
and here's DBLP links for FOCS '16, '06, '96:
dblp.org/db/conf/focs/f…
dblp.org/db/conf/focs/f…
dblp.org/db/conf/focs/f…
tc.computer.org/tcmf/2026/05/1…
Please submit your nominations! More info on the award here:
tc.computer.org/tcmf/focs-test…
and here's DBLP links for FOCS '16, '06, '96:
dblp.org/db/conf/focs/f…
dblp.org/db/conf/focs/f…
dblp.org/db/conf/focs/f…
0 4 0 21 3.4K 4
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 @singerng_, here's the cast of characters:
It's kind of about group theory, though.
toc.csail.mit.edu/node/1671
Besides coauthor @singerng_, here's the cast of characters:
1 2 0 24 3.9K 4
Student I know wants to apply for a PhD program doing quantum computing. But she also wants to be in the *math* department.
My brain couldn't do the lookup "QC person but in Math dept." Any suggestions for universities having such a person? Diverse suggestions (by DM) welcome!🙏
My brain couldn't do the lookup "QC person but in Math dept." Any suggestions for universities having such a person? Diverse suggestions (by DM) welcome!🙏
26 1 1 49 13.6K 14
I just posted the 100th and final video in my YouTube course, "Quantum Computer Programming in 100 Easy Lessons".
If you're interested in learning quantum computing, and you have some 100 consecutive days with a half-hour free, maybe check it out :-)
youtube.com/playlist?list=…
If you're interested in learning quantum computing, and you have some 100 consecutive days with a half-hour free, maybe check it out :-)
youtube.com/playlist?list=…
1 24 1 156 12.9K 83
In case you're in the Boston area, I'll talk about "Quartic quantum speedups for planted inference" tomorrow (Sep. 13) at Harvard at 4pm.
This is at the Freedman CSMA Seminar. cmsa.fas.harvard.edu/event/freedman…
This is at the Freedman CSMA Seminar. cmsa.fas.harvard.edu/event/freedman…
0 1 0 11 2.2K 1
Final quantum course tidbit #10: In the course, we do Grover's algorithm (i.e., SAT in (√2)ⁿ quantum time) before doing the Factoring algorithm.
Always seems funny to me that most courses do them in the other order. (Why is this? To follow the historical order?)
Not only is Grover much easier than Factoring, there's a straight through-line:
1. Distinguishing two 1-qubit states.
2. Distinguishing two 1-qubit rotations (or reflections).
3. Elitzur-Vaidman Bomb.
4. Grover.
5. Grover when you don't know the fraction of satisfying assignments, by binary search.
6. Rotation (Phase) Estimation for 1-qubit rotations.
7. Very high-precision 1-qubit Rotation Estimation, if you can do any power of the rotation efficiently.
8. General Rotation Estimation when you don't know the plane of rotation (i.e. Phase Estimation with an input eigenvector).
9. Applying Rotation Estimation to the permutation induced by "multiply by B, mod N".
10. Factoring N.
Always seems funny to me that most courses do them in the other order. (Why is this? To follow the historical order?)
Not only is Grover much easier than Factoring, there's a straight through-line:
1. Distinguishing two 1-qubit states.
2. Distinguishing two 1-qubit rotations (or reflections).
3. Elitzur-Vaidman Bomb.
4. Grover.
5. Grover when you don't know the fraction of satisfying assignments, by binary search.
6. Rotation (Phase) Estimation for 1-qubit rotations.
7. Very high-precision 1-qubit Rotation Estimation, if you can do any power of the rotation efficiently.
8. General Rotation Estimation when you don't know the plane of rotation (i.e. Phase Estimation with an input eigenvector).
9. Applying Rotation Estimation to the permutation induced by "multiply by B, mod N".
10. Factoring N.
2 4 0 40 4.4K 13
Quantum course tidbit #9:
So if there are no complex numbers in the course, how do we do Shor's Algorithm?
We don't; we do Kitaev's version of the Factoring algorithm, which just uses Phase Estimation.
Well, not Phase Estimation, but "Rotation Estimation" as we call it, since no complex numbers in the course means no "phases"...
For every real unitary operation U (including the operation "increment a number modulo L" which arises in Factoring), space breaks down into a bunch of orthogonal 2-d planes, where U acts as a 2-d rotation in each plane. (There can also be 1-d axes where U acts as reflection or as identity.)
(In 3-d, this is "Euler's Rotation Theorem", which says that any 3-d rotation is actually a 2-d rotation around some axis.)
"Rotation Estimation" is the quantum algorithm that -- given a real unitary U and a state |v> that's in one of U's 2-d planes of rotation -- outputs the angle by which U rotates that plane. To get the angle to k digits of precision, the algorithm uses U roughly 10^k times.
Contrary to the way Phase Estimation is usually presented, you don't need QFT for this either. It's basically just binary search.
youtube.com/watch?v=YZ7_U3…
So if there are no complex numbers in the course, how do we do Shor's Algorithm?
We don't; we do Kitaev's version of the Factoring algorithm, which just uses Phase Estimation.
Well, not Phase Estimation, but "Rotation Estimation" as we call it, since no complex numbers in the course means no "phases"...
For every real unitary operation U (including the operation "increment a number modulo L" which arises in Factoring), space breaks down into a bunch of orthogonal 2-d planes, where U acts as a 2-d rotation in each plane. (There can also be 1-d axes where U acts as reflection or as identity.)
(In 3-d, this is "Euler's Rotation Theorem", which says that any 3-d rotation is actually a 2-d rotation around some axis.)
"Rotation Estimation" is the quantum algorithm that -- given a real unitary U and a state |v> that's in one of U's 2-d planes of rotation -- outputs the angle by which U rotates that plane. To get the angle to k digits of precision, the algorithm uses U roughly 10^k times.
Contrary to the way Phase Estimation is usually presented, you don't need QFT for this either. It's basically just binary search.
youtube.com/watch?v=YZ7_U3…
0 1 0 26 3.2K 11
Probably the largest set of different home countries I've gotten the chance to lecture to. :)
Thanks to Jan Hązła and the rest of @AIMS_Next for inviting me to participate!
Thanks to Jan Hązła and the rest of @AIMS_Next for inviting me to participate!
AIMS RWANDA@AIMS_Rwanda · Aug 12, 2024We are privileged to have three distinguished lecturers leading courses on the theory of computation (Ryan O'Donnell, Carnegie Mellon University), Error-correcting codes (Venkatesan Guruswami, UC Berkeley) and combinatorial statistical mechanics (Amin Coja-Oghlan, TU Dortmund).
Open quoted post →
0 0 0 31 3.1K 3
Quantum course tidbit #8: youtube.com/playlist?list=…
There're also no complex numbers in my quantum course. Of course I tell the students that qubit amplitudes 𝒄𝒂𝒏 be complex, but we never use them in any of our algorithms.
(Yes, we do the Factoring algorithm in 100% detail!)
There're also no complex numbers in my quantum course. Of course I tell the students that qubit amplitudes 𝒄𝒂𝒏 be complex, but we never use them in any of our algorithms.
(Yes, we do the Factoring algorithm in 100% detail!)
0 0 0 5 1.3K 3
Quantum course tidbit #7: youtube.com/playlist?list=…
There's almost no linear algebra in the course. Arguably, you just need to know how to add and subtract vectors.
What linear algebra there is, I prefer to call "geometry".
(Even matrix multiplication is "paths diagrams".)
There's almost no linear algebra in the course. Arguably, you just need to know how to add and subtract vectors.
What linear algebra there is, I prefer to call "geometry".
(Even matrix multiplication is "paths diagrams".)
0 3 0 20 2K 13
(1/3) Quantum course tidbit #6: youtube.com/playlist?list=…
Why is |EPR> = |00> + |11> special? Because when you draw it as a square, it's the 2x2 identity matrix.
Why is |EPR> = |00> + |11> special? Because when you draw it as a square, it's the 2x2 identity matrix.
1 0 0 3 1.2K 2
(1/6) Quantum course tidbit #5: youtube.com/playlist?list=…
I really enjoy depicting 2- and 3-qubit states as labelings of the vertices of the square/cube by amplitudes. E.g., here is |EPR> = |00> + |11> (remember, we like unnormalized states):
I really enjoy depicting 2- and 3-qubit states as labelings of the vertices of the square/cube by amplitudes. E.g., here is |EPR> = |00> + |11> (remember, we like unnormalized states):
1 0 0 6 748 2
Quantum course tidbit #4 youtube.com/watch?v=Wv83nz…:
I often rename Hadamard to "Add & Dif". Applying it to qubit in state (x,y) takes you to (x+y,x-y). (Remember, we're cool with unnormalized states.) I feel this has somewhat more intuition / is more memorable.
I *also* often rename it to "Avg & Dev". This takes (x,y) to the pair (avg{x,y}, "deviation of x,y from average"). (Remember, we're cool with unnormalized states.) To illustrate, if the amplitudes on |0> and |1> are 13 and 3, the new amplitudes are 8 and 5, reflecting that 13,3 = 8±5.
"Add & Dif" and "Avg & Dev" are exact inverses. That's nice because almost every quantum algorithm does Hadamard an even number of times; moreover, it's almost always natural to replace half of the Hadamards with "Add & Dif" and half with "Avg & Dev". Then you don't even end up unnormalized at the end.
Add & Difs are nice for preparing the uniform superposition (namely amplitude 1 on every basic state), starting from |00...0>.
Avg & Devs are nice for the Hadamard transform; it becomes very clear that the final amplitude on |00...0>, e.g., is the *Average* of all the original amplitudes.
I often rename Hadamard to "Add & Dif". Applying it to qubit in state (x,y) takes you to (x+y,x-y). (Remember, we're cool with unnormalized states.) I feel this has somewhat more intuition / is more memorable.
I *also* often rename it to "Avg & Dev". This takes (x,y) to the pair (avg{x,y}, "deviation of x,y from average"). (Remember, we're cool with unnormalized states.) To illustrate, if the amplitudes on |0> and |1> are 13 and 3, the new amplitudes are 8 and 5, reflecting that 13,3 = 8±5.
"Add & Dif" and "Avg & Dev" are exact inverses. That's nice because almost every quantum algorithm does Hadamard an even number of times; moreover, it's almost always natural to replace half of the Hadamards with "Add & Dif" and half with "Avg & Dev". Then you don't even end up unnormalized at the end.
Add & Difs are nice for preparing the uniform superposition (namely amplitude 1 on every basic state), starting from |00...0>.
Avg & Devs are nice for the Hadamard transform; it becomes very clear that the final amplitude on |00...0>, e.g., is the *Average* of all the original amplitudes.
0 3 0 27 2.5K 16
Quantum course youtube.com/watch?v=XtDJXH… tidbit #3:
I introduce unnormalized states very early.
Every schoolkid knows 1/2 and 3/6 and -4/-8 are same number. As long as you multiply all the numbers you see by the same c (≠0), you get same result.
Same for amplitudes of a state.
I also like to motivate this by going on a rant about how much the expression 1/√2 annoys me...
I introduce unnormalized states very early.
Every schoolkid knows 1/2 and 3/6 and -4/-8 are same number. As long as you multiply all the numbers you see by the same c (≠0), you get same result.
Same for amplitudes of a state.
I also like to motivate this by going on a rant about how much the expression 1/√2 annoys me...
0 1 0 31 2.6K 8