:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gama, Simone Ingrid Monteiro, Rodrigues, Rosiane de Freitas
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2512.16807
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Trading Determinism for Time: The k-Reach Problem
by: Bhadra, Ronak, et al.
Published: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
by: Bilò, Davide, et al.
Published: (2026)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
by: Dalirrooyfard, Mina, et al.
Published: (2025)

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

Towards a complexity-theoretic dichotomy for TQFT invariants
by: Bridges, Nicolas, et al.
Published: (2025)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

On Saxe's theorems about the complexity of the Distance Geometry Problem
by: Kupperschmitt, Maël, et al.
Published: (2025)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

High Rate Efficient Local List Decoding from HDX
by: Dikstein, Yotam, et al.
Published: (2026)

Computational aspects of the trace norm contraction coefficient
by: Delsol, Idris, et al.
Published: (2025)

On the complexity of Multipacking
by: Das, Sandip, et al.
Published: (2026)

The complexity of strong conflict-free vertex-connection $k$-colorability
by: Hsieh, Sun-Yuan, et al.
Published: (2024)

On Approximability of Satisfiable k-CSPs: V
by: Bhangale, Amey, et al.
Published: (2024)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

Asymmetric Number Partitioning with Splitting and Interval Targets
by: Bismuth, Samuel, et al.
Published: (2022)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
by: Kratochvíl, Jan, et al.
Published: (2020)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

Width Hierarchy for k-OBDD of Small Width
by: Khadiev, Kamil
Published: (2015)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
by: Doron, Dean, et al.
Published: (2024)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
by: Fang, Yuting, et al.
Published: (2024)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
by: Antonelli, Melissa, et al.
Published: (2026)

Advances in List Decoding of Polynomial Codes
by: Kumar, Mrinal, et al.
Published: (2026)

Payment Scheduling in the Interval Debt Model
by: Friedetzky, Tom, et al.
Published: (2024)