Learning Versus Pseudorandom Generators in Constant Parallel Time

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


Duration: 49:45
434 views
4

Mikito Nanashima (Tokyo Institute of Technology)
https://simons.berkeley.edu/talks/mikito-nanashima-tokyo-institute-technology-2023-02-15
Lower Bounds, Learning, and Average-Case Complexity

Abstract
A polynomial-stretch pseudorandom generator (PPRG) in NC0 is one of the most important cryptographic primitives. In the talk, we present a new learning-theoretic characterization for PPRGs in NC0 and related classes by the average-case hardness of learning for well-studied classes in parameterized settings.



Other Videos By Simons Institute for the Theory of Computing


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
2023-02-14Allender's Conjecture and its Impacts on Meta-Complexity


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