Faculty at the University of Colorado. Interested in theoretical computer science, and especially lattices. Also: mountains, running, music.
Joined January 2015
- Tweets930
- Following564
- Followers699
- Likes4.8K
Pinned Tweet
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/
🚨 I have a postdoc position open for Fall 2027: jobs.colorado.edu/jobs/JobDe…. Please apply by December 15th.
I will give priority to those working on topics related to my work, including lattices, codes, fine-grained complexity (ha!), and algebraic and geometric algorithms. 1/
But, the position is open to those working in algorithms and complexity more broadly as well as those working in aspects of cryptography related to the topics above.
The position is guaranteed for one year, but with the hope of extending to two. 2/
You will be part of CU Boulder theory (colorado.edu/cs-theory/), a large and welcoming group that also collaborates with other groups and departments. And, this is your regular reminder that Boulder is an amazing place to live, especially for those who enjoy the outdoors. 3/3
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: 1/
Here's a direct link to OpenAI's PDF claiming a refutation of ETH. In particular, it's claimed that 3SAT on n variables is in about exp(n/(log n)^{1/2+o(1)}) time
github.com/openai/math/blob/…
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-c…) is from k-SAT to OV, not the other way around! So, fine-grained complexity is currently in the following situation. 5/
My colleague in CU's math department asked me to share the following job ad.
For more details on the position and information on how to apply, please visit
jobs.colorado.edu/jobs/JobDe…
For full consideration, please apply by November 11, 2026.
ALT A job ad for Colorado's math department.
University of Colorado CS is hiring in quantm this year, and quantum theory is explicity a focus area: jobs.colorado.edu/jobs/JobDe… !
I really appreciate the report from the Simons Institute's AI + TCS working group (simons.berkeley.edu/ai-tcs-w…), 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 decided to start using Twitter again in order to witness the hostile big-AI takeover of math and TCS. The "Why would you ruin your career?" wannabe mobsters post here.
Fortunately, I've also enjoyed reading many thoughtful takes by colleagues who aren't active on Bluesky.
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.)
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.
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/
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/