Huck Bennett
@huckbennett.bsky.social
Faculty at the University of Colorado. Interested in theoretical computer science, and especially lattices. Also: mountains, running, music.
https://home.cs.colorado.edu/~hbennett/
https://home.cs.colorado.edu/~hbennett/
There's www.cfail.org for cryptography.
Home | CFAIL
www.cfail.org
November 6, 2025 at 3:35 PM
There's www.cfail.org for cryptography.
Naive question: how are these perturbations related to smoothed analysis perturbations? They're only to b (instead of also A) and they're uniform instead of Gaussian?
October 27, 2025 at 4:05 AM
Naive question: how are these perturbations related to smoothed analysis perturbations? They're only to b (instead of also A) and they're uniform instead of Gaussian?
Nice, thanks Martin!
October 21, 2025 at 10:42 PM
Nice, thanks Martin!
Before this workshop, I was under the (sad!) impression that naive O(n^3) MM was all that was used in practice because of better constants and caching. But, experts there told us (IIRC) that sub-cubic algorithms can be made faster in practice even for n in the 100s. 5/5
October 21, 2025 at 5:32 PM
Before this workshop, I was under the (sad!) impression that naive O(n^3) MM was all that was used in practice because of better constants and caching. But, experts there told us (IIRC) that sub-cubic algorithms can be made faster in practice even for n in the 100s. 5/5
There were several other talks on asymptotically faster algorithms, which is my main interest, but for now it seems like just figuring out how to optimize variants of Strassen might lead to the largest practical gains. 4/
October 21, 2025 at 5:32 PM
There were several other talks on asymptotically faster algorithms, which is my main interest, but for now it seems like just figuring out how to optimize variants of Strassen might lead to the largest practical gains. 4/
... three main parts to the MM stack:
1. Asymptotically fast (sub-cubic) algorithms. (www.youtube.com/live/LhkVS6e...)
2. Better constants within algorithms. (www.youtube.com/live/6lA9JoC...)
3. Managing the memory hierarchy (caching)/communication costs. (www.youtube.com/live/eOBtxE8...)
3/
1. Asymptotically fast (sub-cubic) algorithms. (www.youtube.com/live/LhkVS6e...)
2. Better constants within algorithms. (www.youtube.com/live/6lA9JoC...)
3. Managing the memory hierarchy (caching)/communication costs. (www.youtube.com/live/eOBtxE8...)
3/
Tensors and their uses, especially for matrix multiplication (Part 1)
YouTube video by Simons Institute for the Theory of Computing
www.youtube.com
October 21, 2025 at 5:32 PM
... three main parts to the MM stack:
1. Asymptotically fast (sub-cubic) algorithms. (www.youtube.com/live/LhkVS6e...)
2. Better constants within algorithms. (www.youtube.com/live/6lA9JoC...)
3. Managing the memory hierarchy (caching)/communication costs. (www.youtube.com/live/eOBtxE8...)
3/
1. Asymptotically fast (sub-cubic) algorithms. (www.youtube.com/live/LhkVS6e...)
2. Better constants within algorithms. (www.youtube.com/live/6lA9JoC...)
3. Managing the memory hierarchy (caching)/communication costs. (www.youtube.com/live/eOBtxE8...)
3/
I think a great project for someone would be to write a paper on "Fast Full-Stack MM." To the best of my knowledge, nothing like this exists. It would be very useful to survey the parts of the stack and how they fit together. What I got from the Simons boot camp is that there are ... 2/
October 21, 2025 at 5:32 PM
I think a great project for someone would be to write a paper on "Fast Full-Stack MM." To the best of my knowledge, nothing like this exists. It would be very useful to survey the parts of the stack and how they fit together. What I got from the Simons boot camp is that there are ... 2/
I was about an hour ahead of you today, and it was definitely bad. I love the AB bus, but I'm not sure what was going on. It was the worst that I've seen it (other than the end of spring break, but they sent extra buses then), and I say that having ridden it >30 times in the last two years.
October 12, 2025 at 11:58 PM
I was about an hour ahead of you today, and it was definitely bad. I love the AB bus, but I'm not sure what was going on. It was the worst that I've seen it (other than the end of spring break, but they sent extra buses then), and I say that having ridden it >30 times in the last two years.
Make America go to bed at a reasonable hour again?
October 3, 2025 at 12:19 AM
Make America go to bed at a reasonable hour again?
Correction of link to Schönhage's paper: dl.acm.org/doi/10.1137/.... (The result is Eq. 15.12 in the linked Algebraic Complexity Theory book.)
Partial and Total Matrix Multiplication | SIAM Journal on Computing
In 1979 considerable progress was made in estimating the complexity of matrix multiplication.
Here the new techniques and recent results are presented, based upon the notion of
approximate rank and th...
dl.acm.org
September 21, 2025 at 6:36 PM
Correction of link to Schönhage's paper: dl.acm.org/doi/10.1137/.... (The result is Eq. 15.12 in the linked Algebraic Complexity Theory book.)
Specifically, the MM tensors <4, 1, 4> and <1, 3^2, 1> corresponds to outer and inner products and have border rank 16 and 9, respectively. But, <4, 1, 4> \oplus <1, 3^2, 1> has border rank 17 << 16 + 9 = 25 ! This result is due to Schönhage '81: dl.acm.org/doi/10.1137/.... 2/2
Algebraic Complexity Theory
The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century...
link.springer.com
September 21, 2025 at 6:35 PM
Specifically, the MM tensors <4, 1, 4> and <1, 3^2, 1> corresponds to outer and inner products and have border rank 16 and 9, respectively. But, <4, 1, 4> \oplus <1, 3^2, 1> has border rank 17 << 16 + 9 = 25 ! This result is due to Schönhage '81: dl.acm.org/doi/10.1137/.... 2/2
Awesome community service on your part :-).
August 10, 2025 at 7:24 PM
Awesome community service on your part :-).
"More verys can be provided by the author upon request" is a very nice touch!
July 4, 2025 at 4:38 AM
"More verys can be provided by the author upon request" is a very nice touch!
I'm curious what you have in mind for "AI for TCS" past "I got my LLM to (help) prove this theorem for me," which seems mostly beyond the current capability of LLMs.
June 26, 2025 at 4:33 PM
I'm curious what you have in mind for "AI for TCS" past "I got my LLM to (help) prove this theorem for me," which seems mostly beyond the current capability of LLMs.