scientific article; zbMATH DE number 5899292

DOI10.4086/TOC.2010.V006A006MaRDI QIDQ3002819zbMATH OpenOpenAlexFDO

Authors Navin Goyal, Michael Saks

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2010.v006a006

zbMATH Keywords

complexity theorydecision treesnoisy computation

Mathematics Subject Classification ID

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

Recommendations

• Rounds vs queries trade-off in noisy computation
• Towards better separation between deterministic and randomized query complexity
• Efficient computation for the noisy MAX
• Query-complexity amplification for random oracles
• Rounds in Communication Complexity Revisited
• Noisy optimization complexity under locality assumption
• scientific article; zbMATH DE number 953037
• Improvements of Winograd's result on computation in the presence of noise (Corresp.)

Cited in

(5)

• Rounds vs queries trade-off in noisy computation
• Lower bounds for noisy Boolean decision trees
• Computing with Noisy Information
• Skyline Computation with Noisy Comparisons
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)

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