Malign distributions for average case circuit complexity.

DOI10.1006/INCO.1998.2776MaRDI QIDQ1854270zbMATH OpenOpenAlexFDO

Authors Christian Schindelhauer, Andreas Jakoby, Rüdiger 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)

Recommendations

• Malign distributions for average case circuit complexity
• Circuit complexity: from the worst case to the average case
• On the complexity of worst case and expected time in a circuit
• Average circuit depth and average communication complexity
• Average case complexity for finite Boolean functions

Cites work

• scientific article; zbMATH DE number 3646783 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3655870 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• An average complexity measure that yields tight hierarchies
• Average Case Complete Problems
• Average case completeness
• Average case complexity under the universal distribution equals worst- case complexity
• Circuit complexity: from the worst case to the average case
• Complete problems with L-samplable distributions
• On the complexity of worst case and expected time in a circuit
• On the theory of average case complexity
• The average case complexity of the parallel prefix problem

Cited in

(9)

• Improving the average delay of sorting
• The Complexity of Malign Measures
• Improving the Average Delay of Sorting
• Transformations that preserve malignness of universal distributions
• On the depth of randomly generated circuits
• Circuit complexity: from the worst case to the average case
• Average circuit depth and average communication complexity
• On the complexity of worst case and expected time in a circuit
• Malign distributions for average case circuit complexity

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

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