On the Power of Threshold Measurements as Oracles

DOI10.1007/978-3-642-39074-6_3zbMATH Open1381.68078OpenAlexW2121678646MaRDI QIDQ5300906FDOQ5300906

Authors: José Félix Costa, Diogo Poças, John V. Tucker, Edwin Beggs 

Publication date: 28 June 2013

Published in: Unconventional Computation and Natural Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-39074-6_3

Recommendations

• Oracles that measure thresholds: the Turing machine and the broken balance
• Distance oracles beyond the Thorup-Zwick bound
• Limits on the usefulness of random oracles
• Limits on the Usefulness of Random Oracles
• Physical Aspects of Oracles for Randomness and Hadamard’s Conjecture
• Oracles and query lower bounds in generalised probabilistic theories
• On the random oracle hypothesis
• Limits of random oracles in secure computation (extended abstract)
• On the Power of Threshold Circuits with Small Weights

Mathematics Subject Classification ID

Cited In (9)

• The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\)
• On the Complexity of Measurement in Classical Physics
• Three forms of physical measurement and their computability
• A hierarchy for BPP//log\(\star\) based on counting calls to an oracle
• An analogue-digital Church-Turing thesis
• Oracles that measure thresholds: the Turing machine and the broken balance
• Uncertainty in time
• The Power of Machines That Control Experiments
• Computations with oracles that measure vanishing quantities

This page was built for publication: On the Power of Threshold Measurements as Oracles

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