Buchumschlag

Generalisations of Matrix Partitions : Complexity and Obstructions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Barsukov, Alexey, Kanté, Mamadou Moustapha
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Computational Complexity 68Q15, 68Q17, 05B20 F.1.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
von: Susukita, Kosuke, et al.
Veröffentlicht: (2026)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
von: Huseynzade, Rafig
Veröffentlicht: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)

Completeness classes in algebraic complexity theory
von: Bürgisser, Peter
Veröffentlicht: (2024)

Meta Theorem for Hardness on FCP-Problem
von: Nagao, Atsuki, et al.
Veröffentlicht: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

Linear Matroid Intersection is in Catalytic Logspace
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Oracle Separations for RPH
von: Hamm, Thekla, et al.
Veröffentlicht: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
von: Göös, Mika, et al.
Veröffentlicht: (2025)

A Note on Avoid vs MCSP
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
von: Garcia, Baruch
Veröffentlicht: (2026)

Explicit separations between randomized and deterministic Number-on-Forehead communication
von: Kelley, Zander, et al.
Veröffentlicht: (2023)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
von: Lela, Marko
Veröffentlicht: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
von: Asimi, Kristina, et al.
Veröffentlicht: (2020)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
von: Shalunov, Yakov
Veröffentlicht: (2023)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
von: Tzameret, Iddo, et al.
Veröffentlicht: (2023)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
von: Ye, Lixi
Veröffentlicht: (2026)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
von: Hakoniemi, Tuomas, et al.
Veröffentlicht: (2024)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
von: Saffidine, Abdallah, et al.
Veröffentlicht: (2025)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
von: Abdullah, Duaa, et al.
Veröffentlicht: (2025)

I/O complexity and pebble games with partial computations
von: Sobczyk, Aleksandros
Veröffentlicht: (2024)

The Separation of $NP$ and $PSPACE$
von: Lin, Tianrong
Veröffentlicht: (2021)

Polynomial Identity Testing via Evaluation of Rational Functions
von: Hu, Ivan, et al.
Veröffentlicht: (2022)

Failure of the strong feasible disjunction property
von: Krajicek, Jan
Veröffentlicht: (2026)

The Serial Scaling Hypothesis
von: Liu, Yuxi, et al.
Veröffentlicht: (2025)

Complexities of Well-Quasi-Ordered Substructural Logics
von: Galatos, Nikolaos, et al.
Veröffentlicht: (2025)

Dichotomy for orderings?
von: Kun, Gábor, et al.
Veröffentlicht: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
von: Kumar, Mrinal, et al.
Veröffentlicht: (2018)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
von: Lin, Tianrong
Veröffentlicht: (2023)

The Solver's Paradox in Formal Problem Spaces
von: Rosko, Milan
Veröffentlicht: (2025)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)

On the computational complexity of Data Flow Analysis
von: Sood, Gaurav, et al.
Veröffentlicht: (2013)

NP-hardness of p-adic linear regression
von: Baker, Gregory D.
Veröffentlicht: (2026)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
von: Lela, Marko
Veröffentlicht: (2025)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
von: Edwards, Darren J.
Veröffentlicht: (2025)

Unifying lower bounds for algebraic machines, semantically
von: Seiller, Thomas, et al.
Veröffentlicht: (2018)

DAG Scheduling in the BSP Model
von: Papp, Pál András, et al.
Veröffentlicht: (2023)