Tight Quantum Time-Space Tradeoffs for Function Inversion
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 26-minute IEEE conference talk on quantum computing that delves into tight quantum time-space tradeoffs for function inversion. Learn about classical time-space tradeoffs, circuit complexity, and a generic framework for approaching these problems. Discover the direct product problem, multi-instance gain, and upper and lower bounds. Gain insights into the overall product, multi-instance game, and open questions in the field. Presented by researchers from Academia Sinica, New York University Shanghai, Princeton University, NTT Research, and Boston University, this talk offers a comprehensive overview of cutting-edge research in quantum computing and function inversion.
Syllabus
Introduction
Classical TimeSpace Tradeoffs
Circuit Complexity
Background
Generic Framework
Open Questions
Proof Overview
Direct Product Problem
Multiinstance Gain
Upper Bound
Lower Bound
lemma informally
Overall product
Multiinstance game
Conclusion
Open Question
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube