Huck Bennett

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/

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

@huckbennett I guess you may not see this, but I've heard a number of researchers complaining about twitter recently. The usual complaint is about seeing content they don't want to see. I find twitter to be extremely useful for monitoring new research and don't have those problems.

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

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

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/

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/2024/01…. Check out Surendra's talk if you can! 1/

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

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.

A cool new lattice visualization tool from my colleague Kate Stange: crypto.katestange.net/lattice-demo/. She also has a bunch of other cool crypto/math demos on the same site.

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

This morning, we saw a new preprint from the same author (arxiv.org/abs/2411.07371…) again claiming a construction of exponential kissing number lattices. We sent him the following email. 1/

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

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

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

@huckbennett @NoahSD That's super awesome!

New work with Sasha Golovnev and @noahsd: "Difficulties Constructing Lattices with Exponential Kissing Number from Codes" (arxiv.org/abs/2410.16660). 1/

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

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

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

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/