Separation Between Deterministic and Randomized Query Complexity
From MaRDI portal
Publication:5376437
DOI10.1137/17M1124115zbMath1396.68045MaRDI QIDQ5376437
Sagnik Mukhopadhyay, Swagato Sanyal, Jaikumar Radhakrishnan
Publication date: 18 September 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Unnamed Item
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Lower bounds on probabilistic linear decision trees
- On recognizing graph properties from adjacency matrices
- Probabilistic recurrence relations revisited
- Complexity measures and decision tree complexity: a survey.
- Improved bounds for the randomized decision tree Complexity of recursive majority
- CREW PRAM<scp>s</scp> and Decision Trees
- The Zero-Error Randomized Query Complexity of the Pointer Function
- Separations in Query Complexity Based on Pointer Functions
- Towards Better Separation between Deterministic and Randomized Query Complexity
- Separations in query complexity using cheat sheets
- Inequalities: theory of majorization and its applications
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Separation Between Deterministic and Randomized Query Complexity
