Malign distributions for average case circuit complexity.

DOI10.1006/inco.1998.2776zbMath1045.68567OpenAlexW1963823861MaRDI QIDQ1854270

Christian Schindelhauer, Andreas Jakoby, K. Ruediger Reischuk

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2776

zbMATH Keywords

Turing machinesrandom access machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average case completeness
• On the theory of average case complexity
• Average case complexity under the universal distribution equals worst- case complexity
• An average complexity measure that yields tight hierarchies
• Circuit complexity
• Average Case Complete Problems
• On the complexity of worst case and expected time in a circuit
• The average case complexity of the parallel prefix problem
• Complete problems with L-samplable distributions

This page was built for publication: Malign distributions for average case circuit complexity.