Pseudo-derandomizing learning and approximation
From MaRDI portal
Publication:5009554
Recommendations
- On Pseudodeterministic Approximation Algorithms.
- Pseudorandomness for approximate counting and sampling
- On the possibilities and limitations of pseudodeterministic algorithms
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
- On learning, lower bounds and (un)keeping promises
Cites work
- scientific article; zbMATH DE number 1104345 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 795584 (Why is no real title available?)
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- An average-case depth hierarchy theorem for Boolean circuits
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Analysis of Boolean Functions
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
- Constant depth circuits, Fourier transform, and learnability
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Hardness vs randomness
- Improving exhaustive search implies superpolynomial lower bounds
- Natural proofs
- Number-theoretic constructions of efficient pseudo-random functions
- On learning, lower bounds and (un)keeping promises
- Pseudo-random generators for all hardnesses
- Pseudodeterministic constructions in subexponential time
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- Randomness buys depth for approximate counting
This page was built for publication: Pseudo-derandomizing learning and approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009554)
