Santa Fe Institute

Seminar

October 10, 2012
12:15 PM
Collins Conference Room

Aram Harrow (University of Washington)

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.

Purpose: Research Collaboration

SFI Host: Cris Moore

More Info

• * SFI community lectures are free, open, & accessible to the public.
• * Seminars & colloquia are geared for scientists but free & open to the interested public.
• * All other SFI events are by invitation only.
• * Note: We are unable to accommodate members of the public for SFI's limited lunch service; you're welcome to bring your own.