Pseudo-derandomizing learning and approximation
From MaRDI portal
Publication:5009554
DOI10.4230/LIPICS.APPROX-RANDOM.2018.55OpenAlexW2888859905MaRDI QIDQ5009554FDOQ5009554
Authors: Oliveira Igor Carboni, Rahul Santhanam 
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.55
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
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Hardness vs randomness
- Analysis of Boolean Functions
- Constant depth circuits, Fourier transform, and learnability
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Title not available (Why is that?)
- Natural proofs
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Number-theoretic constructions of efficient pseudo-random functions
- Pseudo-random generators for all hardnesses
- Randomness buys depth for approximate counting
- Improving exhaustive search implies superpolynomial lower bounds
- Title not available (Why is that?)
- On learning, lower bounds and (un)keeping promises
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- Title not available (Why is that?)
- An average-case depth hierarchy theorem for Boolean circuits
- Pseudodeterministic constructions in subexponential time
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
Cited In (1)
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)
