Copertina

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Ghosh, Prantar, Shah, Vihan
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

New Algorithms and Lower Bounds for Streaming Tournaments
di: Ghosh, Prantar, et al.
Pubblicazione: (2024)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
di: Shah, Vihan
Pubblicazione: (2026)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
di: Ding, Matthew, et al.
Pubblicazione: (2024)

A Lower Bound for Light Spanners in General Graphs
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Learning-augmented Maximum Independent Set
di: Braverman, Vladimir, et al.
Pubblicazione: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
di: Cervenjak, Philip, et al.
Pubblicazione: (2024)

A Tight Lower Bound for Cycle Detection in Grid Graphs
di: Au, Andrew
Pubblicazione: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
di: Li, Qian, et al.
Pubblicazione: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
di: Hwang, Samuel, et al.
Pubblicazione: (2024)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
di: Kothari, Pravesh, et al.
Pubblicazione: (2024)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
di: Singer, Noah G., et al.
Pubblicazione: (2026)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
di: Bishnu, Arijit, et al.
Pubblicazione: (2024)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
di: Braverman, Vladimir, et al.
Pubblicazione: (2024)

Streaming Maximal Matching with Bounded Deletions
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
di: Yoshida, Yuichi
Pubblicazione: (2026)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
di: Boneh, Itai, et al.
Pubblicazione: (2025)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
di: De, Rajat, et al.
Pubblicazione: (2023)

Lower Bounds on $0$-Extension with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2024)

Double Exponential Lower Bound for Telephone Broadcast
di: Tale, Prafullkumar
Pubblicazione: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
di: Jayaram, Rajesh, et al.
Pubblicazione: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
di: Doron-Arad, Ilan, et al.
Pubblicazione: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2026)

Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation
di: Lu, Shangqi, et al.
Pubblicazione: (2025)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
di: Funke, Daniel, et al.
Pubblicazione: (2024)

Improved Lower Bounds for Privacy under Continual Release
di: Aryanfard, Bardiya, et al.
Pubblicazione: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
di: Fleming, Noah, et al.
Pubblicazione: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
di: Huiberts, Sophie, et al.
Pubblicazione: (2022)

Lower Bounds on Tree Covers
di: Chen, Yu, et al.
Pubblicazione: (2025)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
di: Manea, Florin, et al.
Pubblicazione: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
di: Heineman, George T., et al.
Pubblicazione: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
di: Chitnis, Rajesh, et al.
Pubblicazione: (2024)

Tight Lower Bounds for Central String Queries in Compressed Space
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

Tight Static Lower Bounds for Non-Adaptive Data Structures
di: Persiano, Giuseppe, et al.
Pubblicazione: (2020)