An information statistics approach to data stream and communication complexity
From MaRDI portal
Recommendations
Cites work
- A Parallel Repetition Theorem
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- Approximate counting of inversions in a data stream
- Asymptotics in statistics: some basic concepts
- Communication complexity
- Communication Complexity
- Divergence measures based on the Shannon entropy
- Fast, small-space algorithms for approximate histogram maintenance
- Graph-Based Algorithms for Boolean Function Manipulation
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- On randomized one-round communication complexity
- On the distributional complexity of disjointness
- Privacy, additional information and communication
- Space lower bounds for distance approximation in the data stream model
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- The Probabilistic Communication Complexity of Set Intersection
- The space complexity of approximating the frequency moments
- Two applications of information complexity
Cited in
(only showing first 100 items - show all)- Sketching information divergences
- Hierarchical sampling from sketches: Estimating functions over data streams
- The landscape of communication complexity classes
- Information complexity and applications.
- Information-theoretic approximations of the nonnegative rank
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- 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
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- Some lower bounds in dynamic networks with oblivious adversaries
- Communication complexity with small advantage
- The communication complexity of graphical games on grid graphs
- Communication complexity of approximate maximum matching in the message-passing model
- Applying approximate counting for computing the frequency moments of long data streams
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- The unbounded-error communication complexity of symmetric functions
- Finding longest increasing and common subsequences in streaming data
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- New strong direct product results in communication complexity
- 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
- Robust lower bounds for communication and stream computation
- Fooling pairs in randomized communication complexity
- The hardness of being private
- Hellinger volume and number-on-the-forehead communication complexity
- Generalizations of the distributed Deutsch-Jozsa promise problem
- scientific article; zbMATH DE number 5899438 (Why is no real title available?)
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- The cost of fault tolerance in multi-party communication 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
- 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
- Sampling lower bounds via information theory
- A Note on Estimating Hybrid Frequency Moment of Data Streams
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Optimal sampling from sliding windows
- Estimating hybrid frequency moments of data streams
- Communication lower bounds via critical block sensitivity
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- Trading information complexity for error
- Sketching and embedding are equivalent for norms
- Interactive information complexity
- Extension complexity of independent set polytopes
- Simplified separation of information and communication
- Compressing interactive communication under product distributions
- Streaming techniques and data aggregation in networks of tiny artefacts
- The Communication Complexity of Distributed epsilon-Approximations
- A candidate for a strong separation of information and communication
- Tight bounds for single-pass streaming complexity of the set cover problem
- Exponential separation of communication and external information
- Continuous monitoring of _p norms in data streams
- Simultaneous multiparty communication protocols for composed functions
- Lower bounds for approximating graph parameters via communication complexity
- Information lower bounds via self-reducibility
- A Framework for Adversarially Robust Streaming Algorithms
- Real-valued embeddings and sketches for fast distance and similarity estimation
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- Distributed approximate maximum matching in the CONGEST model
- Robust communication-optimal distributed clustering algorithms
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- Optimal separation and strong direct sum for randomized query complexity
- Distributed Testing of Distance-k Colorings
- Query-to-communication lifting for BPP
- scientific article; zbMATH DE number 7250149 (Why is no real title available?)
- Sampling algorithms: lower bounds and applications
- On approximating matrix norms in data streams
- One-way multiparty communication lower bound for pointer jumping with applications
- Kolmogorov complexity and combinatorial methods in communication complexity
- An optimal lower bound for distinct elements in the message passing model
- Fast Evaluation of Union-Intersection Expressions
- Tight bounds for distributed functional monitoring
- Partition arguments in multiparty communication complexity
- Communication Lower Bounds Via the Chromatic Number
- Optimal space lower bounds for all frequency moments
- Communication lower bounds using directional derivatives
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
- Secure sampling with sublinear communication
- Separating k-player from t-player one-way communication, with applications to data streams
- The communication complexity of functions with large outputs
- Arithmetic sketching
- Forty years of frequent items
- The work of Mark Braverman
- Communication and information complexity
- Constructive separations and their consequences
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)
