On data structures and asymmetric communication complexity
From MaRDI portal
Publication:1273860
DOI10.1006/jcss.1998.1577zbMath0920.68042OpenAlexW2165461157MaRDI QIDQ1273860
Avi Wigderson, Shmuel Safra, Noam Nisan, Peter Bro Miltersen
Publication date: 6 January 1999
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1998.1577
Related Items (35)
A strong lower bound for approximate nearest neighbor searching ⋮ The cell probe complexity of succinct data structures ⋮ Sample Complexity Bounds on Differentially Private Learning via Communication Complexity ⋮ Unnamed Item ⋮ Certifying equality with limited interaction ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Property-preserving hash functions for Hamming distance from standard assumptions ⋮ Efficient range searching for categorical and plain data ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ One-round multi-party communication complexity of distinguishing sums ⋮ Design of extended dense coding protocol strategy based on combinatorial optimization ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ On realization of left and right products of rational functions ⋮ The NOF multiparty communication complexity of composed functions ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ The communication complexity of addition ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cell-probe lower bounds for the partial match problem ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ A general method for estimating correlated aggregates over a data stream ⋮ Sparse Recovery with Partial Support Knowledge ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Unnamed Item ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Tight Bounds for the Subspace Sketch Problem with Applications ⋮ Lower bounds for dynamic algebraic problems ⋮ The Complexity of Differential Privacy ⋮ Optimal bounds for the predecessor problem and related problems
Cites Work
- On the cell probe complexity of polynomial evaluation
- A lower bound for finding predecessors in Yao's cell probe model
- Surpassing the information theoretic bound with fusion trees
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Lower bounds for union-split-find related problems on random access machines
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Lower bounds for orthogonal range searching: I. The reporting case
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Should Tables Be Sorted?
- Rounds in Communication Complexity Revisited
- Partial-Match Retrieval Algorithms
- On the difficulty of range searching
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On data structures and asymmetric communication complexity
