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 <fjaimes(a)mit.edu>
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 <lids-all(a)mit.edu>, lids-seminars <lids-seminars(a)mit.edu>,
idss-student <idss-student(a)mit.edu>, idss-postdoc <idss-postdoc(a)mit.edu>,
aa-grad <aa-grad(a)mit.edu>, toc-students(a)csail.mit.edu <
toc-students(a)csail.mit.edu>, toc-postdocs(a)csail.mit.edu <
toc-postdocs(a)csail.mit.edu>, Andrew Carvalho <acarvalh(a)mit.edu>,
eecs-communications <eecs-communications(a)mit.edu>, Rachida Kernis <
rkernis(a)mit.edu>, Janet E Fischer <jfischer(a)mit.edu>
*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