On data structures and asymmetric communication complexity
From MaRDI portal
Recommendations
Cites work
- A lower bound for finding predecessors in Yao's cell probe model
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 1306898 (Why is no real title available?)
- scientific article; zbMATH DE number 512871 (Why is no real title available?)
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Lower bounds for orthogonal range searching: I. The reporting case
- Lower bounds for union-split-find related problems on random access machines
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On the cell probe complexity of polynomial evaluation
- On the difficulty of range searching
- Partial-Match Retrieval Algorithms
- Rounds in Communication Complexity Revisited
- Should Tables Be Sorted?
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Surpassing the information theoretic bound with fusion trees
Cited in
(48)- Lower bounds for dynamic algebraic problems
- Optimal bounds for the predecessor problem and related problems
- 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
- Randomized OBDDs for the most significant bit of multiplication need exponential space
- Placing conditional disclosure of secrets in the communication complexity universe
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- Property-preserving hash functions for Hamming distance from standard assumptions
- The cell probe complexity of succinct data structures
- Lower bounds for predecessor searching in the cell probe model
- On realization of left and right products of rational functions
- Upper and lower bounds on the power of advice
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Efficient range searching for categorical and plain data
- Randomized OBDDs for the most significant bit of multiplication need exponential size
- Sparse recovery with partial support knowledge
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Certifying equality with limited interaction
- Sample complexity bounds on differentially private learning via communication complexity
- One-round multi-party communication complexity of distinguishing sums
- scientific article; zbMATH DE number 1263186 (Why is no real title available?)
- The NOF multiparty communication complexity of composed functions
- Tight bounds for the subspace sketch problem with applications
- The complexity of differential privacy
- Nearly Optimal Static Las Vegas Succinct Dictionary
- Placing conditional disclosure of secrets in the communication complexity universe
- Simulating random walks on graphs in the streaming model
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- Optimal lower bounds for matching and vertex cover in dynamic graph streams
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- The communication complexity of addition
- scientific article; zbMATH DE number 7164746 (Why is no real title available?)
- Simulation beats richness: new data-structure lower bounds
- A little advice can be very helpful
- Cell-probe lower bounds for the partial match problem
- Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
- Design of extended dense coding protocol strategy based on combinatorial optimization
- Predecessor on the Ultra-Wide Word RAM
- Pattern masking for dictionary matching: theory and practice
- Randomized communication and implicit graph representations
- (+1) vertex coloring in O(n) communication
- ( + 1) vertex coloring in O(n) communication
- Communication memento: memoryless communication complexity
- Pointer chasing with unlimited interaction
- Streaming algorithms for network design
- A general method for estimating correlated aggregates over a data stream
- A strong lower bound for approximate nearest neighbor searching
- Dynamic asymmetric communication
This page was built for publication: On data structures and asymmetric communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1273860)
