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

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