Separation between deterministic and randomized query complexity

DOI10.1137/17M1124115MaRDI QIDQ5376437zbMATH OpenWikidataFDO

Authors Sagnik Mukhopadhyay, Swagato Sanyal, Jaikumar Radhakrishnan

Publication date 18 September 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17M1124115

zbMATH Keywords

query complexitymodels of computationrandomized decision treedeterministic decision tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Towards better separation between deterministic and randomized query complexity
• The Zero-Error Randomized Query Complexity of the Pointer Function

Cites work

• scientific article; zbMATH DE number 6789270 (Why is no real title available?)
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Concentration of Measure for the Analysis of Randomized Algorithms
• Improved bounds for the randomized decision tree complexity of recursive majority
• Inequalities: theory of majorization and its applications
• Lower bounds on probabilistic linear decision trees
• On recognizing graph properties from adjacency matrices
• Probabilistic recurrence relations revisited
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
• Separations in query complexity using cheat sheets
• The Zero-Error Randomized Query Complexity of the Pointer Function
• Towards better separation between deterministic and randomized query complexity

Cited in

(7)

• The 1-Versus-2 Queries Problem Revisited
• On the complexity of query result diversification
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Optimal separation in exact query complexities for Simon's problem
• On random oracle separations
• Towards better separation between deterministic and randomized query complexity
• Randomized versus deterministic decision tree size

This page was built for publication: Separation between deterministic and randomized query complexity

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