Finding the Median (Obliviously) with Bounded Space

DOI10.1007/978-3-662-47672-7_9zbMath1440.68346arXiv1505.00090OpenAlexW2121162169MaRDI QIDQ3448777

Mihai Pǎtraşcu, Vincent Liew, P. W. Beame

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.00090

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item

Cites Work

• Selection from read-only memory and sorting with minimum data movement
• Upper bounds for time-space trade-offs in sorting and selection
• Meanders and their applications in lower bounds arguments
• Selection and sorting with limited storage
• Time bounds for selection
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Time-space tradeoffs for branching programs
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• On lower bounds for read-\(k\)-times branching programs
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Communication Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding the Median (Obliviously) with Bounded Space