This is a research seminar aimed at PhD students and senior MSc students specializing in theoretical computer science, writ large. Every week, one of the students will give a talk, composed of three parts: general introduction to the area; recent work by the student; review of a paper in the area.
Tentative schedule:
- March 31: Yuval Filmus. I discussed Boolean Function Analysis through selected examples: collective coin flipping and the KKL theorem, and Kalai’s quantitative Arrow’s theorem. I then described my recent and ongoing work with Yaroslav Alekseev on approximate polymorphisms. Finally, I briefly described the paper A dense model theorem for the Boolean slice, comparing it to unpublished work by Irit Dinur and Avishay Tal on linearity testing on the middle slice.
- April 7: Vanessa Kosoy, PhD student of Shay Moran. She discussed learning theory, concentrating on online learning theory and Littlestone dimension. She then described her own work on ambiguous online learning. Finally, she discussed recent work on interactive decision making. Slides
- April 21: Antoine Vinciguerra, PhD student of Yuval Filmus. He will discuss catalytic computing, present an overview of Ryan Williams’ recent breakthrough, and describe his recent research project on the topic.
- April 28: Nikita Gaevoy, PhD student of Ofer Strichman. He will discuss algorithms for the Least Common Subsequence problem. In particular, he will discuss his work “Doubly-periodic string comparison” (CPM 2025), and will review this paper. For more, he recommends Tiskin’s extended survey.
- May 5: No class due to workshop.
- May 12: Yaroslav Alekseev, PhD student of Yuval Filmus. He will likely discuss proof complexity.
- May 19: George Haddad, MSc student of Nader Bshouty.
- May 26: Yoav Danieli, PhD student of Michael Kaminski.
- June 9: Open.
- June 16: Boaz Moav, PhD student of Eitan Yaakobi.
- June 23: No class due to conference.
- June 30: Alon Yerushalmi.
- July 7: Open.
