scientific article; zbMATH DE number 2019636

MaRDI QIDQ4440439zbMATH OpenFDO

Authors Oded Goldreich, A. Wigderson

Publication date 17 December 2003

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Can every randomized algorithm be derandomized?
• On derandomizing algorithms that err extremely rarely
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Derandomizing isolation in space-bounded settings
• Pseudorandom Generators and Typically-Correct Derandomization

Cited in

(16)

• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• On the average-case complexity of property testing
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• On uniformity and circuit lower bounds
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Typically-correct derandomization for small time and space
• Worst-Case to Average-Case Reductions for Subclasses of P
• Derandomizing isolation in space-bounded settings
• Derandomizing isolation in space-bounded settings
• (Nondeterministic) hardness vs. non-malleability
• Nearly optimal pseudorandomness from hardness
• Non-malleable codes with optimal rate for poly-size circuits
• Uniform black-box separations via non-malleable extractors
• Communication complexity vs randomness complexity in interactive proofs
• Asymptotic spectra: theory, applications, and extensions

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 Q4440439)