BIU theory seminar - April 19 : Seth Pettie - Algorithms Should Have Bullshit Detectors! (or Polynomial Time Byzantine Agreement with Optimal Resilience)
4 views
Skip to first unread message
Arnold Filtser
Apr 17, 2023, 1:43:00 AM4/17/23
to BIU Theory Seminar, se...@pettie.net, eio...@gmail.com
Hello all,
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.
https://arxiv.org/abs/2206.15335.
There is a schedule change in the theory seminar. The talk by Roie Levin is postponed to May 10, and instead, this Wednesday we will have a talk by Seth Pettie.
This will also be Seth's last day in BIU (and Israel), so be sure to come and say goodbye.
Location: Building 605 room 14.
See you there at 12,
Arnold
Speaker: Seth Pettie (UMICH)
Title: Algorithms Should Have Bullshit Detectors! (or Polynomial Time Byzantine Agreement with Optimal Resilience)
Abstract: One thing that distinguishes (theoretical) computer science from other
scientific disciplines is its full-throated support of a fundamentallyTitle: Algorithms Should Have Bullshit Detectors! (or Polynomial Time Byzantine Agreement with Optimal Resilience)
Abstract: One thing that distinguishes (theoretical) computer science from other
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.
https://arxiv.org/abs/2206.15335.
Arnold Filtser
Apr 19, 2023, 4:01:18 AM4/19/23
to BIU Theory Seminar, se...@pettie.net, eio...@gmail.com
The seminar starts in one hour!
Reply all
Reply to author
Forward
0 new messages