Malign distributions for average case circuit complexity

DOI10.1007/3-540-59042-0_111MaRDI QIDQ4596659zbMATH OpenOpenAlexFDO

Authors Andreas Jakoby, Christian Schindelhauer, Rüdiger Reischuk

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_111

zbMATH Keywords

average-case complexitycircuit complexitydelaydistribution

Mathematics Subject Classification ID

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
• Complexity of distributions and average-case hardness
• On the complexity of worst case and expected time in a circuit
• Average case complexity, revisited
• Computational complexity of various Mal'cev conditions
• Average circuit depth and average communication complexity
• On the theory of average case complexity
• Average case complexity under the universal distribution equals worst- case complexity
• The complexity of distributions

Cited in

(9)

• Improving the average delay of sorting
• Transformations that preserve malignness of universal distributions
• Malign distributions for average case circuit complexity.
• Circuit complexity: from the worst case to the average case
• The Complexity of Malign Measures
• On the complexity of worst case and expected time in a circuit
• The average case complexity of the parallel prefix problem
• Transformations that preserve malignness of universal distributions
• Average circuit depth and average communication 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 Q4596659)