Congratulations to Venkat! We recently used the explicit expander construction from GUV (the CCC paper) to get a compressed sensing scheme, which is the key to our MM algorithms in arxiv.org/abs/2508.10250. (Thanks to @eigx.bsky.social for the pointer to GUV!)

Output-Sparse Matrix Multiplication Using Compressed Sensing

We give two algorithms for output-sparse matrix multiplication (OSMM), the problem of multiplying two $n \times n$ matrices $A, B$ when their product $AB$ is promised to have at most $O(n^δ)$ many non...

arxiv.org

Simons Institute for the Theory of Computing@simonsinstitute.bsky.social · 2d ago

Simons Institute Director Venkat Guruswami has been honored this summer with STOC and CCC 2026 Test of Time Awards for papers that transformed coding theory and pseudorandomness, and emerged from a common algebraic core. simons.berkeley.edu/news/guruswa...

Yes, the result itself is very interesting (more on this below). From a skim, I agree with Noah that the paper is not well-written. Am I happy to see LLMs invade TCS? No, it's terrible. Is this the most impactful LLM result about lattices this week? Unclear. 1/

Clément Canonne@ccanonne.github.io · 4d ago

(same thing for @huckbennett.bsky.social and @noahsd.bsky.social , regarding the CVP one... If you have the time and energy of course!)

I enjoyed reading that Yu Deng almost became a professional Go player. Go is a fantastic game, which I used to play quite a lot. Here's a picture of playing Go and chess simultaneously with my Go BFF John (www.chungenliu.com; now a full professor of sociology!) when he visited Boulder recently. 3/3

Congratulations to Shayan on winning the Abacus Medal, and to all of the Fields Medal winners! I always really enjoy reading about their work. I've used matroid basis sampling in my own work, and I think (?) I've remembered to mention the improvement to Christofides Algorithm when teaching it. 1/

Quanta Magazine@quantamagazine.org · 2w ago

Read all the profiles here: www.quantamagazine.org/series/field...

An upcoming talk by my student Evelyn about our joint work with Mitchell Black and Amir Nayyeri from ALT 2026 (arxiv.org/abs/2502.18350) and her follow-up work!

Graph Inference with Effective Resistance Queries

The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruction, verification, a...

arxiv.org

CU Boulder CS Theory@bouldertheory.bsky.social · last mo.

Hybrid CS Theory Seminar this Thurs 2026-07-02! Excited to have Evelyn Warton (Oregon State) presenting "Inferring Graph Structures from Resistance Distances" www.evelynw.xyz www.colorado.edu/cs-theory/th... #MathSky #TCSSky #algorithms #combinatorics

This is a brilliant idea!

Sariel Har-Peled@sarielhp.bsky.social · 2mo ago

I wouldn't worry - we can replace these students with LLMs...

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!

@karthikcs.bsky.social · 6mo ago

2/3 Workshops (dates + links): • Algebraic Techniques in FGC (July 20–22): dimacs.rutgers.edu/events/detai... • FGC of String Problems (July 23–25): dimacs.rutgers.edu/events/detai... • FGC of Graph Problems (July 27–31): dimacs.rutgers.edu/events/detai...

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

Handbook of Error-Correcting Codes

Barcode scans, clear phone calls, reliable data storage, satellite communication, and large-scale quantum computation are all made possible by error correction. We present a handbook version of The Er...

arxiv.org

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

My Response to Boaz Barak’s Blog Post

This is my response to Boaz Barak’s blog post from 5/30/2026, titled “AI is a Meteor. Don’t be a Dinosaur.” I also left it as a comment on his post (awaiting moderation as of when…

hdbennett.wordpress.com

Huck Bennett@huckbennett.bsky.social · 2mo ago

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.

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.

Clément Canonne@ccanonne.github.io · 2mo ago

This is the title of what is meant to be an inspiring post by Boaz Barak, one of the more thoughtful, smart people in that space (the post itself is thankfully more nuanced). I can't understand how one can think this'll go well. "We truly believe we're building a cataclysm machine. Try not to die!"

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

Anupam Gupta@anupamg.bsky.social · 4mo ago

The ACM Transactions on Algos now has the Harold N. Gabow Annual Best Paper Award, for research contributions with lasting significance in algos. Hal Gabow, an amazing algos researcher, was founding editor of TALG, and helped establish this award. Thanks Hal! (Submit yr best papers to TALG!) 1/n

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.

Adithya Bhaskara@adithyacolorado.bsky.social · 4mo ago

I’m thrilled to share that I’ll be starting my Ph. D. at MIT EECS in the fall. I’m excited to work on problems in computational social choice theory and mathematical democracy. I’d love to meet other researchers in TCS and EconCS in the greater-Boston area; please reach out!

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

AlphaGo and Artificial Intelligence

On Friday, March 11th the world’s best Go player, Lee Sedol, lost the third game in a row of a five game match to Google DeepMind’s AlphaGo program. Far from being just games, AlphaGo&#…

hdbennett.wordpress.com

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

Noah Stephens-Davidowitz@noahsd.bsky.social · 5mo ago

I don't think this is relevant cryptographically. The DEL25 result that they're comparing to is far from the state of the art. (DEL25 were mostly interested in a different parameter regime.) And the claimed running time of this new attack is way higher than the claimed security of Dilithium.

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

What Is Claude? Anthropic Doesn’t Know, Either

Researchers at the company are trying to understand their A.I. system’s mind—examining its neurons, running it through psychology experiments, and putting it on the therapy couch.

newyorker.com

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.

Maria Antoniak@mariaa.bsky.social · 6mo ago

This decision was made without consulting a single CU Boulder professor with AI expertise. And AFAIK there was one professor *total* involved. More info, such as it is, here: https://www.cu.edu/gen-ai Check the "Guiding Principles" section for entertainment.

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/