Kasper Green Larsen
@kasperglarsen.bsky.social
Professor and Head of Algorithms, Data Structures and Foundations of Machine Learning at Computer Science, Aarhus University
CS at Aarhus University is hiring up to six professors of any rank and area! Come join my section and do cutting-edge research in TCS, database systems and/or ML/AI, both from a theory and applied side.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
Aarhus University is hiring Assistant, Associate and Full Professors for the Department of Computer Science - Vacancy at Aarhus University
Vacancy at Computer Science, Dept. of, Aarhus University
international.au.dk
October 21, 2025 at 6:08 AM
CS at Aarhus University is hiring up to six professors of any rank and area! Come join my section and do cutting-edge research in TCS, database systems and/or ML/AI, both from a theory and applied side.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
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!
conferences.au.dk/icalp2025
Please Share!
ICALP 2025 - Aarhus University, Denmark
The 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP) will take place in Aarhus, Denmark, July 8-11, 2025.
conferences.au.dk
June 3, 2025 at 1:22 PM
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!
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!
Please remember the early registration deadline on May 16th.
Look forward to seeing you in Aarhus!
Programme
conferences.au.dk
May 13, 2025 at 12:55 PM
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!
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
Accepted at COLT'25 🥳
arXiv: arxiv.org/pdf/2502.16462
May 5, 2025 at 5:46 PM
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
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
youtu.be/NfIBloXpjgU
Artificial Intelligence and Machine Learning: How does it work?
YouTube video by Kasper Green Larsen
youtu.be
May 2, 2025 at 11:11 AM
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
youtu.be/NfIBloXpjgU
Reposted by Kasper Green Larsen
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)
Reposted by Kasper Green Larsen
ICALP 2025 accepted list of papers is out: conferences.au.dk/icalp2025/ac...
Accepted Papers
conferences.au.dk
April 30, 2025 at 9:07 AM
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...
conferences.au.dk/icalp2025/ac...
Accepted Papers
conferences.au.dk
April 30, 2025 at 9:26 AM
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...
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...
Post doc position in theory of machine learning at Department of Computer Science, Aarhus University - Vacancy at Aarhus University
Vacancy at Computer Science, Dept. of, Aarhus University
international.au.dk
April 30, 2025 at 9:24 AM
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-...
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-...
ACM-SIAM Symposium on Discrete Algorithms (SODA26) | SIAM
www.siam.org
April 30, 2025 at 9:03 AM
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-...
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.
April 16, 2025 at 6:26 AM
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.
Reposted by Kasper Green Larsen
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
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...
international.au.dk/about/profil...
Tenure-Track Assistant Professor / Associate Professor in Bioinformatics at Aarhus University, Denmark - Vacancy at Aarhus University
Vacancy at Department of Molecular Biology and Genetics - BiRC - Bioinformatics Research Center, Aarhus University
international.au.dk
April 3, 2025 at 6:16 AM
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...
international.au.dk/about/profil...
Very honored and grateful for this recognition by the TCS community ❤️
Professor @kasperglarsen.bsky.social has been named 𝐄𝐀𝐓𝐂𝐒 𝐅𝐞𝐥𝐥𝐨𝐰 2025 by European Association for Theoretical Computer Science for his outstanding contributions to theoretical computer science 🎉 He will be inducted at the ICALP 2025 conference in Aarhus, this summer. Congrats, Kasper! 👏
March 18, 2025 at 8:49 AM
Very honored and grateful for this recognition by the TCS community ❤️
Reposted by Kasper Green Larsen
The submission server for #FOCS2025 is now open! Submit your work: focs25.hotcrp.com
FOCS25
focs25.hotcrp.com
March 16, 2025 at 1:28 AM
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
Link: stoc2025theoryfest.netlify.app
Vite + React + TS
stoc2025theoryfest.netlify.app
March 8, 2025 at 6:02 AM
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
Link: stoc2025theoryfest.netlify.app
Recorded today's lecture on streaming heavy hitters:
youtu.be/BAag04wVvr0?...
youtu.be/BAag04wVvr0?...
Streaming Heavy Hitters 1: Problem Definition and Naive Solutions
YouTube video by Kasper Green Larsen
youtu.be
March 3, 2025 at 1:22 PM
Recorded today's lecture on streaming heavy hitters:
youtu.be/BAag04wVvr0?...
youtu.be/BAag04wVvr0?...
Reposted by Kasper Green Larsen
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
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
ACM SIGACT - Knuth Prize
www.sigact.org
March 2, 2025 at 1:37 AM
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
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 😉
New preprint. And as mentioned yesterday, Mikael is on the job market 😉
February 25, 2025 at 6:27 AM
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 😉
New preprint. And as mentioned yesterday, Mikael is on the job market 😉
And Mikael presenting his second student paper at ALT’25 💪
February 24, 2025 at 2:12 PM
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!
February 24, 2025 at 1:54 PM
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 😉)
February 24, 2025 at 8:24 AM
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 😉)
Reposted by Kasper Green Larsen
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!
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!
people.csail.mit.edu
February 21, 2025 at 10:19 PM
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!
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
New arXiv preprint: arxiv.org/abs/2502.13692
February 20, 2025 at 9:42 AM
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
New arXiv preprint: arxiv.org/abs/2502.13692
Reposted by Kasper Green Larsen
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...
arxiv.org/abs/2502.130...
Improving Algorithmic Efficiency using Cryptography
Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time comple...
arxiv.org
February 19, 2025 at 7:56 AM
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...
arxiv.org/abs/2502.130...