Huck Bennett

Holy crap! I find this way, WAY more surprising than the 3-SUM and APSP results, which I already found extremely surprising. "Just" SETH would have already been gigantic if somewhat less surprising. A few comments:

3. As my student Ashley (ashley-alf.github.io) pointed out to me, this does *not* break OV! Ryan's reduction (people.csail.mit.edu/rrw/2-csp-fi...) is from k-SAT to OV, not the other way around! So, fine-grained complexity is currently in the following situation.

Holy crap! I find this way, WAY more surprising than the 3-SUM and APSP results, which I already found extremely surprising. "Just" SETH would have already been gigantic if somewhat less surprising. A few comments:

2. This is a bit subjective, but I'd argue that in each case except for MM, AI has "barely" broken the barrier. In this case, AI shaved logs in the exponent.

Holy crap! I find this way, WAY more surprising than the 3-SUM and APSP results, which I already found extremely surprising. "Just" SETH would have already been gigantic if somewhat less surprising. A few comments:

WOW!!!

The timing of this is very funny to me too. I'm teaching both undergrad and grad algorithms this semester, and, as I have done many times before, I offer an automatic A in the class to anyone who improves on certain algorithms that we see. Of course, I don't give out automatic As so easily...

I really appreciate the report from the Simons Institute's AI + TCS working group (simons.berkeley.edu/ai-tcs-worki...), even though I don't agree with all of its recommendations. The central thing that I'm wary about is 3.1/3a as a blanket policy. 1/2

I'm in Ottawa, ON, Canada to give a couple of talks at the Selected Areas in Cryptography (SAC) summer school on Monday: sacworkshop.org/SAC26/schedu.... The first is about lattice basics, LWE, and LWE optimizations. The second is on the lattice-isomorphism problem and related cryptography.

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

A particular shout-out to the awesome junior researchers on these papers, who include all four of my Ph.D. students---Evelyn (www.evelynw.xyz), Peter (kirotas.github.io), Bryant, and Matthew (www.matthewfoxphysics.com). These are Peter and Bryant's first papers! 13/

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

Paper #4: "The Code Distortion Problem," arxiv.org/abs/2607.26261, at APPROX 26, with Matthew Fox and Bryant Morrell. We generalize Linear Code Equivalence (LCE; an important problem in crypto) to ask what the minimum *distortion* D of a linear map between two codes is. 11/

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

In particular, it is (and remains) a beautiful open question to show that CRP in the l_2 norm is Pi_2-hard to approximate to within a small constant. We made some progress in this direction by showing NP-hardness for CRP in explicit finite l_p norms for the first time. 9/

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

As a bonus, in an appendix we give a careful write-up of a folklore very flexible/good compressed sensing scheme (works over any ring, has nearly optimal parameters and running time, measurement matrix is binary). See my previous comment on this too: bsky.app/profile/huck.... 7/

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

Paper #2: "Output-Sparse Matrix Multiplication Using Compressed Sensing," arxiv.org/abs/2508.10250, at RANDOM 26, with Karthik Gajulapalli, Alexander Golovnev, and Evelyn Warton. We give the fastest known deterministic algorithm for output-sparse MM (i.e., MM where the product matrix is sparse). 5/

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

Works from a couple of years ago (eprint.iacr.org/2021/1332, eprint.iacr.org/2021/1548) showed how to get basic crypto (KEMs/PKE, signatures) from the assumption that a variant of LIP is hard. We show how to construct more advanced primitives from a similar assumption. 3/

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

Yes, the result itself is very interesting (more on this below). From a skim, I agree with Noah that the paper is not well-written. Am I happy to see LLMs invade TCS? No, it's terrible. Is this the most impactful LLM result about lattices this week? Unclear. 1/

Alas, not all approx factors γ are the same: γ-CVP for γ = n^{1/2} is in coNP, and so it likely isn't NP-hard. Still, the new result with γ = n^{1/200} comes close to the n^{1/2} barrier for the first time. Previously no poly hardness was known, and now it's a matter of pinning down the exponent. 4/

Yes, the result itself is very interesting (more on this below). From a skim, I agree with Noah that the paper is not well-written. Am I happy to see LLMs invade TCS? No, it's terrible. Is this the most impactful LLM result about lattices this week? Unclear. 1/

Alas, not all approx factors γ are the same: γ-CVP for γ = n^{1/2} is in coNP, and so it likely isn't NP-hard. Still, the new result with γ = n^{1/200} comes close to the n^{1/2} barrier for the first time. Previously no poly hardness was known, and now it's a matter of pinning down the exponent. 4/

Yes, the result itself is very interesting (more on this below). From a skim, I agree with Noah that the paper is not well-written. Am I happy to see LLMs invade TCS? No, it's terrible. Is this the most impactful LLM result about lattices this week? Unclear. 1/

First, why is this interesting? Here's an image from eccc.weizmann.ac.il/report/2022/... about the related problem SVP with varying approx factors. The middle regime says that if γ-SVP is hard for a large enough polynomial gamma (say, γ~=n^2) then lattice-based cryptography is *provably* secure. 2/