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/
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.
I don't often weigh in on AI issues, but had some thoughts based on an interesting recent post by @ilyaraz.bsky.social on LinkedIn. Ilya posted recent comments by two top algorithms researchers noting how well LLMs had done on their algorithms exams. 1/
March 19, 2025 at 6:36 AM
I don't often weigh in on AI issues, but had some thoughts based on an interesting recent post by @ilyaraz.bsky.social on LinkedIn. Ilya posted recent comments by two top algorithms researchers noting how well LLMs had done on their algorithms exams. 1/
Reposted by Huck Bennett
I am truly honored to be giving the 2025 William Reinhardt Memorial Lecture next week at the University of Colorado Boulder.
"How we might have taken the Continuum Hypothesis
as a fundamental axiom, necessary for mathematics"
www.colorado.edu/math/2025/03...
"How we might have taken the Continuum Hypothesis
as a fundamental axiom, necessary for mathematics"
www.colorado.edu/math/2025/03...
2025 William Reinhardt Memorial Lecture
The William Reinhardt Memorial Lecture in the Philosophy of Mathematics was founded to commemorate the life of William Reinhardt, Professor of Mathematics at
www.colorado.edu
March 6, 2025 at 6:56 PM
I am truly honored to be giving the 2025 William Reinhardt Memorial Lecture next week at the University of Colorado Boulder.
"How we might have taken the Continuum Hypothesis
as a fundamental axiom, necessary for mathematics"
www.colorado.edu/math/2025/03...
"How we might have taken the Continuum Hypothesis
as a fundamental axiom, necessary for mathematics"
www.colorado.edu/math/2025/03...
It was my pleasure to join a jubilant and well-attended rally against the current administration's assault on science in Boulder today. Besides the University of Colorado, Boulder and the surrounding area are home to many national labs, including NIST, NOAA, NCAR, and NREL. 1/2
March 4, 2025 at 2:46 AM
It was my pleasure to join a jubilant and well-attended rally against the current administration's assault on science in Boulder today. Besides the University of Colorado, Boulder and the surrounding area are home to many national labs, including NIST, NOAA, NCAR, and NREL. 1/2
Periodic reminder for theorists who like to run: join 114 friends in the Running in Theory club on Strava (www.strava.com/clubs/runnin...)!
"A club for runners of all levels working or interested in theoretical computer science. Come decrease your running times (asymptotic and otherwise) in style!"
"A club for runners of all levels working or interested in theoretical computer science. Come decrease your running times (asymptotic and otherwise) in style!"
Boulder, Colorado | Running in Theory
A club for runners of all levels working or interested in theoretical computer science.
Come decrease your running times (asymptotic and otherwise) in style!
If you're in an adjacent field (math, op...
www.strava.com
March 2, 2025 at 2:34 AM
Periodic reminder for theorists who like to run: join 114 friends in the Running in Theory club on Strava (www.strava.com/clubs/runnin...)!
"A club for runners of all levels working or interested in theoretical computer science. Come decrease your running times (asymptotic and otherwise) in style!"
"A club for runners of all levels working or interested in theoretical computer science. Come decrease your running times (asymptotic and otherwise) in style!"
New work with Mitchell Black, Amir Nayyeri, and Evelyn Warton, in which we study what can be learned about a hidden graph using few effective resistance queries: arxiv.org/abs/2502.18350. Evelyn (Amir and my co-advised student) recently did her Ph.D. thesis proposal on the subject of this paper!
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
February 26, 2025 at 2:59 AM
New work with Mitchell Black, Amir Nayyeri, and Evelyn Warton, in which we study what can be learned about a hidden graph using few effective resistance queries: arxiv.org/abs/2502.18350. Evelyn (Amir and my co-advised student) recently did her Ph.D. thesis proposal on the subject of this paper!
This is terrible news, and part of the ongoing assault on science in the U.S. by the new administration.
To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/
To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/
February 21, 2025 at 4:50 AM
This is terrible news, and part of the ongoing assault on science in the U.S. by the new administration.
To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/
To honor Tracy Kimbrel and his service to the NSF's AF division, here's a short thread about a beautiful algorithm of his, joint with Rakesh Sinha (www.sciencedirect.com/science/arti...). 1/