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)

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