Superlinear lower bounds for multipass graph processing

DOI10.1007/s00453-016-0138-7zbMath1353.68084arXiv1212.6925OpenAlexW2310290370MaRDI 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

zbMATH Keywords

shortest pathinformation theorymaximum matchingcommunication complexitystreaming

Mathematics Subject Classification ID

Related Items (9)

Finding Articulation Points of Large Graphs in Linear Time ⋮ Maximum Matching in Turnstile Streams ⋮ Superlinear lower bounds for multipass graph processing ⋮ Unnamed Item ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Depth First Search in the Semi-streaming Model ⋮ 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

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

This page was built for publication: Superlinear lower bounds for multipass graph processing