Lightnews — Scholar-powered news

Huck Bennett @huckbennett.bsky.social · 3d

Sending good vibes to Portland.

1

Huck Bennett @huckbennett.bsky.social · 6d

Make America go to bed at a reasonable hour again?

1 3

Huck Bennett @huckbennett.bsky.social · 6d

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!

Tenure-Track Faculty in Quantum Computing

jobs.colorado.edu

8 15

Huck Bennett @huckbennett.bsky.social · 17d

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

Partial and Total Matrix Multiplication | SIAM Journal on Computing

In 1979 considerable progress was made in estimating the complexity of matrix multiplication. Here the new techniques and recent results are presented, based upon the notion of approximate rank and th...

dl.acm.org

1

Huck Bennett @huckbennett.bsky.social · 17d

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

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

link.springer.com

1 1

Huck Bennett @huckbennett.bsky.social · 17d

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

Partial and Total Matrix Multiplication | SIAM Journal on Computing

In 1979 considerable progress was made in estimating the complexity of matrix multiplication. Here the new techniques and recent results are presented, based upon the notion of approximate rank and th...

dl.acm.org

1 1 8

Huck Bennett @huckbennett.bsky.social · Aug 15

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

arxiv cs.DS @arxiv-cs-ds.bsky.social · Aug 15

Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Evelyn Warton
Output-Sparse Matrix Multiplication Using Compressed Sensing
https://arxiv.org/abs/2508.10250

8

Huck Bennett @huckbennett.bsky.social · Aug 10

Awesome community service on your part :-).

1

Huck Bennett @huckbennett.bsky.social · Jul 29

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

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.

1 7

Reposted by Huck Bennett

CU Boulder CS Theory @bouldertheory.bsky.social · Jul 14

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

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

2 6

Huck Bennett @huckbennett.bsky.social · Jul 4

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

1

Huck Bennett @huckbennett.bsky.social · Jun 26

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.

2 4

Huck Bennett @huckbennett.bsky.social · Jun 22

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

4

Huck Bennett @huckbennett.bsky.social · Jun 17

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

2

Huck Bennett @huckbennett.bsky.social · Jun 17

"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

1 2

Huck Bennett @huckbennett.bsky.social · Jun 6

Nice! Congrats to her advisor too!

1

Huck Bennett @huckbennett.bsky.social · May 31

Great choice!

Clément Canonne @ccanonne.github.io · May 31

Huge congratulations to Tracy Kimbrel, who received the 2025 ACM SIGACT Service Award 🏆 for his time, dedication, and advocacy as Program Director for the Algorithmic Foundations (AF) program at the NSF!
sigact.org/prizes/servi... #TCSSky

2025 ACM-SIGACT Distinguished Service Award

sigact.org

2

Huck Bennett @huckbennett.bsky.social · May 17

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.

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

www.nytimes.com

3

Huck Bennett @huckbennett.bsky.social · May 16

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

1 1

Huck Bennett @huckbennett.bsky.social · Apr 30

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.

arxiv.org

1

Huck Bennett @huckbennett.bsky.social · Apr 30

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.

ECCC - TR22-170

eccc.weizmann.ac.il

2

Huck Bennett @huckbennett.bsky.social · Apr 29

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

2 4

Huck Bennett @huckbennett.bsky.social · Apr 22

Happy Earth Day 2025!

The Enchantments, WA // Grand Canyon, AZ

1 8

Huck Bennett @huckbennett.bsky.social · Apr 16

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

matthewfoxphysics.com

7

Huck Bennett @huckbennett.bsky.social · Apr 1

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.

2 12