An information statistics approach to data stream and communication complexity
From MaRDI portal
Publication:598248
DOI10.1016/j.jcss.2003.11.006zbMath1074.68022OpenAlexW2107917944MaRDI QIDQ598248
Ravi Kumar, D. Sivakumar, T. S. Jayram, Ziv Bar-Yossef
Publication date: 6 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.11.006
Related Items (97)
Sketching and Embedding are Equivalent for Norms ⋮ Communication with contextual uncertainty ⋮ Hellinger volume and number-on-the-forehead communication complexity ⋮ Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Taylor Polynomial Estimator for Estimating Frequency Moments ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ The communication complexity of the Hamming distance problem ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ The landscape of communication complexity classes ⋮ Interactive Information Complexity ⋮ Common information and unique disjointness ⋮ Superlinear lower bounds for multipass graph processing ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Towards a reverse Newman's theorem in interactive information complexity ⋮ Certifying equality with limited interaction ⋮ A discrepancy lower bound for information complexity ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Some lower bounds in dynamic networks with oblivious adversaries ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ The Hardness of Being Private ⋮ Communication complexity with small advantage ⋮ Distributed Testing of Distance-k Colorings ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Unnamed Item ⋮ The communication complexity of graphical games on grid graphs ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Secure sampling with sublinear communication ⋮ Optimal sampling from sliding windows ⋮ The communication complexity of functions with large outputs ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Arithmetic sketching ⋮ Unnamed Item ⋮ Forty years of frequent items ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Query-to-Communication Lifting for BPP ⋮ Estimating hybrid frequency moments of data streams ⋮ Unnamed Item ⋮ Extension Complexity of Independent Set Polytopes ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Streaming techniques and data aggregation in networks of tiny artefacts ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Fast Evaluation of Union-Intersection Expressions ⋮ Information complexity and applications. ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Information lower bounds via self-reducibility ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ New results for finding common neighborhoods in massive graphs in the data stream model ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Property testing lower bounds via communication complexity ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Partition arguments in multiparty communication complexity ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Applying approximate counting for computing the frequency moments of long data streams ⋮ Finding longest increasing and common subsequences in streaming data ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Sketching information divergences ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Information complexity of the AND function in the two-party and multi-party settings ⋮ Hierarchical sampling from sketches: Estimating functions over data streams ⋮ Upper and Lower Bounds on the Power of Advice ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Unnamed Item ⋮ A Note on Estimating Hybrid Frequency Moment of Data Streams ⋮ The Communication Complexity of Distributed epsilon-Approximations ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Unnamed Item ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ Exponential Separation of Communication and External Information ⋮ On Approximating Matrix Norms in Data Streams ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Unnamed Item ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity ⋮ On the streaming indistinguishability of a random permutation and a random function
Cites Work
- Unnamed Item
- Unnamed Item
- Communication complexity
- Asymptotics in statistics: some basic concepts
- On the distributional complexity of disjointness
- On randomized one-round communication complexity
- The space complexity of approximating the frequency moments
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Divergence measures based on the Shannon entropy
- Space lower bounds for distance approximation in the data stream model
- Approximate counting of inversions in a data stream
- Fast, small-space algorithms for approximate histogram maintenance
- Two applications of information complexity
- Graph-Based Algorithms for Boolean Function Manipulation
- The Probabilistic Communication Complexity of Set Intersection
- Privacy, additional information and communication
- A Parallel Repetition Theorem
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- Communication Complexity
This page was built for publication: An information statistics approach to data stream and communication complexity
