Seminar Upcoming

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.

Icon of seminar time  Wednesdays, 12:30-13:30 (food starts at 12:15)
Icon of seminar place  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.

To join or leave our mailing list.

Algorithms Should Have Bullshit Detectors! (or Polynomial Time Byzantine Agreement with Optimal Resilience)
Show and Hide Ext. Content for Algorithms Should Have Bullshit Detectors! (or Polynomial Time Byzantine Agreement with Optimal Resilience)
Wed, February 15
Seth Pettie (University of Michigan)

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
idea?

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.

TBD
Show and Hide Ext. Content for TBD
Wed, May 3
Shay Solomon

TBD

TBD
Show and Hide Ext. Content for TBD
Wed, May 17
Thomas Vidick

TBD

TBD
Show and Hide Ext. Content for TBD
Wed, October 25
David Wajc

TBD