10 years ago today: my blog post on AlphaGo and Artificial Intelligence, which I wrote in grad school: hdbennett.wordpress.com/2016/03/18/a....

Emphasis on the attack not coming close to the security claimed by Dilitihium. Dilithium claims 123, 186, and 265 bits of security for classical unforgeability; the attack gets running times of 202, 289, and 400 (for L2, L3, and L5, respectively). (Ref: pq-crystals.org/dilithium/da..., Tbl 1.)

This New Yorker article about Claude (and AI in general) was excellent: www.newyorker.com/magazine/202.... In a world of 200-character hot takes, TNY's nuanced long-form journalism stands out even more. It's also funny: "investors ... including legendary League of Legends player Sam-Bankman-Fried."

Students without technical knowledge will have no ability to recognize if AI outputs something that's sub-optimal or just plain wrong, let alone have any idea about how to produce the right thing. I also think that anthropomorphizing AI as having "read" books is rather misleading.

1/3 Fine-Grained Complexity Fest at DIMACS this July! Three back-to-back workshops on Algebraic Techniques, String Algorithms, and Graph Algorithms in fine-grained complexity, with a terrific speaker lineup. Organized by @jalman.bsky.social , Elazar Goldenberg, and @eigx.bsky.social.

The University of Colorado made a major, expensive "LLMification of higher ed" deal with OpenAI based on the recommendation of a committee (www.cu.edu/gen-ai#tabs-2) with no CS or STEM faculty, no faculty from CU Boulder, and no one with clear expertise in any aspect of AI or AI-based pedagogy.

I wrote a short expository note about a beautiful result of Carmosino, Gao, Impagliazzo, Mihajlin, Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/

I wrote up a little blog post proposing a slightly different way to write asymptotic notation. www.solipsistslog.com/a-simple-and... In short, I think asymptotic notation should usually be written with an INequality. E.g., f(n) <= O(n^2), f(n) < o(log n), f(n) > 2^{-o(n)}, f(n) >= n^{-O(1)}, etc.

To kick off 2026, here's a quick thread on a few mountain ascents from 2025, starting at home in Boulder, Colorado with Mount Sanitas (6,798') at night. 1/4

A deeply dangerous — and blatantly retaliatory action against Colorado — by the Trump administration. NCAR is one of the most renowned scientific facilities in the WORLD — where scientists perform cutting-edge research everyday. We will fight this reckless directive with every legal tool we have.

New paper with Surendra Ghentiyala (my wonderful PhD student) and Zeyong Li (a PhD student at NUS) eccc.weizmann.ac.il/report/2025/... . I'm super excited about this paper!

Venkat is the best! He'll be an awesome director at Simons.

Join us next Tuesday! simons.berkeley.edu/events/matri...

"AI will use ~1% of global electricity, of which ~45-90% will be for matrix multiplications" is crazy! Even for those of us who are on the Luddite side of the AI spectrum and even if the numbers are off by an order of magnitude, this heavily motivates studying MM. 1/

Hybrid CS Theory Seminar next Fri 2025-10-24! We're excited to have Alexander Golovnev (Georgetown University), presenting "Online Orthogonal Vectors Revisited" golovnev.org www.colorado.edu/cs-theory/th... #MathSky #Algorithms #Complexity #TCSSky

Tenure-track opening @ U. Colorado Boulder Dept. of Math! Esp. (but not only) looking for: algebraic geometry homotopy theory foundations functional analysis number theory interdisciplinary collab. b/w math & computer science or the math of quantum physics www.mathjobs.org/jobs/list/27... #🧮

Sending good vibes to Portland.

CU computer science is doing a search for a tenure-track position in quantum computing this year: jobs.colorado.edu/jobs/JobDeta.... The scope of the search in particular includes quantum CS theory! AMA about how awesome Boulder and Colorado are!

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