[Colloquium] CS Theory Seminar - Avishay Tal, Tuesday, May 24, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO

COMPUTER SCIENCE DEPARTMENT

PRESENTS


Avishay Tal, PhD
University of California, Berkeley


 [A person smiling for the camera  Description automatically generated with medium confidence]

Tuesday, May 24, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107


“On certified randomness from quantum advantage experiments”

 Abstract:  Certified randomness is the ability to generate random bits that one can certify their randomness to a skeptic, without placing any trust in the experimental device. Recently Aaronson (Aaronson 2018, 2020) proposed a novel certified randomness protocol based on existing random circuit sampling experiments - placing this application within reach of near-term quantum devices. However, the security of Aaronson's protocol relies on non-standard conjectures that were not previously studied in the literature. In joint work with Roozbeh Bassirian, Adam Bouland, Bill Fefferman, and Sam Gunn, we prove two versions of Aaronson’s conjectures unconditionally in the black-box (aka, random-oracle) setting.

In this talk, I will describe the setting and applications and give a brief proof outline of one of our results. The presentation will be self-contained and not assume much prior knowledge about quantum computing.

Bio: Avishay Tal is an Assistant Professor at the University of California, Berkeley. His research interests include computational complexity theory, analysis of Boolean functions, quantum computing, pseudo randomness, and learning theory. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science and later held postdoctoral appointments at the Institute for Advanced Study and at Stanford University.

Host: Aaron Potechin




--
Jose J Fragoso
Project Assistant IV
Computer Science Department
5730 S. Ellis – Room 200C
Chicago, IL. 60637
jfragoso at uchicago.edu
(773) 702-6614
(773) 702-8487 FAX

[signature_1572818061]



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220516/3e3505cc/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 34683 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220516/3e3505cc/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 459613 bytes
Desc: image003.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220516/3e3505cc/attachment-0001.png>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220516/3e3505cc/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220516/3e3505cc/attachment-0003.txt>