Huck Bennett

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.

Make America go to bed at a reasonable hour again?

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!

Correction of link to Schönhage's paper: dl.acm.org/doi/10.1137/.... (The result is Eq. 15.12 in the linked Algebraic Complexity Theory book.)

Algebraic Complexity Theory The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century...

Specifically, the MM tensors <4, 1, 4> and <1, 3^2, 1> corresponds to outer and inner products and have border rank 16 and 9, respectively. But, <4, 1, 4> \oplus <1, 3^2, 1> has border rank 17 << 16 + 9 = 25 ! This result is due to Schönhage '81: dl.acm.org/doi/10.1137/.... 2/2

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*?

Awesome community service on your part :-).

A Google search for "baker-gill-solovay theorem" results in an information box labeled with "TV program" and showing a black-and-white frame presumably from the show.

Ah, yes, the Baker-Gill-Solovay Theorem is my favorite old timey TV program. What an age of internet search we live in.

Fine-Grained Reductions Network of many problems, together with arrows between them representing fine-grained reductions, as well as the lower bounds on those problems assuming the (Strong) Exponential Time Hypothesis. Example problems include 3/2-approximate Diameter, SAT, Dominating Set, Edit Distance, All Pairs Shortest Paths, 3-SUM, Collinearity, Hitting Set, ...

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

"More verys can be provided by the author upon request" is a very nice touch!

I'm curious what you have in mind for "AI for TCS" past "I got my LLM to (help) prove this theorem for me," which seems mostly beyond the current capability of LLMs.

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?! It's just a reference, not the article itself! And, (1) articles can of course be open access, and (2) non-open-access articles often have open-access preprint versions available.

Including articles in an uploaded .bib file also leads to an error with no explanation. 2/2

"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

Nice! Congrats to her advisor too!

Great choice!

Peter Lax, Pre-eminent Cold War Mathematician, Dies at 99

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.

I'm imagining that you have an especially low chance of being mugged today.

Actually, I encountered the fact in the OP through lattice complexity too. It comes up in the proof of Theorem 1.1 in arxiv.org/pdf/1806.04087.

I'd forgotten that NP-hardness of unique SVP was your result! It's very nice! I actually mention your result and the (still) open question of proving any NP-hardness of approximation for uSVP in my survey on the complexity of SVP: eccc.weizmann.ac.il/report/2022/.... See Sec. 4.2 and Open Prob. 4.6.

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.

Thanks for sharing! That's indeed a good reduction, but now the "in NP" part is garbage :-). I originally just asked about NP-hardness (I think the exact prompt was "Prove that the Closest Vector Problem is NP-hard.")

I also tried this on Deepseek, which I hadn't used before. It's weird (it spews stuff stream-of-consciousness until you hit "stop") and also didn't give a right answer, but some of what it said was fairly close to being right and unlike ChatGPT it didn't obviously assert anything false. 5/5