Buchumschlag

Lower Bounds for Non-adaptive Local Computation Algorithms

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Azarmehr, Amir, Behnezhad, Soheil, Ghafari, Alma, Sudan, Madhu
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Markov Chains with Rewinding
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Stochastic Matching via In-n-Out Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Half-Approximating Maximum Dicut in the Streaming Setting
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Efficient Algorithms and New Characterizations for CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
von: Funke, Daniel, et al.
Veröffentlicht: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Tight Static Lower Bounds for Non-Adaptive Data Structures
von: Persiano, Giuseppe, et al.
Veröffentlicht: (2020)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
von: Hwang, Samuel, et al.
Veröffentlicht: (2024)

Quality control in sublinear time: a case study via random graphs
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2025)

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
von: Shiran, Maryam
Veröffentlicht: (2025)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
von: Atalig, Sunny, et al.
Veröffentlicht: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
von: Jin, Billy, et al.
Veröffentlicht: (2023)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
von: Shah, Vihan
Veröffentlicht: (2026)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
von: Croquevielle, Luis Alberto, et al.
Veröffentlicht: (2026)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
von: De, Rajat, et al.
Veröffentlicht: (2023)