scientific article; zbMATH DE number 7650137

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.70MaRDI QIDQ5875530

Amit Chakrabarti, Prantar Ghosh

Publication date: 3 February 2023

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superlinear lower bounds for multipass graph processing
• 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
• Annotations for Sparse Data Streams
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Better bounds for matchings in the streaming model