Huck Bennett

10/10 meme choice.

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.

From the combination of their nontrivial algorithm for co-3-SUM, they conclude that, assuming NSETH, there is no fine-grained reduction from k-SAT to 3-SUM (unlike, say, Orthogonal Vectors, for which such a reduction is known). 5/5

Their paper, which is the epitome of a good ITCS paper, also introduced the nondeterministic SETH (NSETH) assumption, which roughly asserts that there is no non-trivial algorithm for the co-k-SAT for large k (i.e., that certifying that formulas are UNSAT takes as long as solving the problem). 4/

But, it is not at all clear how to certify that there are *no* triples that sum to 0! Carmosino et al. give such an algorithm by noting that it's efficient to *count* 3-SUM solutions mod a small prime p using FFT, and by providing all "false positives mod p" as a witness. 3/

Recall that 3-SUM is the decision problem where the input is an array A = [a_1, ..., a_n] of integers and the goal is to decide whether there exist indices i, j, k s.t. a_i + a_j + a_k = 0. It is easy to certify YES instances very efficiently: the witness is just the indices of a 3-SUM triple. 2/

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.

Otis Peak (12,486') and Hallett Peak (12,720') in Rocky Mountain National Park, Colorado. Spot the ptarmigan! 4/4

Mount Whitney (14,505'), the highest peak in California and the entire continental U.S. Roughly 6,300 feet of elevation gain and 20.75 miles. Done with @ilyaraz.bsky.social, who provided much-needed energy at the end. 3/4

Mount Adams (12,281'), the second-highest peak in Washington State and one of its five volcanoes. Roughly 6,800 feet of elevation gain and 12.25 miles. Yes, TSA allows ice axes in checked baggage. 2/4

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!

That's awful if true. I was actually just commenting on knowing a bunch of great people who went to Purdue. They include an awesome colleague who's Venezuelan and did her Ph.D. there.

www.youtube.com/watch?v=EZYQ...

There's www.cfail.org for cryptography.

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

Join us next Tuesday!

simons.berkeley.edu/events/matri...

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!

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/

Tensors and their uses, especially for matrix multiplication (Part 1) YouTube video by Simons Institute for the Theory of Computing

... 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/

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/

"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/

A grid of 0s and 1s with the 1s highlighted blue One row is circled in red Next to it, a vector q = 0100

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

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.

MathJobs from the the American Mathematical Society Mathjobs is an automated job application system sponsored by the AMS.

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.