Date & Time:
January 3, 2023 3:30 pm – 4:30 pm
Kent 102, 1020 E 58th St, Chicago, IL, 60637
01/03/2023 03:30 PM 01/03/2023 04:30 PM America/Chicago Roei Tell (IAS) – A Free Lunch Theorem for De-randomization of Proof Systems, and Consequences Kent 102, 1020 E 58th St, Chicago, IL, 60637

In the first half of the talk, I’ll set up some background, by describing two recent directions in the study of de-randomization: A non-black-box algorithmic framework, which replaces the classical PRG-based paradigm; and free lunch results, which eliminate randomness with essentially no runtime overhead.

In the second half we’ll see one result along these directions: Under hardness assumptions, every doubly efficient proof system with constantly many rounds of interaction can be simulated by a deterministic NP-type verifier, with essentially no runtime overhead, such that no efficient adversary can mislead the deterministic verifier. Consequences include an NP-type verifier of this type for #SAT, running in time 2^{eps*n} for an arbitrarily small constant eps>0; and a complexity-theoretic analysis of the Fiat-Shamir heuristic in cryptography.

The talk is based on a joint work with Lijie Chen (UC Berkeley).


Roei Tell

Postdoctoral Researcher, Institute for Advanced Study and Center for Discreet Mathematics and Theoretical Computer Science

I’m a postdoc at IAS+DIMACS working in Theoretical Computer Science and Complexity Theory. Previously, I was a postdoc at MIT and completed my PhD at the Weizmann Institute of Science.

Related News & Events

Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
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