@huckbennett profile picture
Huck Bennett @huckbennett

Faculty at the University of Colorado. Interested in theoretical computer science, and especially lattices. Also: mountains, running, music.

Joined January 2015
  • Tweets 908
  • Following 542
  • Followers 631
56 Photos and videos
Pinned Tweet
Huck Bennett@huckbennett
20 Mar 2021
Like a lot of people I was elated that László Lovász and Avi Wigderson won the Abel Prize on Wednesday (abelprize.no/c76389/seksjon/…). So, to honor (or maybe horrify) Lovász, I'm going to Tweet what will likely be a long thread about one of his top contributions, the LLL algorithm. 1/

4
51
143
I've now fully migrated to Bluesky, and encourage everyone else to join there as well. This account is inactive for now, and I'm not monitoring it. (I may still rarely post things, and may start using Twitter again if things dramatically change.)
Huck Bennett@huckbennett
16 Nov 2024
Like a lot of people, I recently created a Bluesky account (@huckbennett.bsky.social). For now I'll keep using Twitter too (to the extent I use either), but I'll be gleeful if there's enough momentum towards Bluesky that I can stop using Twitter.
2
2
213
Work with Surendra Ghentiyala and Noah Stephens-Davidowitz to be presented at ITCS '25 in a few days: "The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions," eccc.weizmann.ac.il/report/2…. Check out Surendra's talk if you can! 1/

1
1
307
more replies
Specifically, the canonical problem for (A, B)-PMPP^L is defined as follows. Given positive integers A, B, L, and a circuit C: [A] -> [B], find L domain elements that all map to the same range element. This problem is total if L >= ceil(A/B) by the pigeonhole principle. 4/
1
203
We show both containment and hardness results for coding problems with respect to PMPP classes, including those corresponding to several standard coding bounds. We also show analogous results for lattice problems, and study PMPP classes themselves. 5/5
179
Like a lot of people, I recently created a Bluesky account (@huckbennett.bsky.social). For now I'll keep using Twitter too (to the extent I use either), but I'll be gleeful if there's enough momentum towards Bluesky that I can stop using Twitter.
4
743
A cool new lattice visualization tool from my colleague Kate Stange: crypto.katestange.net/lattic…. She also has a bunch of other cool crypto/math demos on the same site.
2
11
966
This morning, we saw a new preprint from the same author (arxiv.org/abs/2411.07371v1) again claiming a construction of exponential kissing number lattices. We sent him the following email. 1/
Huck Bennett@huckbennett
23 Oct 2024
New work with Sasha Golovnev and @noahsd: "Difficulties Constructing Lattices with Exponential Kissing Number from Codes" (arxiv.org/abs/2410.16660). 1/
1
1
5
2,296
Speaking only for myself: it's not scientifically productive to attempt quick fixes like this without real new ideas, especially when there was a major issue with the original approach. 2/2
346
Ilya's blog post about our hike last weekend (featuring some of my photos)!
This tweet is unavailable
3
445
CU and Boulder looking rather photogenic after the first snow of the year.
15
568
New work with Sasha Golovnev and @noahsd: "Difficulties Constructing Lattices with Exponential Kissing Number from Codes" (arxiv.org/abs/2410.16660). 1/

Difficulties Constructing Lattices with Exponential Kissing Number...

In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-weight non-zero...

arxiv.org
4
4
21
5,604
more replies
This updated situation affects at least two papers on lattice complexity: arxiv.org/abs/2109.04025 and arxiv.org/abs/1712.00942. The complexity papers are correct, but have hardness results that are now conditional. 4/

Improved Hardness of BDD and SVP Under Gap-(S)ETH

We show improved fine-grained hardness of two key lattice problems in the $\ell_p$ norm: Bounded Distance Decoding to within an $α$ factor of the minimum distance ($\mathrm{BDD}_{p, α}$)...

arxiv.org
1
401
The author of the retracted papers, Serge Vlăduţ, was tremendously helpful, communicative, and ethical when responding to our questions and eventual bug report. This is not a fun situation to be in, but he handled everything very well. 5/5
342
Job ad from my CU colleague Stephen Becker. The first position is theory-adjacent! The Department of Applied Mathematics at the University of Colorado at Boulder invites applications for two tenure track faculty positions at the Assistant Professor level to begin August 2025. 1/
2
3
5
1,774
One position is in mathematical data science (jobs.colorado.edu/jobs/JobDe…), while the other position is in mathematical climate science (jobs.colorado.edu/jobs/JobDe…). 2/2
1
1
451
Huck Bennett retweeted
Mike Rosulek@GarbledCircus
18 Oct 2024
Big announcement: The next edition of The Joy of Cryptography will be published by @mitpress!
6
26
110
8,087
Load more