Superlinear lower bounds for multipass graph processing
From MaRDI portal
Publication:343847
DOI10.1007/s00453-016-0138-7zbMath1353.68084arXiv1212.6925MaRDI QIDQ343847
Krzysztof Onak, Venkatesan Guruswami
Publication date: 29 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.6925
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C57: Games on graphs (graph-theoretic aspects)
Related Items
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models, Pointer chasing via triangular discrimination, A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths, A simple augmentation method for matchings with applications to streaming algorithms, Depth First Search in the Semi-streaming Model, Unnamed Item, Superlinear lower bounds for multipass graph processing, Finding Articulation Points of Large Graphs in Linear Time, Maximum Matching in Turnstile Streams
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superlinear lower bounds for multipass graph processing
- A direct product theorem for two-party bounded-round public-coin communication complexity
- A discrepancy lower bound for information complexity
- An information statistics approach to data stream and communication complexity
- Communication complexity
- Lower bounds on communication complexity
- Private vs. common random bits in communication complexity
- Some bounds on multiparty communication complexity of pointer jumping
- Weighted matching in the semi-streaming model
- Bipartite matching in the semi-streaming model
- On graph problems in a semi-streaming model
- How to Compress Interactive Communication
- Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
- Estimating PageRank on graph streams
- Maximum Matching in Semi-streaming with Few Passes
- Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
- Interactive Information Complexity
- Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
- Graph Distances in the Data-Stream Model
- Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
- Rounds in Communication Complexity Revisited
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Information Equals Amortized Communication
- Better bounds for matchings in the streaming model
- The communication complexity of pointer chasing
