Virtual LIDS Seminar

Title: Thresholds for Reliable Computation with Noisy Gates, and Applications in Quantum Nonlocality

Speaker: Mary Wootters (Stanford University)

Date: Monday, November 9, 2020

Time: 4:00 PM EDT

Host: Prof. Guy Bresler

Zoom link: https://mit.zoom.us/j/94189117315

Meeting ID: 941 8911 7315

Abstract: Suppose you are given a bunch of logic gates -- ANDs, XORs, and NOTs -- but they are noisy, and with some probability will return the incorrect answer. At what noise levels is reliable computation possible using these gates?  We investigate this question when the gates have asymmetric noise levels (aka, the AND gates might have a different amount of noise than the XOR gates) and prove new results about when reliable computation is and is not possible.  While the statement about reliable communication is completely classical, our work is motivated by a question in the foundations of quantum mechanics: when are information-theoretic axioms like "communication complexity is non-trivial" enough to explain phenomena like the quantum value of the CHSH game?  Our work implies a limitation to an approach Brassard et al. to answer this question, and also allows us to construct a nonlocal game for which the axiom "communication complexity is non-trivial" *does* explain the quantum value.  In this talk I'll explain our results/approach for classical computation with noisy gates and sketch the connection to quantum nonlocality; no background in quantum mechanics will be assumed.  This talk is based on joint work with Noah Shutty and Patrick Hayden.

Biography: Mary Wootters is a professor of Computer Science and Electrical Engineering at Stanford University. She received a PhD in mathematics from the University of Michigan, a BA in math and computer science from Swarthmore College, and was an NSF postdoctoral fellow at Carnegie Mellon University. She works in theoretical computer science, applied math, and information theory; her research interests include error-correcting codes and randomized algorithms for dealing with high dimensional data. She is the recipient of an NSF CAREER award and was named a Sloan Research Fellow in 2019; she was named to the Stanford Tau Beta Pi Teaching honor roll in 2018-19 and 2019-20.

This talk is part of the LIDS Seminar Series. See the full schedule at: https://lids.mit.edu/news-and-events/lids-seminar-series.