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 discuss proof complexity: the definition of a Cook–Reckow proof system; the Resolution proof system; lower bound on the Pigeonhole Principle via width; his recent work on the Res(⊕) proof system.
- May 19: George Haddad, MSc student of Nader Bshouty. He will discuss learning parity with noise, showing that approximating the number of relevant variables is as hard as properly learning parities.
- May 26: Yoav Danieli, PhD student of Michael Kaminski. He will discuss finite automata on infinite alphabets, describing some decidability results and some undecidability results, the latter proved via the Post correspondence problem and Hilbert’s 10th problem.
- June 9: Noor Athamnah, MSc student of Ron Rothblum. She will discuss zero-knowledge proofs, and in particular, her work on rate-1 zero-knowledge proofs.
- June 16: Boaz Moav, PhD student of Eitan Yaakobi. He will discuss coding for DNA storage, specifically, indel codes.
- June 23: No class due to conference.
- June 30: Alon Yerushalmi.
- July 7: Open.
