Reminder: The FINAL registration deadline for ICALP'25 is coming up on June 20th. Hope to see you in Aarhus! conferences.au.dk/icalp2025 Please Share!

The ICALP program is now online at conferences.au.dk/icalp2025/pr... Please remember the early registration deadline on May 16th. Look forward to seeing you in Aarhus!

Almost tight generalisation bounds for large margin voting classifiers and an optimal Majority-of-3-AdaBoosts weak-to-strong learner. Accepted at COLT'25 🥳 arXiv: arxiv.org/pdf/2502.16462

In the Fall, I gave a public lecture on AI and Machine Learning for the Academy of Science in Denmark. I finally finished an English version. The video introduces the basic ideas of AI and ML for any audience with a high school background or math interest. Please share! youtu.be/NfIBloXpjgU

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)

ICALP 2025 accepted list of papers is out: conferences.au.dk/icalp2025/ac...

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

I have an opening for a post doc position in machine learning theory, with a deadline of June 1st. Please share and apply: international.au.dk/about/profil...

The SODA'26 Call for Papers and submission server is now online! Deadline July 14 AOE. Please share and submit your awesome work! Look very much forward to co-chairing the program committee with Barna Saha @barnacs.bsky.social and the 82 other amazing PC members. www.siam.org/conferences-...

On behalf of Raghu Meka: Students at US universities can apply for travel support to attend STOC 2025 Theory Fest (June 23-27, Prague CZ). The deadline for applications is April 27th. Link in comment.

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

The bioinformatics research centre at Aarhus University is looking for TT Assistant + Associate Professors with a data science/ML/algorithms background. Apply here by June 1st international.au.dk/about/profil...

Very honored and grateful for this recognition by the TCS community ❤️

The submission server for #FOCS2025 is now open! Submit your work: focs25.hotcrp.com

STOC 2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals! Deadline March 9, so please hurry and submit your great proposals and please repost! Link: stoc2025theoryfest.netlify.app

Recorded today's lecture on streaming heavy hitters: youtu.be/BAag04wVvr0?...

Please nominate candidates to the 🏆 Knuth Prize, to be awarded this year during #STOC2025! The prize recognizes "major research accomplishments and contributions to the foundations of Computer Science over an extended period of time." ⏰ Deadline: March 31 www.sigact.org/prizes/knuth... #TCSSky

An almost tight understanding of AdaBoost's generalisation, a proof that Majority-of-3-AdaBoosts is an optimal weak-to-strong learner in expectation and better margin-generalisation for voting classifiers. New preprint. And as mentioned yesterday, Mikael is on the job market 😉

And Mikael presenting his second student paper at ALT’25 💪

Arthur about to present our paper on sample compression schemes at ALT’25. He is also on the job market and is amazing as well!

Proud advisor 🥹 Mikael presenting his single-authored paper at ALT’25. He is an amazing student and is on the post doc job market (hint, hint 😉)

New paper: Simulating Time With Square-Root Space people.csail.mit.edu/rrw/time-vs-... It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}]. To appear in STOC. Comments are very welcome!

Finally completely tight margin-based generalisation bounds for halfspaces. Very cool proof combining random discretizations with Rademacher complexity in a highly non-trivial way. New arXiv preprint: arxiv.org/abs/2502.13692

This sounds very cool! The insight appears to be that if you can fool any computationally bounded adversaries, then you can fool any reasonable algo looking at the result of your computations. I.e., see the world as an "adversary", use cryptographic primitives to fool it. arxiv.org/abs/2502.130...

Using multi-color discrepancy to prove lower bounds for fair allocations of indivisible items among agents. New arXiv preprint: arxiv.org/abs/2502.10516

In today's lecture in Randomized Algorithms, we covered Streaming Algorithms for Frequency Estimation (Misra-Gries, CountMin, CountSketch). Will be followed by Heavy Hitters later. For anyone interested, here's a YouTube playlist www.youtube.com/watch?v=JS8Q...

Please nominate the most outstanding PhD dissertations in Theoretical Computer Science for the EATCS Distinguished Dissertation Award. The dissertation must have been successfully defended in 2024. Looking much forward to reading your nominations! eatcs.org/index.php/di...

Welcome @stefaniezollmann.bsky.social 👋🏻😀 Stefanie joins the department as Associate Professor, bringing expertise in AR, Computer Vision & Computer Graphics. Excited to see her impact on research & teaching! 🎉 Learn more➡️https://cs.au.dk/news-events/meet-our-new-faculty-member-stefanie-zollmann

Recording some of my lectures in Randomized Algorithms. Today was on Hash Functions. Maybe some of you would find it interesting with a thorough introduction to basic definitions like Universal Hashing etc. www.youtube.com/playlist?lis...

How many queries does it take to estimate the volume of the union of a set of geometric objects? We now have a tight lower bound and improved bounds for the special Klee's measure problem. Accepted at SoCG'25: Symp. on Computational Geometry. arxiv.org/abs/2410.00996

Submit your papers to ICALP'25 by February 8th and visit us in lovely Aarhus! conferences.au.dk/icalp2025 Have been working hard with @iannis.bsky.social as General Chairs to plan an amazing week for you!

Significantly improved sample complexity of replicable boosting via a majority of smooth-boosters. New arxiv preprint: arxiv.org/abs/2501.18388

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 neat framework for analyzing learning algorithms based on sub-sampling the training data, with applications in boosting! arxiv.org/abs/2402.02976 Accepted at ALT25 🥳

In case you missed my awesome post doc Arthur da Cunha's Oral Presentation of our "Optimal Parallelization of Boosting" at #NeurIPS2024, I recorded a (slightly extended) version here. youtu.be/BGZJMwhQc4U

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

Recorded an extended version of my MFCS'24 invited talk. The talk presents my personal experiences in entering learning theory with a TCS background. The target audience is mostly TCS researchers. Hope some of you might enjoy it. youtu.be/ZYe2mITwww4

Reminder that we are hiring TT Assistant Profs and Assoc Profs broadly in CS. Expect to hire 4 candidates. Send your application by Jan 13 and join my amazing colleagues and I. cs.au.dk/about-us/vac...

Hello BlueSky! Great to see so many awesome colleagues here 🦋