Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.09702 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)
by: Nagao, Atsuki, et al.
Published: (2025)
A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)
by: Hirsch, Edward A., et al.
Published: (2025)
Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)
by: Hirsch, Edward A., et al.
Published: (2025)
Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)
by: Agarwala, Aryan, et al.
Published: (2025)
Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)
by: Hamm, Thekla, et al.
Published: (2025)
Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)
by: Göös, Mika, et al.
Published: (2025)
Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)
by: Edwards, Darren J.
Published: (2025)
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)
by: Tzameret, Iddo, et al.
Published: (2023)
Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)
by: Barsukov, Alexey, et al.
Published: (2021)
Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)
by: Czerwinski, Reiner
Published: (2021)
Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)
by: Shalunov, Yakov
Published: (2023)
The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)
by: Liu, Yuxi, et al.
Published: (2025)
An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)
by: Lela, Marko
Published: (2025)
Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)
by: Krajicek, Jan
Published: (2026)
Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)
by: Susukita, Kosuke, et al.
Published: (2026)
NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)
by: Czerwinski, Reiner
Published: (2023)
IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)
by: Lela, Marko
Published: (2025)
Dichotomy for orderings?
by: Kun, Gábor, et al.
Published: (2025)
by: Kun, Gábor, et al.
Published: (2025)
Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)
by: Saffidine, Abdallah, et al.
Published: (2025)
Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)
by: Huseynzade, Rafig
Published: (2025)
CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)
by: Bodnar, Levente
Published: (2024)
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)
by: Kumar, Mrinal, et al.
Published: (2018)
Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)
by: Asimi, Kristina, et al.
Published: (2020)
Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)
by: Kelley, Zander, et al.
Published: (2023)
Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)
by: Rossman, Benjamin
Published: (2024)
The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)
by: Rosko, Milan
Published: (2025)
Fixed-parameter debordering of Waring rank
by: Dutta, Pranjal, et al.
Published: (2024)
by: Dutta, Pranjal, et al.
Published: (2024)
Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)
by: Cornelissen, Arjan, et al.
Published: (2024)
A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)
by: Latkin, Ivan V.
Published: (2023)
The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)
by: Czerwinski, Reiner
Published: (2024)
Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)
by: Bürgisser, Peter
Published: (2024)
On the computational complexity of Data Flow Analysis
by: Sood, Gaurav, et al.
Published: (2013)
by: Sood, Gaurav, et al.
Published: (2013)
Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)
by: Schewe, Klaus-Dieter
Published: (2020)
Stochastic well-structured transition systems
by: Aspnes, James
Published: (2025)
by: Aspnes, James
Published: (2025)
NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)
by: Baker, Gregory D.
Published: (2026)
Quantum algorithms through graph composition
by: Cornelissen, Arjan
Published: (2025)
by: Cornelissen, Arjan
Published: (2025)
Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)
by: Cornelissen, Arjan
Published: (2025)
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)
by: Hakoniemi, Tuomas, et al.
Published: (2024)
Algebraic metacomplexity and representation theory
by: Berg, Maxim van den, et al.
Published: (2024)
by: Berg, Maxim van den, et al.
Published: (2024)
Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)
by: Bläser, Markus, et al.
Published: (2025)