Pseudo-Derandomizing Learning and Approximation

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.55OpenAlexW2888859905MaRDI QIDQ5009554

Rahul Santhanam, Oliveira Igor Carboni

Publication date: 4 August 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.55

zbMATH Keywords

learningapproximationderandomizationBoolean circuits

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness buys depth for approximate counting
• Hardness vs randomness
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Constant depth circuits, Fourier transform, and learnability
• Number-theoretic constructions of efficient pseudo-random functions
• An Average-Case Depth Hierarchy Theorem for Boolean Circuits
• Pseudodeterministic constructions in subexponential time
• Analysis of Boolean Functions
• On Learning, Lower Bounds and (un)Keeping Promises
• Natural proofs
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Pseudo-random generators for all hardnesses

This page was built for publication: Pseudo-Derandomizing Learning and Approximation