Cover Image

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yoshida, Yuichi
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Tolerant Testing for Unique Games
by: Yoshida, Yuichi
Published: (2026)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
by: Cheng, Yu, et al.
Published: (2024)

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

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

Solving Hypergraph Laplacian Systems in Almost-Linear Time
by: Yoshida, Yuichi
Published: (2026)

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

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

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

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

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

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

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

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
by: Hu, Ivan, et al.
Published: (2022)

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

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

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

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

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

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

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

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

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

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

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

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

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

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
by: Doron-Arad, Ilan, et al.
Published: (2023)

Equivalence Testing: The Power of Bounded Adaptivity
by: Chakraborty, Diptarka, et al.
Published: (2024)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Lipschitz Continuous Algorithms for Covering Problems
by: Kumabe, Soh, et al.
Published: (2023)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
by: Ghosh, Prantar, et al.
Published: (2024)