I enjoyed attending the Simons Complexity and Linear Algebra workshop this past week. I learned a cool fact in one of Peter Bürgisser's talks: it's possible to show that the MM exponent satisfies ω < 2.55 by analyzing the complexity of computing an outer and an inner product simultaneously! 1/2

New work on matrix multiplication with Karthik, Sasha, and my student Evelyn. The fastest known algorithms for multiplying arbitrary n x n matrices A, B take O(n^{2.372}) time, but can we do better (ideally deterministically) if their product AB (and potentially A, B themselves) are *sparse*?

Ah, yes, the Baker-Gill-Solovay Theorem is my favorite old timey TV program. What an age of internet search we live in.

Hybrid CS Theory Seminar this Fri 2025-07-18! We're excited to have Alexander Kulikov (JetBrains) presenting "Polynomial formulations as a barrier for reduction-based hardness proofs" alexanderskulikov.github.io www.colorado.edu/cs-theory/th... 🧪 #MathSky #Algorithms #Complexity #TCSSky

I'm in Ann Arbor for the week for ISIT (presenting eprint.iacr.org/2025/187). If anyone else is attending or around, please say "hi"!

"Huh?!" of the day from NSF award reporting: They allow you to upload a .bib file to report your relevant publications (great call!), but in general disallow using "article" as a publication type because of public access requirements. 1/2

Great choice!

A nice obituary about Peter Lax, who recently died at age 99: www.nytimes.com/2025/05/16/s.... He was one of the legendary mathematicians I was always excited to see at Courant, and had quite a personal story.

TIL a useful fact that has a fairly easy proof: If NP is in BPP then RP = NP. The idea is to reduce to SAT, which has a fast search-to-decision reduction, and then use your BPP algorithm for SAT to try to generate a witness. (This is Problem 11.5.18 in Papadimitriou's complexity textbook.)

Happy Earth Day 2025! The Enchantments, WA // Grand Canyon, AZ

Proud advisor moment: My Ph.D. student Matthew Fox (who's co-advised and in CU's physics department) taught a class on quantum computing as the sole instructor at the Colorado School of Mines this semester. He wrote these awesome notes: matthewfoxphysics.com/teaching/QPL....

It's always good to have back-up plans, and now I have a plan for what I'm going to do if I don't get tenure: start a coding-theory-themed comedy club.

I don't often weigh in on AI issues, but had some thoughts based on an interesting recent post by @ilyaraz.bsky.social on LinkedIn. Ilya posted recent comments by two top algorithms researchers noting how well LLMs had done on their algorithms exams. 1/

I am truly honored to be giving the 2025 William Reinhardt Memorial Lecture next week at the University of Colorado Boulder. "How we might have taken the Continuum Hypothesis as a fundamental axiom, necessary for mathematics" www.colorado.edu/math/2025/03...

It was my pleasure to join a jubilant and well-attended rally against the current administration's assault on science in Boulder today. Besides the University of Colorado, Boulder and the surrounding area are home to many national labs, including NIST, NOAA, NCAR, and NREL. 1/2

Periodic reminder for theorists who like to run: join 114 friends in the Running in Theory club on Strava (www.strava.com/clubs/runnin...)! "A club for runners of all levels working or interested in theoretical computer science. Come decrease your running times (asymptotic and otherwise) in style!"

New work with Mitchell Black, Amir Nayyeri, and Evelyn Warton, in which we study what can be learned about a hidden graph using few effective resistance queries: arxiv.org/abs/2502.18350. Evelyn (Amir and my co-advised student) recently did her Ph.D. thesis proposal on the subject of this paper!

This is terrible news, and part of the ongoing assault on science in the U.S. by the new administration. To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/

TIL/realized that there's a close connection between the number of Abelian groups of finite order n and the partition function alpha (en.wikipedia.org/wiki/Partiti.... If n's prime factorization is n = p_1^{e_1} * ... * p_k^{e_k} then the number of groups of order n is alpha(e_1) * ... * alpha(e_k).

I gave a virtual talk at CWI Amsterdam's cryptology seminar today and really enjoyed it. There's not much of a punchline, but rather a reminder/PSA (including to myself) that CWI is awesome.

New work on faster algorithms for the code equivalence problem: eprint.iacr.org/2025/187! This came out of Jean-François Biasse's REU, and three great undergraduates (Drisana Bhatia, Medha Durisheti, and Lucas LaBuff) are among the coauthors.

A *2011* grant from NSERC Research Tools and Instruments, for 60000 CAD, to Geoff Hinton (@geoffreyhinton.bsky.social) For "Large scale machine learning using GPUs" Everything you're seeing now started from a pittance of cash given by the Canadian government for fundamental research

I am one of these NSF postdocs. NSF has frozen everyone’s access to their salaries and research stipends (that were already awarded) with no information about when they might be expected to be unfrozen. It still appears like we are expected to continue doing our work though.

I don't have much to add past what other people have written, but I'm furious with executive order M-25-13's broad assault on American science and universities and the precedent it sets (even if it's now rescinded).

My cousin Liz (@koslov.bsky.social), who is a UCLA professor and studies the impact of natural disasters and climate change on cities, co-wrote a NYT op-ed on the recent LA fires. Check it out: www.nytimes.com/2025/01/19/o...!

A new proof marks the first progress in decades on important cases of the “kissing spheres” problem. 😚 @gregbarber.bsky.social reports: www.quantamagazine.org/mathematicia...

Work with Surendra Ghentiyala and Noah Stephens-Davidowitz to be presented at ITCS '25 in a few days: "The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions," eccc.weizmann.ac.il/report/2024/.... Check out Surendra's talk if you're attending! 1/

I'm nearing the end of teaching graduate algorithms, and am having fun with our last unit on quantum algorithms, which I've never taught before. As part of preparing, I found the very nice slides/notes by @henryyuen.bsky.social, e.g., these on the CHSH game: henryyuen.net/fall2022/lec....

This conversation is the teaching version of a longstanding debate in TCS: is theory worthwhile per se, or should it always be motivated by applications? In the mid-90s, there was a famous debate about this between two pairs of TCS luminaries: blog.computationalcomplexity.org/2016/06/karp.... 1/

The University of Michigan theory group is amazing, and has one the largest and best collections of junior theory faculty in the world!

I wanted to share some things I think are amazing and cool. Each like -> one theorem (or definition or phenomenon or example or...). #MathSky

A cool new lattice visualization tool from my colleague Kate Stange: crypto.katestange.net/lattice-demo/. She also has a bunch of other cool crypto/math demos on the same site.

I previously posted on Twitter (x.com/huckbennett/...) about new work with Sasha Golovnev and Noah Stephens-Davidowitz "Difficulties Constructing Lattices with Exponential Kissing Number from Codes" (arxiv.org/abs/2410.16660). 1/