scientific article; zbMATH DE number 2081094

MaRDI QIDQ4474207zbMATH OpenFDO

Authors Manindra Agrawal

Publication date 4 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2245/22450058.htm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Hardness vs randomness
• Pseudorandom bits for constant depth circuits
• The complexity of constructing pseudorandom generators from hard functions
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Pseudo-random generators for all hardnesses

Cited in

(8)

• The complexity of satisfiability problems: Refining Schaefer's theorem
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Computational Randomness from Generalized Hardcore Sets
• Pseudorandom Generators in Propositional Proof Complexity
• Randomness buys depth for approximate counting
• Constant-error pseudorandomness proofs from hardness require majority
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Pseudorandom bits for constant depth circuits

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4474207)