Reposted by Gary H
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
Reposted by Gary H
The directed next-to-shortest path problem was solved by 2 undergrads! arxiv.org/abs/2511.04345 Look out for Kuowen Chen and Yiran Zhang this PhD application cycle.
A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
Given a graph and a pair of terminals $s$, $t$, the next-to-shortest path problem asks for an $s\!\to \!t$ (simple) path that is shortest among all not shortest $s\!\to \!t$ paths (if one exists). Thi...
arxiv.org
December 4, 2025 at 5:36 PM
The directed next-to-shortest path problem was solved by 2 undergrads! arxiv.org/abs/2511.04345 Look out for Kuowen Chen and Yiran Zhang this PhD application cycle.
Reposted by Gary H
\'Edouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, Tom\'a\v{s} Masa\v{r}\'ik: Separator Theorem for Minor-Free Graphs in Linear Time https://arxiv.org/abs/2512.01587 https://arxiv.org/pdf/2512.01587 https://arxiv.org/html/2512.01587
December 2, 2025 at 6:31 AM
\'Edouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, Tom\'a\v{s} Masa\v{r}\'ik: Separator Theorem for Minor-Free Graphs in Linear Time https://arxiv.org/abs/2512.01587 https://arxiv.org/pdf/2512.01587 https://arxiv.org/html/2512.01587
Reposted by Gary H
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 Gary H
The connection between distributed algorithms and descriptive set theory featured in Quanta:
www.quantamagazine.org/a-new-bridge...
www.quantamagazine.org/a-new-bridge...
A New Bridge Links the Strange Math of Infinity to Computer Science | Quanta Magazine
Descriptive set theorists study the niche mathematics of infinity. Now, they’ve shown that their problems can be rewritten in the concrete language of algorithms.
www.quantamagazine.org
November 22, 2025 at 8:54 PM
The connection between distributed algorithms and descriptive set theory featured in Quanta:
www.quantamagazine.org/a-new-bridge...
www.quantamagazine.org/a-new-bridge...
Reposted by Gary H
I used AI to create an easier-to-navigate schedule for SODA and SOSA 26 here:
soda26.netlify.app
The original one is hard to see the overview. meetings.siam.org/program.cfm?...
soda26.netlify.app
The original one is hard to see the overview. meetings.siam.org/program.cfm?...
SODA/SOSA 2026 Schedule
soda26.netlify.app
November 21, 2025 at 4:42 AM
I used AI to create an easier-to-navigate schedule for SODA and SOSA 26 here:
soda26.netlify.app
The original one is hard to see the overview. meetings.siam.org/program.cfm?...
soda26.netlify.app
The original one is hard to see the overview. meetings.siam.org/program.cfm?...
Reposted by Gary H
Kuowen Chen, Nicole Wein, Yiran Zhang: A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs https://arxiv.org/abs/2511.04345 https://arxiv.org/pdf/2511.04345 https://arxiv.org/html/2511.04345
November 7, 2025 at 6:31 AM
Kuowen Chen, Nicole Wein, Yiran Zhang: A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs https://arxiv.org/abs/2511.04345 https://arxiv.org/pdf/2511.04345 https://arxiv.org/html/2511.04345
Reposted by Gary H
📢 Our first TCS+ talk of the season will be Wednesday, Oct 8 (10amPT, 1pm ET, 19:00 CEST): Janani Sundaresan, from U Waterloo, will tell us how "Distributed Triangle Detection is Hard in Few Rounds"!
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
TCS+ RSVP: Janani Sundaresan (2025/10/08)
Title: Distributed Triangle Detection is Hard in Few Rounds
forms.gle
September 27, 2025 at 9:42 PM
📢 Our first TCS+ talk of the season will be Wednesday, Oct 8 (10amPT, 1pm ET, 19:00 CEST): Janani Sundaresan, from U Waterloo, will tell us how "Distributed Triangle Detection is Hard in Few Rounds"!
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky
Reposted by Gary H
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/