Optimal communication complexity of chained index

DOI10.4230/LIPICS.ITCS.2025.89MaRDI QIDQ7296737zbMATH OpenFDO

Authors Janani Sundaresan

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.89

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• A property of quantum relative entropy with an application to privacy in quantum communication
• Communication Complexity
• Communication Complexity
• Elements of Information Theory
• Graph Distances in the Data-Stream Model
• scientific article; zbMATH DE number 1263236 (Why is no real title available?)
• scientific article; zbMATH DE number 7829323 (Why is no real title available?)
• Independent sets in vertex-arrival streams
• Information cost tradeoffs for augmented index and streaming language recognition
• Interval selection in data streams: weighted intervals and the insertion-deletion setting
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Multi-pass graph streaming lower bounds for cycle counting, MAX-CUT, matching size, and other problems
• Numerical linear algebra in the streaming model
• On data structures and asymmetric communication complexity
• On streaming algorithms for geometric independent set and clique
• On the exact space complexity of sketching and streaming small norms
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Some bounds on multiparty communication complexity of pointer jumping
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• Streaming and communication complexity of clique approximation
• Streaming Lower Bounds for Approximating MAX-CUT
• Sublinear algorithms for ( + 1) vertex coloring
• Submodular maximization subject to matroid intersection on the fly
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Tight bounds for single-pass streaming complexity of the set cover problem
• Tight lower bounds for the distinct elements problem

Cited in

(1)

• A min-entropy approach to multi-party communication lower bounds

This page was built for publication: Optimal communication complexity of chained index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296737)