On the decisional complexity of problems over the reals

DOI10.1006/inco.2000.3012zbMath1007.68076OpenAlexW2038714837MaRDI QIDQ1854429

Moni Naor, Sitvanit Ruah

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/71d674e0600452463ce49ffde9542e024b6acd1d

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Lower bounds on probabilistic linear decision trees
• On the complexity of computations under varying sets of primitives
• On randomized semi-algebraic test complexity
• Randomized complexity lower bound for arrangements and polyhedra
• A randomized algorithm for finding maximum with \(O((\log n)^2)\) polynomial tests
• A note on Rabin's width of a complete proof
• Simulating probabilistic by deterministic algebraic computation trees
• Proving simultaneous positivity of linear forms
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• On the Polyhedral Decision Problem
• Lower bounds for algebraic decision trees
• CREW PRAM<scp>s</scp> and Decision Trees
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Simple Constructions of Almost k-wise Independent Random Variables
• Computing with Noisy Information
• Class of constructive asymptotically good algebraic codes
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations