Huck Bennett
@huckbennett.bsky.social
Faculty at the University of Colorado. Interested in theoretical computer science, and especially lattices. Also: mountains, running, music.
https://home.cs.colorado.edu/~hbennett/
https://home.cs.colorado.edu/~hbennett/
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/
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/
home.cs.colorado.edu
January 23, 2026 at 4:36 PM
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/
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/
Reposted by Huck Bennett
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.
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.
A simple and modest proposal for improving asymptotic notation | Solipsist's Log
www.solipsistslog.com
January 7, 2026 at 6:32 PM
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.
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.
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
January 1, 2026 at 8:15 PM
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
Reposted by Huck Bennett
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.
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.
Exclusive: The Trump administration is moving to dismantle the National Center for Atmospheric Research in Colorado, according to a senior White House official, taking aim at one of the world's leading climate research labs.
Trump moves to dismantle major US climate research center in Colorado
The Trump administration is breaking up the National Center for Atmospheric Research, taking aim at one of the world's leading climate research labs.
bit.ly
December 17, 2025 at 3:23 AM
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.
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.
Reposted by Huck Bennett
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!
I'm super excited about this paper!
ECCC - TR25-210
eccc.weizmann.ac.il
December 9, 2025 at 12:41 AM
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!
I'm super excited about this paper!
November 22, 2025 at 7:25 AM
Venkat is the best! He'll be an awesome director at Simons.
Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky
October 31, 2025 at 1:01 AM
Venkat is the best! He'll be an awesome director at Simons.
Reposted by Huck Bennett
October 22, 2025 at 6:56 PM
"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/
1/2 Should have paid attention to matrices during linear algebra classes! In 2026, AI will use ~1% of global electricity, of which ~45-90% will be for matrix multiplications, said Oded Schwartz of Hebrew University of Jerusalem at the Simons Institute. simons.berkeley.edu/talks/oded-s...
October 21, 2025 at 5:32 PM
"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/
Reposted by Huck Bennett
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
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
October 17, 2025 at 5:16 PM
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
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
Reposted by Huck Bennett
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...
#🧮
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...
#🧮
MathJobs from the the American Mathematical Society
Mathjobs is an automated job application system sponsored by the AMS.
www.mathjobs.org
October 12, 2025 at 12:44 AM
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...
#🧮
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.
October 6, 2025 at 4:28 AM
Sending good vibes to Portland.
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!
AMA about how awesome Boulder and Colorado are!
Tenure-Track Faculty in Quantum Computing
jobs.colorado.edu
October 2, 2025 at 2:40 PM
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!
AMA about how awesome Boulder and Colorado are!
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
September 21, 2025 at 6:35 PM
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*?
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Evelyn Warton
Output-Sparse Matrix Multiplication Using Compressed Sensing
https://arxiv.org/abs/2508.10250
Output-Sparse Matrix Multiplication Using Compressed Sensing
https://arxiv.org/abs/2508.10250
August 15, 2025 at 7:04 PM
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*?
Ah, yes, the Baker-Gill-Solovay Theorem is my favorite old timey TV program. What an age of internet search we live in.
July 29, 2025 at 4:05 PM
Ah, yes, the Baker-Gill-Solovay Theorem is my favorite old timey TV program. What an age of internet search we live in.
Reposted by Huck Bennett
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
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
July 14, 2025 at 5:07 PM
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
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
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"!
June 22, 2025 at 5:43 PM
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?!" 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
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
June 17, 2025 at 9:22 PM
"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
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
Great choice!
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
sigact.org/prizes/servi... #TCSSky
2025 ACM-SIGACT Distinguished Service Award
sigact.org
May 31, 2025 at 3:35 AM
Great choice!
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
May 17, 2025 at 5:54 AM
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.
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.)
April 29, 2025 at 6:54 PM
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
The Enchantments, WA // Grand Canyon, AZ
April 22, 2025 at 5:19 PM
Happy Earth Day 2025!
The Enchantments, WA // Grand Canyon, AZ
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....
matthewfoxphysics.com
April 16, 2025 at 4:24 PM
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.
April 1, 2025 at 4:31 PM
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.