Hung Le

Hung Le

@hunglv.bsky.social

Umass Amherst

136 followers117 following42 posts

Hung Le reposted

Clément Canonne
@ccanonne.github.io

To start the day with something nice (?): for two arbitrary events A, B, of course we don't have Pr(A∩B) = Pr[A]Pr[B]. That would be silly! But... we always have it "approximately": |Pr(A∩B) - Pr[A]Pr[B]| ≤ 1/4

Hung Le
@hunglv.bsky.social

Reflecting on the reading, I saw a lot of familiar bits and pieces from papers that I read in the past. But clearly, there are two major ideas in this OpenAI proof: (1) the column model and (2) the chart associated with each point.

Hung Le
@hunglv.bsky.social

The column model is conceptually interesting: it unifies other ad hoc tricks I’ve seen under a single model. This model should be universally useful for many problems. The charts seem to be ad hoc to L1 embedding only.

Hung Le
@hunglv.bsky.social

The problem with big names praising "breakthroughs" by OpenAI is that it gives OpenAI a pass on mostly sloppy and sometimes incorrect proofs, treating them as "machine things" that we should accept as a "small price". Would love to see them read the proofs and then write their understandings.

Hung Le
@hunglv.bsky.social

(2/n) The proofs are straightforward, and nothing deep happens yet. I also spent about 3 hours reading section 3 of the manuscript. It is only 4 pages long, but full of gibberish. The central concept in this section is called a chart. Nothing in this section is formal.

Hung Le
@hunglv.bsky.social

(3/n) I have to interact with GPT Anstra just to understand what each paragraph means. So far, I get the impression that nothing deep happens in this section either. Perhaps great stuff will be in subsequent sections, so I am looking forward to that. It has been a lot of pain reading so far.

Hung Le
@hunglv.bsky.social

This is bad. If you do not want to read a paper to review it properly, don't accept the review request.

Clément Canonne@ccanonne.github.io

Getting an obviously AI-generated review for #SOSA2027 (the Symposium on Simplicity in Algorithms), a conference promoting insights and exposition, is so incredibly ironic it almost makes me forget I am fuming.

Hung Le
@hunglv.bsky.social

SODA 27 notifications are out. Interesting facts: 1. Submissions: 1181 papers. Last year, 809 submissions, a 46% up. 2. Acceptance: 287 (~24.3%). Last year, 243 acceptances (~30%) Personal facts: Only 4-4-4 papers got into SODA; all 3-3-4 papers rejected. Rebuttal does not change anything.

Hung Le reposted

Clément Canonne
@ccanonne.github.io

"The proof [...] was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT. We then prepared this manuscript for public release, with the intent of uploading it on the morning of Thursday, September 17, 2026" Shameless, and shameful. arxiv.org/abs/2609.207...

arxiv.orgThe Strong Secretary Conjecture is True for Linear MatroidsWe prove a $1/e$ guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is...

Hung Le reposted

William Umboh
@swumboh.bsky.social

Had a great time organizing (with Julian Mestre, R Ravi, and Mik Zlatin) a post #FOCS2025 2-day workshop on Trends in Approximation and Online Algorithms! Featuring an amazing lineup of speakers (from established experts to rising stars) + wiki edit-a-thon + gelato cart from Mapo 1/n

Hung Le reposted

FOCS 2026
@focs2026.bsky.social

📢 #FOCS2026 will be held in NewYork City, USA! Nov 8–11, 2026 at NYU (colocated with TCC) General Chair: Marshall Ball PC Chair: Sanjeev Khanna (Co-Chair: Sepehr Assadi)

Hung Le
@hunglv.bsky.social

I hate conference deadlines, but somehow, deadlines make magic happen. A week ago, we had a jumble of texts, but now we have what looks like a nice paper.

Hung Le
@hunglv.bsky.social

I agreed to review 6 SODA papers this year (not counting other reviews); an idiot is here. It's hard to say no; my past self struggled to find reviewers. People (non-PC members) accepting more than 6 reviews for a theory conference are definitely inspiring; 6 is my new record. What's your number?

