A Duality Between One-Way Functions and Average-Case Symmetry of Information

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=WmKG36bpKZY


Category:
Guide
Duration: 39:36
493 views
6

Zhenjian Lu (University of Oxford)
https://simons.berkeley.edu/talks/duality-between-one-way-functions-average-case-symmetry-information
Lower Bounds, Learning, and Average-Case Complexity



Other Videos By Simons Institute for the Theory of Computing


2023-02-18What (Doesn't) Make Learning Algorithms Generalize?
2023-02-17Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
2023-02-17On Low End Obfuscation and Learning
2023-02-17Average-case Complexity for Polynomials, and All That
2023-02-17On the Average-case Complexity of the Nearest Boolean Vector to a Subspace
2023-02-17New Approaches to Heuristic Pac-learning vs. PRFs
2023-02-16Succinct Neural Networks
2023-02-16New Lower Bounds and Derandomization for ACC, and a...
2023-02-16Learning Safe Action Models
2023-02-16Quantum Meets Minimum Circuit Size Problem
2023-02-16A Duality Between One-Way Functions and Average-Case Symmetry of Information
2023-02-15Learning Versus Pseudorandom Generators in Constant Parallel Time
2023-02-15Quantum Learning Algorithms Imply Circuit Lower Bounds
2023-02-15Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
2023-02-15Replicability in Learning
2023-02-15Extending Generalization Theory Towards Addressing Modern Challenges in Machine Learning
2023-02-14The Mystery of the Missing String
2023-02-14How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
2023-02-14Journey with Eric Allender: From Turing Machines to Circuits, and Back
2023-02-14Improved Learning from Time-bounded Kolmogorov Complexity
2023-02-14NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Lower Bounds Learning and Average-Case Complexity
Zhenjian Lu