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, 12:30-13:30 (food starts at 12:15)
Room 201, Taub Building
The online meetings were generally recorded, and available on YouTube.
If you are interested in giving a talk at the seminar, contact Idan Mehalel.
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.
One thing that distinguishes (theoretical) computer science from other
scientific disciplines is its full-throated support of a fundamentally
adversarial view of the universe. Malicious adversaries, with
unbounded computational advantages, attempt to foil our algorithms at
every turn and destroy their quantitative guarantees. However, there
is one strange exception to this world view and it is this: the
algorithm must accept its input as sacrosanct, and may never simply
reject its input as illegitimate. But what if some inputs really are
illegitimate? Is building a “bullshit detector” for algorithms a good
To illustrate the power of the Bullshit Detection worldview, we give
the first polynomial-time protocol for Byzantine Agreement that is
resilient to f<n/3 corruptions against an omniscient, computationally
unbounded adversary in an asynchronous message-passing model. (This is
the first improvement to Ben-Or and Bracha’s exponential time
protocols from the 1980s that are resilient to f<n/3 corruptions.) The
key problem is to design a coin-flipping protocol in which corrupted
parties (who chose the outcomes of their coins maliciously) are
eventually detected via statistical tests.
We will also discuss other algorithmic contexts in which bullshit
detection might be useful.