Lightnews — Scholar-powered news

Hung Le @hunglv.bsky.social · 16h

SODA26 accepted papers out: www.siam.org/conferences-...

ACM-SIAM Symposium on Discrete Algorithms (SODA26) will take place from January 11–14, 2026 in Vancouver, Canada. This symposium focuses on research topics related to the design and analysis of effici...

www.siam.org

1 5

Hung Le @hunglv.bsky.social · Aug 25

I did not expect the subtleties of the light version. Beautiful work!

1

Hung Le @hunglv.bsky.social · Aug 25

Some questions on spanners in my talk at the Simons Institute. Since the talk, progress has been made on a few questions, but most are open. minorfree.github.io/SpannerQues/

Some Questions on Spanners | Rambling on Graphs

minorfree.github.io

2 2 6

Hung Le @hunglv.bsky.social · Aug 10

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?

3 9

Hung Le @hunglv.bsky.social · Jun 3

Report new theory jobs here: kamathematics.wordpress.com/2025/06/03/t...

Theory Jobs 2025

The Theory community has a tradition of a crowdsourced spreadsheet of sharing who has accepted which jobs, previously hosted by Grigory Yaroslavtsev and Lance Fortnow. Past years have been slightly…

kamathematics.wordpress.com

Hung Le @hunglv.bsky.social · Jun 1

On a Dagstuhl workshop that I recently co-organized: minorfree.github.io/Dagstuhl/

Dagstuhl Workshop: Experience and Organization | Rambling on Graphs

minorfree.github.io

4

Reposted by Hung Le

Lance Fortnow @lance.fortnow.com · May 31

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

1 4 14

Reposted by Hung Le

Clément Canonne @ccanonne.github.io · Apr 30

The Call for Papers (CfP) for #SODA26 is out: www.siam.org/conferences-...

The submission server is open: soda26.hotcrp.com

Deadline: ⏰ Monday, July 14, AoE (July 15, 11:59am UTC)

SODA 2026

soda26.hotcrp.com

11 13

Hung Le @hunglv.bsky.social · Apr 13

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/

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

Roughly, 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 $γΔ$...

arxiv.org

1 5

Reposted by Hung Le

Sophie Huiberts @sophie.huiberts.me · Apr 8

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.

Optimal Smoothed Analysis of the Simplex Method

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

arxiv.org

1 8 71

Reposted by Hung Le

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

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

Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds

In 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 $...

arxiv.org

2 7 49

Reposted by Hung Le

Shivam Nadimpalli @shivamnadimpalli.bsky.social · Mar 19

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 · Mar 17

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

Workshop on Algorithms for Large Data (Online) 2025

waldo-workshop.github.io

1 7

Reposted by Hung Le

Clément Canonne @ccanonne.github.io · Mar 6

The next few talks on TCS+ (@tcsplus.bsky.social):
🍰 Tom Gur on Zero-Knowledge PCPs (March 19) (@tomgur.bsky.social)
🍰 Or Zamir on streaming and optimal F₂ moment estimation (April 9)
🍰 Ryan Williams on time v. memory (April 23) (@rrwilliams.bsky.social)

Sweet!

1 11 32

Reposted by Hung Le

Ryan Williams @rrwilliams.bsky.social · Mar 1

The STOC 2025 Theory Fest is looking for workshop proposals!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!

Vite + React + TS

stoc2025theoryfest.netlify.app

2 7

Reposted by Hung Le

Clément Canonne @ccanonne.github.io · Mar 2

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

www.sigact.org/prizes/knuth...

1 3 5

Reposted by Hung Le

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

CALL FOR PAPERS: With Robert Calderbank, Krishna Narayanan, Henry Pfister and Mary Wootters, I'm editing a special issue of the IEEE BITS magazine on Error-Correcting Codes & invite expository/tutorial articles.
Deadline: April 17 (white paper). Please circulate widely.
www.itsoc.org/sites/defaul...

www.itsoc.org

3 3

Reposted by Hung Le

Prashant Shenoy @pshenoy.bsky.social · Feb 19

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

Cuts to NSF and CISE Directorate Jeopardize American Leadership in Computing

A 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…

cra.org

1 1

Hung Le @hunglv.bsky.social · Feb 10

the Four Russians Method is a technique for speeding up Boolean matrix multiplication and dynamic programming. The original paper is in Russian, and I am not aware of any English translation. Now we have a translation, by Ben Rozonoyer, a PhD student at UMass.

minorfree.github.io/FourRussian/

The Four Russian Method: Now in English | Rambling on Graphs

minorfree.github.io

5

Reposted by Hung Le

FOCS 2025 @focs2025.bsky.social · Feb 8

The #FOCS2025 website is up! Featuring a Call for Papers and important dates: focs.computer.org/2025/

⏰ Deadline: April 3, 2025 (8pm ET)
⏰ Notification: July 8, 2025
🗓️ Conference: December 14–17, 2025

Content and info will be added as it becomes available (workshops, activities, travel support).

FOCS 2025

focs.computer.org

15 25

Hung Le @hunglv.bsky.social · Feb 7

STOC 25 accepted papers: acm-stoc.org/stoc2025/acc...

STOC 2025 - 57th ACM Symposium on Theory of Computing

acm-stoc.org

1 5

Hung Le @hunglv.bsky.social · Feb 7

So in 1999, people wrote a paper with 11 authors! Pretty amazing. How did they find each other?

1

Hung Le @hunglv.bsky.social · Feb 7

Ah this is amazing! Thanks for these.

2

Hung Le @hunglv.bsky.social · Feb 7

Just learnt about this: you can query DBLP to find out the most number of authors on a paper at a conf or a group of conf: SODA 11, FOCS 11, STOC 10. The new record this year at STOC 25 is 13.

дблп - ☮ Stop the war! @dblp.org · Feb 7

sparql.dblp.org/dblp/xZFrX9
Seems legit to me. ~MRA

dblp SPARQL

sparql.dblp.org

1

Reposted by Hung Le

Greg Bodwin @gbodwin.bsky.social · Feb 6

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.

2 2 10

Hung Le @hunglv.bsky.social · Feb 1

Is 13 the most number of authors on a STOC paper ever? I suspect Yes.

1 1