Aram Harrow of the University of Washington will present Fault-Tolerant Memory and Computation in the Presence of Adversarial Noise at 12:15 p.m. Wednesday, Oct. 10 in the Medium Conference Room at the Santa Fe Institute.
Abstract: Theoretical and practical work on fault-tolerant computation has shown that it is possible to compute reliably in the presence of a sufficiently small constant rate of random noise.
In this work, we consider for the first time the case of adversarial noise; i.e. an adversary who can choose a small constant fraction of bits to flip after each step of the computation.
We describe constructions for reliable memory and computation in the presence of adversarial noise.
Our methods of fault-tolerant computations are based on locally-decodable codes, and we also give a converse showing that being able to perform adversarial-noise-tolerant computation implies the existence of locally decodable codes.
Our results are applicable only for classical computers, and we conjecture that fault-tolerant quantum computing is impossible in the presence of adversarial noise. Joint work with Matt Hastings and Anup Rao.
Note: We are unable to accommodate members of the public for SFI’s limited lunch service; you’re welcome to bring your own.
SFI Host: Cris Moore http://www.santafe.edu/gevent/detail/science/1130/
The Santa Fe Institute‘s mission is to foster a transdisciplinary research community that endeavors to expand the boundaries of scientific understanding.
Its aim is to discover and comprehend the common fundamental principles in physical, computational, biological, and social systems that underlie many of the most profound problems facing science and society today.