scientific article; zbMATH DE number 7758324

DOI10.4230/lipics.approx/random.2020.22arXiv2007.03039MaRDI QIDQ6062143

Prantar Ghosh, Justin Thaler, Amit Chakrabarti

Publication date: 31 October 2023

Full work available at URL: https://arxiv.org/abs/2007.03039

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph algorithmsinteractive proofsdata streamsArthur-Merlin

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Improved Merlin-Arthur protocols for central problems in fine-grained complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• Streaming graph computations with a helpful advisor
• Streaming computations with a loquacious prover
• Counting Arbitrary Subgraphs in Data Streams
• Graph Distances in the Data-Stream Model
• Probabilistic checking of proofs
• Algebraic methods for interactive proof systems
• IP = PSPACE
• On Estimating Maximum Matching Size in Graph Streams
• Semi-Streaming Algorithms for Annotated Graph Streams
• Streaming Verification of Graph Properties.
• Annotations in Data Streams
• Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
• Approximate Maximum Matching in Random Streams
• Vertex Ordering Problems in Directed Graph Streams
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Arthur-Merlin Streaming Complexity
• Annotations for Sparse Data Streams
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Computing and Combinatorics
• Better bounds for matchings in the streaming model
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

This page was built for publication: