An information statistics approach to data stream and communication complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- 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
- 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)- The hardness of being private
- Communication lower bounds via critical block sensitivity
- Relative discrepancy does not separate information and communication complexity
- Lower bounds on information complexity via zero-communication protocols and applications
- New results for finding common neighborhoods in massive graphs in the data stream model
- Communication complexity with small advantage
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Information-theoretic approximations of the nonnegative rank
- Trading information complexity for error
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- One-way multiparty communication lower bound for pointer jumping with applications
- Kolmogorov complexity and combinatorial methods in communication complexity
- Trading information complexity for error. II: The case of a large error and the external information complexity
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- Information complexity and applications.
- The communication complexity of the Hamming distance problem
- Constructive separations and their consequences
- Communication complexity of approximate maximum matching in the message-passing model
- Partition arguments in multiparty communication complexity
- Robust lower bounds for communication and stream computation
- Distributed Testing of Distance-k Colorings
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- A Note on Estimating Hybrid Frequency Moment of Data Streams
- Optimal sampling from sliding windows
- Generalizations of the distributed Deutsch-Jozsa promise problem
- A Framework for Adversarially Robust Streaming Algorithms
- The communication complexity of functions with large outputs
- 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
- Estimating hybrid frequency moments of data streams
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- The unbounded-error communication complexity of symmetric functions
- Hellinger volume and number-on-the-forehead communication complexity
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Interactive Information Complexity
- Common information and unique disjointness
- scientific article; zbMATH DE number 7561590 (Why is no real title available?)
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- scientific article; zbMATH DE number 5899438 (Why is no real title available?)
- Hierarchical sampling from sketches: Estimating functions over data streams
- Fast Evaluation of Union-Intersection Expressions
- Sampling algorithms: lower bounds and applications
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Sketching information divergences
- Exponential separation of communication and external information
- On approximating matrix norms in data streams
- Fooling pairs in randomized communication complexity
- Secure sampling with sublinear communication
- Property testing lower bounds via communication complexity
- The landscape of communication complexity classes
- The effect of range and bandwidth on the round complexity in the congested clique model
- Arithmetic sketching
- Sketching and embedding are equivalent for norms
- Robust communication-optimal distributed clustering algorithms
- Choosing, agreeing, and eliminating in communication complexity
- Interactive information complexity
- Tight bounds for distributed functional monitoring
- Query-to-communication lifting for BPP
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- Streaming techniques and data aggregation in networks of tiny artefacts
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- Compressing interactive communication under product distributions
- Simplified separation of information and communication
- Applying approximate counting for computing the frequency moments of long data streams
- Upper and lower bounds on the power of advice
- scientific article; zbMATH DE number 7250149 (Why is no real title available?)
- Lower bounds for number-in-hand multiparty communication complexity, made easy
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- Forty years of frequent items
- The Communication Complexity of Distributed epsilon-Approximations
- Lower bounds for approximating graph parameters via communication complexity
- 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
- Communication and information complexity
- The work of Mark Braverman
- Some lower bounds in dynamic networks with oblivious adversaries
- Communication Lower Bounds Via the Chromatic Number
- Information lower bounds via self-reducibility
- Communication lower bounds using directional derivatives
- A candidate for a strong separation of information and communication
- Taylor polynomial estimator for estimating frequency moments
- Extension complexity of independent set polytopes
- Continuous monitoring of \(\ell_p\) norms in data streams
- 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 communication complexity of graphical games on grid graphs
- Simultaneous multiparty communication protocols for composed functions
- The cost of fault tolerance in multi-party communication complexity
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Optimal separation and strong direct sum for randomized query complexity
- Distributed approximate maximum matching in the CONGEST model
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
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)
