October 10, 2012
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
The popular Science On Screen series continued Wednesday, May 8, with SFI's Simon DeDeo and the 1992 cult hacker film Sneakers. If you missed it, you can hear DeDeo ...
SFI's 2013 Community Lecture series debuted March 14 with UC-Boulder's Leysia Palen describing how victims, observers, and “citizen-responders” are using modern technology to participate in disaster response. Watch ...
Speaking at SFI yesterday, noted climate scientist James Hansen told an overflow crowd that efforts to stem climate change will be ineffectual as long as fossil fuels remain the cheapest ...
SFI's crowdfunding campaign has reached its goal. The resulting research will help scientists preserve the threatened landscapes on which indigenous human groups depend.
The 2012 Science On Screen series in Santa Fe wrapped up December 13 to a full house, with "The Gods Must Be Crazy" and Murray Gell-Mann's distinctive insight and ...