Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

DOI10.1145/509907.510006zbMath1192.68346OpenAlexW2156336752MaRDI QIDQ3579215

Erik Vee, P. W. Beame

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

Mathematics Subject Classification ID

Related Items (11)

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

This page was built for publication: Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems