Meike Neuwohner, Vera Traub, Rico Zenklusen Approximation Schemes for Planar Graph Connectivity Problems https://arxiv.org/abs/2512.21128

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

📢 #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)

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

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.

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

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/

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

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

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

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)

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/

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.

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

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

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!

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

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

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

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

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

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

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.

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.

STOC25 notification was out. A record number of submissions, 735, and acceptances, 218. To compare with SODA 25, 655 submissions and 192 acceptances. This is probably the 1st time STOC has more submissions and acceptances than SODA.

New post summerizes what I've learnt over the last few years about Locality Sensitive Ordering, a technique for reducing geometric problems in R^d to problems in the line (1D): minorfree.github.io/LSO/

My latest in @quantamagazine.bsky.social: why theoretical computer scientists like to pose questions to imaginary black boxes:

New breakthrough first poly-log approximation for directed steiner tree in polytime by Bundit Laekhanukit: arxiv.org/abs/2412.10744

I might be the last horse to cross the finish line here, but I learned today that the length "1em" in tex doesn't stand for anything, rather, it's called that because it's exactly the length of one uppercase M 🤯

A kind reminder to everyone that the golden rule of peer review is "Do not write a review that you wouldn't want to receive yourself." Even rejection can be done in a way that is helpful to the authors. If a paper is not in your area, you should decline reviewing it instead of rejecting by default.

*AI for Mathematics and Theoretical Computer Science*, a workshop hosted jointly by the Simons Institute for the Theory of Computing and the Simons Laufer Mathematical Sciences Institute, will be held in Berkeley at April 7-11, 2025. simons.berkeley.edu/workshops/si...

The PCP theorem, a jewel of theoretical computer science, establishes that any NP statement can be assessed by a randomized verifier who only checks a vanishing fraction of the proof (indeed, a constant # of characters!) This has had incredible impact, most notably on how ML reviews are conducted

Nice post, and congrats on the new results! Related problem: Prove for any set of |S|>=n^{2/3} nodes, there is a subgraph on O(|S|^2) edges that preserves all distances within S. This would imply the +4 spanner. IMO it's the second-biggest open problem in the area, behind the girth conjecture.

New post on additive spanners. Oustanding open problem: construct a +4 spanner with O(n^{4/3}) edges.

It's tough to gain visibility as a young researcher, and it's job market season! Are you a theoretical computer science PhD/postdoc on the job market? I don't have a crazy juge audience but I'll try to help a bit: fill this form, and I'll tweet your pitch and info! docs.google.com/forms/d/e/1F...

By the way, the program for ITCS'25 (Jan 7-10 at Columbia University, NYC) has been posted: itcs-conf.org/itcs25/itcs2... (Looks like I'll be opening the conference...)

With 330 submissions and 21 acceptances (6.4% acceptance rate), the NeurIPS high school project track may be the new most selective ML venue! blog.neurips.cc/2024/11/18/a...