Hung Le reposted

Lance Fortnow
@lance.fortnow.com

Tracy Kimbrel, former National Science Foundation program director extraordinaire, will receive the 2025 ACM SIGACT Distinguished Service Award. He spearheaded programs such as TRIPODS (foundations of data science) and AitF (Algorithms in the Field). 1/2

Hung Le
@hunglv.bsky.social

Jonathan Conroy and Arnold Filtser have recently solved the padded decomposition problem for minor-free graphs, one of my favorite open problems. Congratulations to both! Their paper here: arxiv.org/abs/2504.00278 My take: minorfree.github.io/PaddedSolved/

arxiv.orgHow to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free GraphsRoughly, a metric space has padding parameter $β$ if for every $Δ>0$, there is a stochastic decomposition of the metric points into clusters of diameter at most $Δ$ such that every ball of radius $γΔ$...

Hung Le reposted

Sophie Huiberts
@sophie.huiberts.me

I first got into smoothed analysis and linear programming during my master's. Now, 9 years later, we finally have matching upper and lower bounds. I spent a huge part of my life on this, and it feels weird that it's now finished.

arxiv.orgOptimal Smoothed Analysis of the Simplex MethodSmoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through w...

Hung Le reposted

𝖬𝖺𝗁𝖽𝗂 𝖢𝗁𝖾𝗋𝖺𝗀𝗁𝖼𝗁𝗂
@mahdi.ch

Huge congratulations to my amazing student Yeyuan Chen (+co-author Zihan Zhang of OSU advised by Zeyu Guo) for being awarded the STOC 2025 Best Student Paper Award! Their monumental result proves that explicit Reed-Solomon codes can correct more errors than previously known: arxiv.org/abs/2408.15925

arxiv.orgExplicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton BoundsIn this paper, we prove that explicit FRS codes and multiplicity codes achieve relaxed generalized Singleton bounds for list size $L\ge1.$ Specifically, we show the following: (1) FRS code of length $...

Hung Le reposted

Shivam Nadimpalli
@shivamnadimpalli.bsky.social

I got a lot out of participating in WALDO back in 2021, so I definitely recommend checking it out! 😄

Clément Canonne@ccanonne.github.io

An announcement: the Workshop on Algorithms for Large Data (Online) 2025 will take place 🗓️ April 14—16. waldo-workshop.github.io/2025.html Goal: "to generate new collaborations through an emphasis on big data algorithms, broadly defined" Register (free) by ⏰ April 7 to access the virtual platform

waldo-workshop.github.ioWorkshop on Algorithms for Large Data (Online) 2025

Hung Le reposted

Clément Canonne
@ccanonne.github.io

Hey, it's March now. You know what would be great? Nominating trailblazing TCS researchers to the Knuth Prize! www.sigact.org/prizes/knuth...

sigact.orgACM SIGACT - Knuth Prize
FOCS 2026@focs2026.bsky.social

Please nominate candidates to the 🏆 Knuth Prize, to be awarded this year during #STOC2025! The prize recognizes "major research accomplishments and contributions to the foundations of Computer Science over an extended period of time." ⏰ Deadline: March 31 www.sigact.org/prizes/knuth... #TCSSky

sigact.orgACM SIGACT - Knuth Prize

Hung Le reposted

Prashant Shenoy
@pshenoy.bsky.social

CRA statement on the cuts at NSF: "These cuts are the very definition of being pennywise and pound foolish — a shortsighted move that will undermine American innovation and technological leadership .." cra.org/cuts-to-nsf-...

cra.orgCuts to NSF and CISE Directorate Jeopardize American Leadership in ComputingA statement from the Computing Research Association (CRA) The reported termination today of 10 percent of the National Science Foundation’s (NSF) workforce — including significant cuts to the Compu…

Hung Le reposted

Greg Bodwin
@gbodwin.bsky.social

A proof is a logical argument written to convince a skeptical audience. A corollary is that the best way to read a proof is to roleplay as a skeptical audience.