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."
That's fair. Yes, I think I'd still say "trained."
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.
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.
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...
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/
... 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/
