An information statistics approach to data stream and communication complexity
From MaRDI portal
Publication:598248
DOI10.1016/J.JCSS.2003.11.006zbMATH Open1074.68022OpenAlexW2107917944MaRDI QIDQ598248FDOQ598248
Authors: Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- Graph-Based Algorithms for Boolean Function Manipulation
- The space complexity of approximating the frequency moments
- Asymptotics in statistics: some basic concepts
- Title not available (Why is that?)
- Divergence measures based on the Shannon entropy
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Space lower bounds for distance approximation in the data stream model
- Two applications of information complexity
- A Parallel Repetition Theorem
- On randomized one-round communication complexity
- Communication complexity
- On the distributional complexity of disjointness
- Privacy, additional information and communication
- Fast, small-space algorithms for approximate histogram maintenance
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- Approximate counting of inversions in a data stream
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
Cited In (only showing first 100 items - show all)
- Trading information complexity for error
- New results for finding common neighborhoods in massive graphs in the data stream model
- Information-theoretic approximations of the nonnegative rank
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Trading information complexity for error. II: The case of a large error and the external information complexity
- One-way multiparty communication lower bound for pointer jumping with applications
- Kolmogorov complexity and combinatorial methods in communication complexity
- Information complexity and applications.
- The communication complexity of the Hamming distance problem
- Communication complexity of approximate maximum matching in the message-passing model
- Title not available (Why is that?)
- Partition arguments in multiparty communication complexity
- A Framework for Adversarially Robust Streaming Algorithms
- Generalizations of the distributed Deutsch-Jozsa promise problem
- Optimal sampling from sliding windows
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- New strong direct product results in communication complexity
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
- Estimating hybrid frequency moments of data streams
- The unbounded-error communication complexity of symmetric functions
- Hellinger volume and number-on-the-forehead communication complexity
- Interactive Information Complexity
- Common information and unique disjointness
- Fast Evaluation of Union-Intersection Expressions
- Sampling algorithms: lower bounds and applications
- Title not available (Why is that?)
- Hierarchical sampling from sketches: Estimating functions over data streams
- Secure sampling with sublinear communication
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Sketching information divergences
- The landscape of communication complexity classes
- Property testing lower bounds via communication complexity
- Sketching and embedding are equivalent for norms
- Tight bounds for distributed functional monitoring
- Query-to-communication lifting for BPP
- Choosing, agreeing, and eliminating in communication complexity
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- Title not available (Why is that?)
- Streaming techniques and data aggregation in networks of tiny artefacts
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- The Communication Complexity of Distributed epsilon-Approximations
- Optimal space lower bounds for all frequency moments
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Certifying equality with limited interaction
- Superlinear lower bounds for multipass graph processing
- Towards a reverse Newman's theorem in interactive information complexity
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Some lower bounds in dynamic networks with oblivious adversaries
- Information lower bounds via self-reducibility
- Communication lower bounds using directional derivatives
- Extension complexity of independent set polytopes
- Sampling lower bounds via information theory
- Tight bounds for single-pass streaming complexity of the set cover problem
- An optimal lower bound for distinct elements in the message passing model
- The cost of fault tolerance in multi-party communication complexity
- Optimal separation and strong direct sum for randomized query complexity
- Real-valued embeddings and sketches for fast distance and similarity estimation
- The multiparty communication complexity of set disjointness
- Finding longest increasing and common subsequences in streaming data
- Communication lower bounds via critical block sensitivity
- The hardness of being private
- Relative discrepancy does not separate information and communication complexity
- Lower bounds on information complexity via zero-communication protocols and applications
- On the streaming indistinguishability of a random permutation and a random function
- Communication complexity with small advantage
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- Constructive separations and their consequences
- Distributed Testing of Distance-k Colorings
- Robust lower bounds for communication and stream computation
- A Note on Estimating Hybrid Frequency Moment of Data Streams
- The communication complexity of functions with large outputs
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Title not available (Why is that?)
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- On approximating matrix norms in data streams
- Exponential separation of communication and external information
- Fooling pairs in randomized communication complexity
- Arithmetic sketching
- The effect of range and bandwidth on the round complexity in the congested clique model
- Robust communication-optimal distributed clustering algorithms
- Interactive information complexity
- Compressing interactive communication under product distributions
- Simplified separation of information and communication
- Upper and lower bounds on the power of advice
- Applying approximate counting for computing the frequency moments of long data streams
- Title not available (Why is that?)
- Forty years of frequent items
- Lower bounds for approximating graph parameters via communication complexity
- Communication and information complexity
- The work of Mark Braverman
- Communication Lower Bounds Via the Chromatic Number
- A candidate for a strong separation of information and communication
- Taylor polynomial estimator for estimating frequency moments
- Continuous monitoring of \(\ell_p\) norms in data streams
- Simultaneous multiparty communication protocols for composed functions
- The communication complexity of graphical games on grid graphs
This page was built for publication: An information statistics approach to data stream and communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598248)
