Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
From MaRDI portal
Publication:3579215
DOI10.1145/509907.510006zbMath1192.68346OpenAlexW2156336752MaRDI QIDQ3579215
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.510006
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Finding the Median (Obliviously) with Bounded Space, Lifting query complexity to time-space complexity for two-way finite automata, Text indexing with errors, Quantum branching programs and space-bounded nonuniform quantum complexity, Cell-probe lower bounds for the partial match problem, A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs, Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle, Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs, A hierarchy result for read-once branching programs with restricted parity nondeterminism, Computing (and Life) Is All about Tradeoffs, On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs