On the Power of Threshold Measurements as Oracles

DOI10.1007/978-3-642-39074-6_3MaRDI QIDQ5300906zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Cited in

(9)

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