New SIGACT award expository work, created in memory of Luca Trevisan: "intended to promote and recognize high-impact work expositing ideas and results from the Theory of Computation." A wonderful initiative—consider nominating people! ⏰ Nomination deadline: April 10 sigact.org/prizes/trevi...

Given AIs, I am still not sure how to teach algorithm classes today and in the future. This discussion is quite nice, though. www.youtube.com/watch?v=Vnz8...

It's first round interview season and the most useful thing I can recommend is to spend time on these: csfaculty.github.io

#FOCS2025 This is one of the best FOCS conferences I have attended.

I just gave a tutorial on Design Templates for Dynamic Graph Algorithms at IISc in Bangalore. The kindest words I received were "best tutorial I have listened to in the last 10 years." Hope it interests you. Video: www.youtube.com/live/L8ev24g... Slides: tinyurl.com/yetx3vxu

The 2025 Chicago Junior Theorists Workshop is December 8-9, hosted jointly by Northwestern and TTIC. Monday Dec 8 will be at TTIC and Tuesday Dec 9 will be at Northwestern (in the SkAI/NITMB in the Hancock tower in downtown Chicago). Register in advance. theory.cs.northwestern.edu/2025/11/14/j...

The connection between distributed algorithms and descriptive set theory featured in Quanta: www.quantamagazine.org/a-new-bridge...

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

This talk is really illuminating to me (especially around minute 7 to 11). Clearly, I intuitively know what understanding is, but his explanation makes it much more explicit and makes sense. youtu.be/6fvXWG9Auyg?...

Announcing the 7th Learning Theory Alliance mentoring workshop on November 20. Fully free & virtual! Theme: Harnessing AI for Research, Learning, and Communicating Ft @aaroth.bsky.social @andrejristeski.bsky.social @profericwong.bsky.social @ktalwar.bsky.social &more

Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky

Nominate your final-year TCS PhD students or postdoc for the 2025 Chicago Junior Theorists Workshop (hosted by Northwestern and TTIC). theory.cs.northwestern.edu/2025/10/30/2...

Can a max flow algorithm be both near-optimal and simple enough to teach? Last year, we showed that the classical and intuitive augmenting-path approach can indeed be almost optimal for dense graphs. arxiv.org/abs/2406.03648 But the result was not actually satisfying! 1/3

📢 Our second TCS+ talk of the season will be Wednesday, Oct 22 (10amPT, 1pm ET, 19:00 CEST): Ian Mertz, from Charles University, will give guide us through "A Random Walk Down Full Memory Lane"! RSVP to receive the link (available one day prior to the talk): forms.gle/495UjiLmQkkD...

It was such a pleasure being a guest on "Math-Life Balance", a podcast devoted to interviews with mathematicians. Mura Yakerson is a fantastic interviewer! Check out our chat at www.youtube.com/watch?v=Gx8F... #mathsky

This is very impressive. Breaking the sorting barrier for directed single source shortest paths search.app/wnEUo

This lecture provides a gentle introduction to amortized analysis. For experts: At the end, I explained Hollow Heaps, an optimal heap like Fibonacci heaps, but simpler! Surprisingly, I have not seen video lectures on this before. www.youtube.com/watch?v=8mHa...

Math vs. Cooking: What does it mean to do math/theory? Here, I presented an analogy to cooking. The goal was to help students understand how to effectively learn in theory classes. www.youtube.com/watch?v=8Fz2... (The discussion at 59:38) I am curious to know if you think this makes sense.

The list of accepted papers at #FOCS2025 is up! focs.computer.org/2025/accepte...

Wow, this might be the best lecture on academic writing I've ever watched! www.youtube.com/watch?v=vtIz... If any of you have suggestions for good materials related to grant writing and/or mathematical writing, I would be interested :)

Professor Sepehr Assadi has won the 2025 Presburger Award, a prestigious honour recognizing his exceptional contributions to theoretical computer science, in particular his pioneering work on establishing lower bounds for multi-pass streaming algorithms. cs.uwaterloo.ca/news/sepehr-...

Omg

This year TCS for All Inspiration talk will be given by Sofya Raskhodnikova, Boston University on June 27th at our STOC 2025 TCS for All Meeting. Join us. We are relocating the TCS for All Rising Star Workshop to FOCS 2025 this year. Stay tuned. SIGACT.org/tcsforall/ #stoc2025 @ccanonne.github.io

How do you use AI to help you do research? I'd love to learn! I'll share how to use them below. 1/3

This graduate-level summer school at the Max Planck Institute (Aug 18–22) on "Graph Decompositions and Efficient Algorithms" looks pretty good! Ft. Maria Chudnovsky, Michał Pilipczuk, and Thatchaphol Saranurak (@eigx.bsky.social) Travel grant applications: June 30 www.mpi-inf.mpg.de/departments/...

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

Incredibly well deserved!!

This! I like to say, "Let p|A denote distribution p conditioned on event A. Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A. Except you don't have to imagine, because it's literally our world! Now explore probabilistic algorithms in this world."

Accepted papers for ICALP'25 is now online! Please register for amazing program and come visit us here in Aarhus! conferences.au.dk/icalp2025/ac...

Tuukka Korhonen Dynamic Treewidth in Logarithmic Time https://arxiv.org/abs/2504.02790

Taking a break from the submission season? Swing by the Workshop on Algorithms for Large Data (Online), WALDO 2025 🗓️ April 14—16: waldo-workshop.github.io/2025.html Registration is free! (but necessary by April 7)

An alternative name for log* that I quite like

I am very much looking forward to giving this talk at TCS+, which is one of my favourite seminars. Thanks for inviting me!

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

This new sorting algorithm is so simple and beautiful! I hope there is an easy analysis for this. arxiv.org/abs/2502.05082

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!

Take a Stand blog.computationalco...

Amazing result! There seems to be an upcoming IAS seminar for this broadcast over Zoom: www.ias.edu/math/events/...

:(

This looks very very interesting!

At STACS 2003 we published the first analysis of d-ary cuckoo hashing, but also described a less known open addressing technique called filter hashing which "can be used in combination with essentially any other hashing scheme to improve the space efficiency of the latter"

I am grateful to be awarded the Sloan Research Fellowship! Deep appreciation to my mentors, students, and colleagues for their guidance and support — this wouldn’t be possible without you. news.engin.umich.edu/2025/02/two-...

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

The alternative is to read with the view that the results could not possibly be correct, and the authors (those fools) could not possibly have proved it, and you will find the inevitable flaw. And then as you read you're slowly, begrudgingly, forced to admit that they were right after all.

If you just want to convince somebody that something like the Chernoff inequality should be correct, than the animation of the binomial distribution might be pretty convincing. If you just want to prove something, this might work: sarielhp.org/misc/blog/25... www.youtube.com/watch?v=sgGh...

Irit Dinur, Venkat Guruswami and I are organizing a 2-week program on HDX and Codes at ICTS-TIFR, Bengaluru, India. See attached poster for more details and how to apply for the program. www.icts.res.in/program/HDXa...

I love this paper by Bill Kuszmaul. His proof of Chernoff bound is much more illuminating than the standard algebraic proof I learned.

The Simons Foundation, which funds Quanta as an editorially independent magazine, created this video to honor the life of mathematician, investor and philanthropist Jim Simons. www.youtube.com/watch?v=RvjG...

Excited to co-organise another summer school on learning theory! This time in beautiful Odense, Denmark. Please share and apply here: event.sdu.dk/algoml2025

A nice lecture series on graph theory www.youtube.com/@DiestelGrap...