On Low End Obfuscation and Learning

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


Duration: 45:51
406 views
1

Gal Yehuda (Technion)
https://simons.berkeley.edu/talks/low-end-obfuscation-learning
Lower Bounds, Learning, and Average-Case Complexity

Abstract
Most recent works on cryptographic obfuscation focus on the high-end regime of obfuscating general circuits while guaranteeing computational indistinguishability between functionally equivalent circuits. Motivated by the goals of simplicity and efficiency, we initiate a systematic study of ``low-end'' obfuscation, focusing on simpler representation models and information-theoretic notions of security.



Other Videos By Simons Institute for the Theory of Computing


2023-03-21Random log(n)-CNF are Hard for Cutting Planes (Again)
2023-03-20Lower Bounds Against PC With Extension Variables
2023-03-17Strong Bounds for 3-Progressions
2023-03-15The Quantum Fourier Transform Has Small Entanglement | Quantum Colloquium
2023-03-07Writing Workshop with Science Communicator in Residence Adam Becker
2023-02-26What Do the Theory of Computing and the Movies Have in Common?
2023-02-18Unstructured Hardness to Average-Case Randomness
2023-02-18Learning with Distributional Inverters
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


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