Hi all, Matt will be giving a talk about our result on infinite randomness expansion this Thursday, 4pm (in Stata, 32-G575), which will also be presented at QIP in two weeks. The abstract can be found below. Hope to see you there! Henry ---------- Forwarded message ---------- From: Ilya Razenshteyn <ilyaraz(a)mit.edu> Date: Sun, Jan 19, 2014 at 4:57 PM Subject: [A&C seminar] A talk by Matt Coudron this Thursday! To: compalgsem(a)lists.csail.mit.edu, theory-seminars(a)lists.csail.mit.edu Hi! After a long break, we continue our A&C seminar! This _THURSDAY_ 4pm (location is still TBA, but tentatively let's aim at the good old 32-G575) Matt Coudron from MIT will present his exciting joint work with Henry Yuen (also from MIT) about Infinite Randomness Expansion. See the title and and the abstract below, and don't forget to read a great blog post by Henry: http://mittheory.wordpress.com/2013/12/25/can-you-tell-if-a-bit-is-random/ . Hope to see you all there! Ilya TITLE: Infinite Randomness Expansion with a Constant Number of Devices ABSTRACT: We present a device-independent randomness expansion protocol, involving only a constant number of non signaling quantum devices, that achieves infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(−Ω(m^1/3))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m). This settles an open problem in the area of randomness expansion and device-independence. We also present a protocol that achieves infinite randomness amplification using a constant number of devices. The input seed is not necessarily uniform, but can be generated from a Santha-Vazirani source, a type of weak randomness. The output is still nearly uniform, secure against a quantum adversary, and can be arbitrarily long. In contrast, it is well known that classically one cannot extract even a single near-uniform bit from a Santha-Vazirani source. The analysis of our protocols involves overcoming fundamental challenges in the study of adaptive device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are Input Secure; that is, their output is guaranteed to be secure against a quantum eavesdropper, even if the input randomness was generated by that same eavesdropper! The notion of Input Security may be of independent interest to other areas such as device independent quantum key distribution. Join work with Henry Yuen. _______________________________________________ Compalgsem mailing list Compalgsem(a)lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/compalgsem _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip