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

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.