Date & Time:
May 24, 2022 3:30 pm – 4:30 pm
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
05/24/2022 03:30 PM 05/24/2022 04:30 PM America/Chicago Avishay Tal (UC Berkeley) – On Certified Randomness from Quantum Advantage Experiments Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

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.

Host: Aaron Potechin


Avishay Tal

Assistant Professor, University of California, Berkeley

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.

Related News & Events

UChicago CS News

UChicago Partners With UMass On NSF Expedition To Elevate Computational Decarbonization As A New Field In Computing

May 23, 2024
UChicago CS News

Assistant Professor Raul Castro Fernandez Awarded NSF CAREER Grant to investigate Data-sharing Markets

May 21, 2024
UChicago CS News

Empowering Middle School Girls in Tech: compileHER’s <prompt/HER> Capstone Event

May 20, 2024
UChicago CS News

Haifeng Xu Wins Best Paper Award at Leading AI Conference for Pioneering Research on Mechanism Design for LLMs

May 17, 2024
UChicago CS News

Fred Chong Receives Quantrell Award for Excellence in Teaching

May 16, 2024
UChicago CS News

Unveiling Attention Receipts: Tangible Reflections on Digital Consumption

May 15, 2024
UChicago CS News

NASA to Launch UChicago Undergraduates’ Satellite

May 14, 2024
UChicago CS News

University of Chicago Computer Science Researchers To Present Ten Papers at CHI 2024

May 06, 2024
UChicago CS News

Two UChicago MPCS Students Win the Apple Swift Student Challenge

May 01, 2024
In the News

How Artificial Intelligence Can Transform U.S. Energy Infrastructure

Apr 29, 2024
In the News

Community Data Fellow Stephania Tello Zamudio helps broaden internet access for Illinois residents

Apr 29, 2024
UChicago CS News

Two UChicago CS Students Awarded NSF Graduate Research Fellowship

Apr 24, 2024
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube