Date & Time:
May 24, 2022 3:30 pm – 4:30 pm
Location:
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

Speakers

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

PhD Candidate Bogdan Stoica Receives Distinguished Artifact Evaluator Award for Championing Reproducibility in Computer Science

Jul 14, 2025
UChicago CS News

Report from GlobusWorld 2025: Going Beyond Data

Jul 10, 2025
headshots
UChicago CS News

University of Chicago PhD Graduates Secure Tenure-Track Faculty Positions Amid a Competitive Job Market

Jun 25, 2025
text to 3d example
UChicago CS News

Democratizing Digital Graphics: An Undergrad’s Unlikely Path To Putting Agency of 3D-Generation in Users’ Hands

Jun 17, 2025
headshot
UChicago CS News

Faculty Spotlight: Get to Know Kexin Pei

Jun 03, 2025
David Cash
UChicago CS News

David Cash Receives 2025 Quantrell Award for Undergraduate Teaching

Jun 02, 2025
future of AI panelists
Video

The Future of AI Panel: Alumni Weekend

May 30, 2025
Steven Song and Spencer Ellis
UChicago CS News

Bridging Medicine and Machine Learning: Predicting Skin Cancer in Resource-Limited Settings

May 28, 2025
UChicago CS News

Hands-On Vision: How a Wrist Camera Can Expand the World for All Users

May 23, 2025
students accepting best paper award
UChicago CS News

UChicago Students Received ACM EuroSys Best Paper for CacheBlend, a Game-Changer in AI Speed and Precision

May 22, 2025
Video

Can we authenticate human creativity?

May 19, 2025
robot interaction
In the News

More Control, Less Connection: How User Control Affects Robot Social Agency

May 16, 2025
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