On the complexity of worst case and expected time in a circuit

DOI10.1007/3-540-60922-9_25MaRDI QIDQ4593940zbMATH OpenOpenAlexFDO

Authors Andreas Jakoby, Christian Schindelhauer

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_25

zbMATH Keywords

computational complexityaverage-case analysisworst caseexpected timetheory of parallel and distributed computationtimed circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Malign distributions for average case circuit complexity.
• Circuit complexity: from the worst case to the average case
• Malign distributions for average case circuit complexity
• Average circuit depth and average communication complexity
• The delay of circuits whose inputs have specified arrival times

Cited in

(5)

• Malign distributions for average case circuit complexity.
• Malign distributions for average case circuit complexity
• On the complexity of designing optimal branch-and-combine clock networks
• On the complexity of hazard-free circuits
• Circuit complexity: from the worst case to the average case

This page was built for publication: On the complexity of worst case and expected time in a circuit

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