Reposted by Hung Le
Meike Neuwohner, Vera Traub, Rico Zenklusen
Approximation Schemes for Planar Graph Connectivity Problems
https://arxiv.org/abs/2512.21128
Approximation Schemes for Planar Graph Connectivity Problems
https://arxiv.org/abs/2512.21128
December 25, 2025 at 5:45 AM
Meike Neuwohner, Vera Traub, Rico Zenklusen
Approximation Schemes for Planar Graph Connectivity Problems
https://arxiv.org/abs/2512.21128
Approximation Schemes for Planar Graph Connectivity Problems
https://arxiv.org/abs/2512.21128
Reposted by Hung Le
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
December 20, 2025 at 11:40 PM
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
Reposted by Hung Le
📢 #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)
Nov 8–11, 2026 at NYU (colocated with TCC)
General Chair: Marshall Ball
PC Chair: Sanjeev Khanna (Co-Chair: Sepehr Assadi)
December 15, 2025 at 7:43 AM
📢 #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)
Nov 8–11, 2026 at NYU (colocated with TCC)
General Chair: Marshall Ball
PC Chair: Sanjeev Khanna (Co-Chair: Sepehr Assadi)
Stoked about the new work with Édouard Bonnet, Tuukka Korhonen, Jason Li, and Tomáš Masařík: a simple linear time algorithm to find a balanced separator in minor-free graphs.
A more detailed blog post, giving a complete pseudocode: minorfree.github.io/SepLinear/
Paper: arxiv.org/abs/2512.01587
A more detailed blog post, giving a complete pseudocode: minorfree.github.io/SepLinear/
Paper: arxiv.org/abs/2512.01587
A Separator for Minor-free Graphs in Linear Time | Rambling on Graphs
minorfree.github.io
December 8, 2025 at 6:58 PM
Stoked about the new work with Édouard Bonnet, Tuukka Korhonen, Jason Li, and Tomáš Masařík: a simple linear time algorithm to find a balanced separator in minor-free graphs.
A more detailed blog post, giving a complete pseudocode: minorfree.github.io/SepLinear/
Paper: arxiv.org/abs/2512.01587
A more detailed blog post, giving a complete pseudocode: minorfree.github.io/SepLinear/
Paper: arxiv.org/abs/2512.01587
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.
November 24, 2025 at 8:25 PM
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.
Reposted by Hung Le
STOC 2026 is offering experimental pre-submission feedback using an AI tool optimized for checking mathematical rigor. Results won't go to PC or be used for training purposes. Opt-in via the submission server by November 1.
Details: acm-stoc.org/stoc202...
CFP: acm-stoc.org/stoc202...
Details: acm-stoc.org/stoc202...
CFP: acm-stoc.org/stoc202...
October 25, 2025 at 5:16 PM
STOC 2026 is offering experimental pre-submission feedback using an AI tool optimized for checking mathematical rigor. Results won't go to PC or be used for training purposes. Opt-in via the submission server by November 1.
Details: acm-stoc.org/stoc202...
CFP: acm-stoc.org/stoc202...
Details: acm-stoc.org/stoc202...
CFP: acm-stoc.org/stoc202...
SODA26 accepted papers out: www.siam.org/conferences-...
Accepted Papers | SIAM
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
October 14, 2025 at 12:40 PM
SODA26 accepted papers out: www.siam.org/conferences-...
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
August 25, 2025 at 12:56 PM
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/
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?
August 10, 2025 at 2:40 PM
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?
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
June 3, 2025 at 2:01 PM
Report new theory jobs here: kamathematics.wordpress.com/2025/06/03/t...
On a Dagstuhl workshop that I recently co-organized: minorfree.github.io/Dagstuhl/
Dagstuhl Workshop: Experience and Organization | Rambling on Graphs
minorfree.github.io
June 1, 2025 at 8:32 PM
On a Dagstuhl workshop that I recently co-organized: minorfree.github.io/Dagstuhl/
Reposted by Hung Le
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/2
May 31, 2025 at 4:16 PM
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/2
Reposted by Hung Le
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)
The submission server is open: soda26.hotcrp.com
Deadline: ⏰ Monday, July 14, AoE (July 15, 11:59am UTC)
SODA 2026
soda26.hotcrp.com
April 30, 2025 at 8:13 AM
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)
The submission server is open: soda26.hotcrp.com
Deadline: ⏰ Monday, July 14, AoE (July 15, 11:59am UTC)
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/
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
April 13, 2025 at 9:48 PM
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/
Their paper here: arxiv.org/abs/2504.00278
My take: minorfree.github.io/PaddedSolved/
Reposted by Hung Le
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.
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
April 8, 2025 at 12:22 PM
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.
I spent a huge part of my life on this, and it feels weird that it's now finished.
Reposted by Hung Le
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.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
April 4, 2025 at 4:08 PM
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.org/abs/2408.15925
Reposted by Hung Le
I got a lot out of participating in WALDO back in 2021, so I definitely recommend checking it out! 😄
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.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
March 19, 2025 at 6:42 PM
I got a lot out of participating in WALDO back in 2021, so I definitely recommend checking it out! 😄
Reposted by Hung Le
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!
🍰 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!
March 6, 2025 at 10:13 AM
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!
🍰 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!
Reposted by Hung Le
The STOC 2025 Theory Fest is looking for workshop proposals!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
Vite + React + TS
stoc2025theoryfest.netlify.app
March 1, 2025 at 3:06 PM
The STOC 2025 Theory Fest is looking for workshop proposals!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
Reposted by Hung Le
Hey, it's March now. You know what would be great? Nominating trailblazing TCS researchers to the Knuth Prize!
www.sigact.org/prizes/knuth...
www.sigact.org/prizes/knuth...
March 2, 2025 at 1:39 AM
Hey, it's March now. You know what would be great? Nominating trailblazing TCS researchers to the Knuth Prize!
www.sigact.org/prizes/knuth...
www.sigact.org/prizes/knuth...
Reposted by Hung Le
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...
Deadline: April 17 (white paper). Please circulate widely.
www.itsoc.org/sites/defaul...
www.itsoc.org
February 20, 2025 at 10:59 PM
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...
Deadline: April 17 (white paper). Please circulate widely.
www.itsoc.org/sites/defaul...
Reposted by Hung Le
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.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
February 19, 2025 at 2:19 AM
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.org/cuts-to-nsf-...
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/
minorfree.github.io/FourRussian/
The Four Russian Method: Now in English | Rambling on Graphs
minorfree.github.io
February 10, 2025 at 6:21 PM
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/
minorfree.github.io/FourRussian/
Reposted by Hung Le
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).
⏰ 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
February 8, 2025 at 9:04 PM
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).
⏰ 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).
STOC 25 accepted papers: acm-stoc.org/stoc2025/acc...
STOC 2025 - 57th ACM Symposium on Theory of Computing
acm-stoc.org
February 7, 2025 at 10:42 PM
STOC 25 accepted papers: acm-stoc.org/stoc2025/acc...