Lower Bounds, Learning, and Average-Case Complexity
2023-02-13..2023-02-17
Berkeley, United States
who it's for
complexity theorists, cryptographers, learning theorists, quantum computing researchers, theoretical machine learning researchers, algorithm designers
topics
time-bounded Kolmogorov complexity; minimum circuit size problem (MCSP/MKTP); meta-complexity approximation gaps; agnostic PAC learning from KT; replicability in randomized algorithms; NC0 pseudorandom generators; indistinguishability obfuscation and witness encryption; ACC0 lower bounds and derandomization; quantum learners implying circuit lower bounds; distributional inverters; succinct neural networks; heuristic PAC vs pseudorandom functions
| title | author | length |
|---|---|---|
| A Commentary on the Collision of Worlds | Rahul Santhanam | 53m |
A précis of the concrete claims: Allender’s 2001 survey promotes a variant K^T (capital T) that relates tightly to circuit complexity and to MCSP via a… | ||
| Allender's Conjecture and its Impacts on Meta-Complexity | Shuichi Hirahara | 51m |
Allender’s conjectures are shown false under plausible collapses: reductions to Kolmogorov-random strings would imply EXP^NP = NEXP, so the hoped… | ||
| NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach | Rahul Ilango | 45m |
Shows NP‑hardness gaps for concrete meta‑complexity problems: under subexponentially‑secure indistinguishability obfuscation/witness encryption the conditional… | ||
| Improved Learning from Time-bounded Kolmogorov Complexity | Halley Goldberg | 45m |
Assuming heuristics for time‑bounded Kolmogorov complexity (MKTP/KT) on average, the work gives concrete learners for P/poly that are agnostic PAC learning… | ||
| Journey with Eric Allender: From Turing Machines to Circuits, and Back | Michal Koucky | 37m |
Tracks historical reductions and concrete proofs: shows Valiant‑Vazirani isolation turning NP instances into ones with a single accepting path, recalls… | ||
| How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP) | Neekon Vafa | 23m |
Shows a concrete combinatorial scheme: split p pages into blocks of r/2, assign one friend to each pair-of-chapters construction (friend reads union of two… | ||
| The Mystery of the Missing String | Ryan Williams | 52m |
Equivalence between the simple missing string task and relativized exponential lower bounds: finding a string outside M strings of length N (with M ≈ 2^{εN})… | ||
| Extending Generalization Theory Towards Addressing Modern Challenges in Machine Learning | Shay Moran | 40m |
Main claim: any 0/1 infinite game that violates the Minimax equality contains arbitrarily large copies of Jewish poker, i.e. arbitrarily large triangular… | ||
| Replicability in Learning | Jessica Sorrell | 51m |
Defines rho‑replicable randomized algorithms that, with probability 1−rho, produce exactly the same output on two independent samples from the same… | ||
| Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms | Hanlin Ren | 47m |
Presents the first unconditional FP^NP algorithm for ACC^0-Avoid and also gives FP^NP procedures for ACC^0-Remote-Point and ACC^0-Partial-AvgHard with… | ||
| Quantum Learning Algorithms Imply Circuit Lower Bounds | Alex B. Grilo, Srinivasan Arunachalam, Tom Gur, Igor C. Oliveira, Aarthi Sundaram | 42m |
Shows a concrete implication: any quantum learner that beats the two trivial learners (full truth-table queries or the sampling-based 1/2 − 2^{-n/2} advantage)… | ||
| Learning Versus Pseudorandom Generators in Constant Parallel Time | Mikito Nanashima | 50m |
Proves an equivalence: existence of polynomial-stretch PRGs computable in NC0 (collections and single-generator parity-NC0 cases) is exactly captured by… | ||
| A Duality Between One-Way Functions and Average-Case Symmetry of Information | Zhenjian Lu | 40m |
Proves an equivalence: one-way functions do not exist (infinitely often) if and only if average-case symmetry of information for pK^poly holds, and similarly… | ||
| Quantum Meets Minimum Circuit Size Problem | Nai-Hui Chia | 44m |
Defines three quantum MCSPs (Boolean functions, unitaries, and states) and shows concrete complexity and reductions: MQCSP in QCMA, multi-output MQCSP is… | ||
| Learning Safe Action Models | Brendan Juba | 55m |
Proposes polynomial-time algorithms that output conservative precondition intersection (start with all literals, remove those violated) and learn effects by… | ||
| New Lower Bounds and Derandomization for ACC, and a... | Lijie Chen | 53m |
Proves concrete derandomization and lower-bound steps: shows MA_sub_ACC0 ⊆ i.o.NQP with quasi‑polynomial verification but polynomial‑length proofs, uses PCPs… | ||
| Succinct Neural Networks | Adam Tauman Kalai | 45m |
Proposes a DNN architecture that is succinct meaning a single constant-size neural network S is convolved and recurrently applied to simulate the tableau of… | ||
| New Approaches to Heuristic Pac-learning vs. PRFs | Ari Karchmer | 47m |
Proves that, under the nonexistence of PRFs, Naor–Reingold’s pseudorandom synthesizer reduction yields a concrete algorithmic consequence: most polynomial-size… | ||
| On the Average-case Complexity of the Nearest Boolean Vector to a Subspace | Andrej Bogdanov | 41m |
Most n-dimensional subspaces of R^m are Ω(√m)-far from {-1,1}^m and there is a non-deterministic interactive algorithm that certifies a random subspace is… | ||
| Average-case Complexity for Polynomials, and All That | Emanuele Viola | 01h 00m |
Survey of concrete advances and limits: proves an explicit counterexample to the CHLLZ conjecture by showing TRIBES DNF retains large local correlation after… | ||
| On Low End Obfuscation and Learning | Gal Yehuda | 46m |
Shows an exact characterization: a program class admits information‑theoretic (perfect) obfuscation exactly when it is whitebox learning–exactly learnable from… | ||
| Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity | Yanyi Liu | 46m |
Proves a precise equivalence: existence of (quasi‑polynomial or subexponential) one-way functions is iff mild average‑case hardness of MK^tP[polylog n] (or… | ||
| What (Doesn't) Make Learning Algorithms Generalize? | Roi Livni | 42m |
Shows that empirical risk minimization needs dimension-dependent samples (at least log D) while adding regularization yields 1/ε^2 sample complexity for… | ||
| Learning with Distributional Inverters | Marco Carmosino | 38m |
A three-step reduction turns learning a concept over a samplable distribution D into learning over the uniform distribution by defining g(z) = f(sampler(z))… | ||
| Unstructured Hardness to Average-Case Randomness | Roei Tell | 48m |
Proves that polynomial-time average-case derandomization of RP follows from concrete, weaker hardness hypotheses: e.g., any logspace-uniform family of circuits… | ||
| nothing matches | ||