Huck Bennett

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

[Huck Bennett @huckbennett]

Like a lot of people I was elated that László Lovász and Avi Wigderson won the Abel Prize on Wednesday (https://t.co/Qi0LjwBsck). 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/

[Huck Bennett @huckbennett]

@AlanPaulFern1 Thanks Alan. I used to really like Twitter, but have major issues with it now. Fortunately, most of TCS is on BlueSky (often exclusively), although ML might be different. I'd suggest checking it out if you haven't yet: it's a Twitter knockoff in a good way.

[Huck Bennett @huckbennett]

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]

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.

[Huck Bennett @huckbennett]

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

[Huck Bennett @huckbennett]

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," https://t.co/jqiCj7LVES. Check out Surendra's talk if you can! 1/

[Huck Bennett @huckbennett]

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/

[Huck Bennett @huckbennett]

@overleaf I've had a project open for ~45 minutes and have already gotten >5 pop-up ads for the AI writing service you're trying to force on us. Please stop! This is quite disruptive. This is with a premium account too.

[Huck Bennett @huckbennett]

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.

[Huck Bennett @huckbennett]

A cool new lattice visualization tool from my colleague Kate Stange: https://t.co/JJeAQyaH4B. She also has a bunch of other cool crypto/math demos on the same site.

[Huck Bennett @huckbennett]

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

[Huck Bennett @huckbennett]

This morning, we saw a new preprint from the same author (https://t.co/1kC8rSZRDU) again claiming a construction of exponential kissing number lattices. We sent him the following email. 1/

[Huck Bennett @huckbennett]

New work with Sasha Golovnev and @noahsd: "Difficulties Constructing Lattices with Exponential Kissing Number from Codes" (https://t.co/gfxDyJtmUY). 1/

[Huck Bennett @huckbennett]

Ilya's blog post about our hike last weekend (featuring some of my photos)!

[Huck Bennett @huckbennett]

CU and Boulder looking rather photogenic after the first snow of the year.

[Huck Bennett @huckbennett]

@jackervatorlin @NoahSD Thanks Yanlin! Speaking of awesome stuff, I saw your thesis recently. Congratulations!

[Huck Bennett @huckbennett]

New work with Sasha Golovnev and @noahsd: "Difficulties Constructing Lattices with Exponential Kissing Number from Codes" (https://t.co/gfxDyJtmUY). 1/

[Huck Bennett @huckbennett]

@mahdi_tcs @NoahSD Agreed! Maybe there's a way to use structural properties of specific codes. It's a great question.

[Huck Bennett @huckbennett]

@mahdi_tcs @NoahSD Yeah, although our work gives barriers, so now the main question remains more open than ever :-). The issues with the papers were not related to the (AG) codes used, but rather the means of constructing lattices from codes.

[Huck Bennett @huckbennett]

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

[Huck Bennett @huckbennett]

This updated situation affects at least two papers on lattice complexity: https://t.co/sVc2hnZUCU and https://t.co/eKlDvlEAp5. The complexity papers are correct, but have hardness results that are now conditional. 4/