On the Power of Threshold Measurements as Oracles

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

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

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 (6)

• The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\)
• On the Complexity of Measurement in Classical Physics
• An analogue-digital Church-Turing thesis
• The Power of Machines That Control Experiments
• THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY
• 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)