This talk looks interesting. For background, if you have free PR boxes (ie.. devices that win CHSH w/ prob 1) then any function f(x,y) can be computed using one bit of communication between the parties holding x and y. This is what the abstract refers to as "communication complexity becoming trivial." Later work showed that this result holds even if your boxes win only w/ prob 0.95 (or something like that) but it wasn't known if these arguments could be pushed all the way down to the quantum value 0.878... So it sounds like this work was able to achieve this goal for a different game. ---------- Forwarded message --------- From: Francisco Jaimes &lt;fjaimes(a)mit.edu&gt; Date: Wed, Nov 4, 2020 at 1:13 PM Subject: [Lids-seminars] Virtual LIDS Seminar Series - Mary Wootters (Stanford) // Monday, November 9, 2020 To: lids-all &lt;lids-all(a)mit.edu&gt;du>, lids-seminars &lt;lids-seminars(a)mit.edu&gt;du>, idss-student &lt;idss-student(a)mit.edu&gt;du>, idss-postdoc &lt;idss-postdoc(a)mit.edu&gt;du>, aa-grad &lt;aa-grad(a)mit.edu&gt;du>, toc-students(a)csail.mit.edu < toc-students(a)csail.mit.edu&gt;gt;, toc-postdocs(a)csail.mit.edu < toc-postdocs(a)csail.mit.edu&gt;gt;, Andrew Carvalho &lt;acarvalh(a)mit.edu&gt;du>, eecs-communications &lt;eecs-communications(a)mit.edu&gt;du>, Rachida Kernis < rkernis(a)mit.edu&gt;gt;, Janet E Fischer &lt;jfischer(a)mit.edu&gt; *Virtual LIDS Seminar* *Title: *Thresholds for Reliable Computation with Noisy Gates, and Applications in Quantum Nonlocality *Speaker: *Mary Wootters <https://sites.google.com/site/marywootters> (Stanford University) *Date: *Monday, November 9, 2020 *Time:* 4:00 PM EDT *Host: *Prof. Guy Bresler <https://www.mit.edu/~gbresler/> *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 <https://stanford.edu/~noaj/> and Patrick Hayden <https://web.stanford.edu/~phayden/>. *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. Francisco Jaimes Laboratory for Information and Decision Systems Massachusetts Institute of Technology 32 Vassar Street, Building 32-D775 Cambridge, MA 02139 Telephone: (617) 253–2142 Email: fjaimes(a)mit.edu URL: lids.mit.edu [image: signature_817792918] _______________________________________________ Lids-seminars mailing list Lids-seminars(a)mit.edu http://mailman.mit.edu/mailman/listinfo/lids-seminars _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip