This is a brilliant idea!

DIMACS is hosting not one, not two, but three workshops on fine-grained complexity next month, from July 20–31! Registration is free but required. To register, click each relevant workshop page on the DIMACS events page: dimacs.rutgers.edu/events/list Hope to see many of you there!

Big update: the EC Zoo is now a handbook. It spans codes, sphere packings, lattices, designs, groups, and phases of matter. Extensively checked, but not perfect—feedback very welcome: arxiv.org/abs/2606.11484

Huge congratulations to Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart on being awarded the Gödel prize for their breakthrough work on algorithmic robustness! www.sigact.org/prizes/g%C3%...

I kept thinking about Boaz's blog post, and ended up responding with a fairly long comment. My response touched on a few things I wanted to say anyway, and so I decided to make it a blog post of my own: hdbennett.wordpress.com/2026/05/31/m.... (It's my second blog post ever, and first in >10 years.)

I'm saddened that thoughtful, smart people aren't able to leave it at "I think AI is good and I use it." They feel the need to gush, "OMG! If YOU aren't token maxxing every minute of every day then YOU are falling behind! Use it for everything or else!" It's like a cult.

You may find the comments by Melanie Matchett Wood on the discovery of a counter example to Erdős’ Unit Distance Conjecture as interesting as I did 👇🏼(see previous post for a link)

The plane got all of the attention today, but what about higher dimensions? Here's a nice problem: Give an explicit configuration of n points in R^4 such that Theta(n^2) pairs of points are at unit distance. (Note that n^2 is as large as possible.)

What I get as the top hit for "CS Theory" on Google search. Turing Machines just look so much shinier with that Matte Finish.

(Sisyphus teaches at CU Boulder.)

One great thing about CU Boulder is that it has a Grammy-award-winning string quartet in residence: the Takács Quartet. Last night, I got to see what was founding cellist András Fejér's last performance with the group after 51 years. He had been the only remaining founding member. 1/2

One of my favorite New Yorker covers (cf. www.nytimes.com/2026/04/23/t... and related stories).

Happy Earth Day 2026! (Oregon/Colorado)

This is very nice recognition of Hal Gabow! Hal spent his whole career as faculty at CU Boulder, and his legacy looms large for us. (Hal retired in 2008, and I unfortunately have never gotten a chance to meet him.)

Former NSF theory program director Peter Brass guest posts on the state of the foundation.

I was lucky to get to run the Corvallis Half Marathon over the weekend in Oregon! A couple of weeks ago, I was part of a theory Ph.D. thesis defense at U. Colorado where I enjoyed realizing that all of the other faculty on the committee were also runners (and that 3 of 4 are faster than I am).

Online CS Theory Seminar this Fri 2026-04-10! We're excited to have Martin Kreuzer (Uni. Passau) presenting "From Code Equivalence to Polynomial Isomorphism" www.digital.uni-passau.de/en/profiles/... www.colorado.edu/cs-theory/th... #MathSky #TCSSky #complexity #AlgebraicGeometry

Congratulations to fantastic @bouldertheory.bsky.social undergraduate @adithyacolorado.bsky.social! I've had the pleasure of getting to work with Adithya during his time at CU, and am very excited to hear about his work going forward.

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/