The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.
Wednesdays, 13:00-14:00 (food starts at 12:45)
Room 201 (note return to traditional room), Taub Building
If you are interested in giving a talk at the seminar, contact Omri Ben-Eliezer and/or David Wajc.
The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.
To join or leave our mailing list.
Ensuring that AI systems behave as intended is a central challenge in contemporary AI. This talk offers an exposition of provable mathematical guarantees for learning and security in AI systems.
Starting with a classic learning-theoretic perspective on generalization guarantees, we present two results quantifying the amount of training data that is provably necessary and sufficient for learning:
(1) In online learning, we show that access to unlabeled data can reduce the number of prediction mistakes quadratically, but no more than quadratically [NeurIPS23, NeurIPS25 Best Paper Runner-Up].
(2) In statistical learning, we discuss how much labeled data is actually necessary for learning—resolving a long-standing gap left open by the celebrated VC theorem [COLT23].
Provable guarantees are especially valuable in settings that require security in the face of malicious adversaries. The main part of the talk adopts a cryptographic perspective, showing how to:
(1) Utilize interactive proof systems to delegate data collection and AI training tasks to an untrusted party [ITCS21, COLT23, NeurIPS25].
(2) Leverage random self-reducibility to provably remove backdoors from AI models, even when those backdoors are themselves provably undetectable [STOC25].
Assaf Reiner (Hebrew University)
Lossless vertex expanders are d-regular (or biregular) graphs in which every small set of vertices S has almost the largest possible number of neighbors d|S|. While random regular graphs are known to be lossless expanders with high probability, constructing them explicitly has been a longstanding challenge.
In this talk, I will present the first explicit construction of constant-degree two-sided lossless vertex expanders. The resulting graphs also admit a free group action, and hence realize the new families of good quantum LDPC codes due to Lin and Hsieh. The construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from LPS Ramanujan cubical complexes, which are natural high-dimensional generalizations of the well-known LPS Ramanujan graphs.
Based on joint work with Jun-Ting Hsieh, Alex Lubotzky, Sidhanth Mohanty and Rachel Zhang (FOCS 2025).
Upcoming
