Buchumschlag

NP-hardness of p-adic linear regression

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Baker, Gregory D.
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity Number Theory 68Q17 F.2.2; F.1.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

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)

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

Quoridor is PSPACE-Complete
von: Drop, Marius, et al.
Veröffentlicht: (2026)

NP-hard problems are not in BQP
von: Czerwinski, Reiner
Veröffentlicht: (2023)

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
von: Emmerich, Michael T. M., et al.
Veröffentlicht: (2026)

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
von: Emmerich, Michael T. M., et al.
Veröffentlicht: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
von: Eua-anant, Pakapim, et al.
Veröffentlicht: (2025)

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

Hive is PSPACE-Hard
von: Andel, Daniël, et al.
Veröffentlicht: (2025)

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

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
von: Wulf, Lasse
Veröffentlicht: (2025)

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

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

Quantum algorithms through graph composition
von: Cornelissen, Arjan
Veröffentlicht: (2025)

Quantum walks through generalized graph composition
von: Cornelissen, Arjan
Veröffentlicht: (2025)

On Small-depth Frege Proofs for PHP
von: Håstad, Johan
Veröffentlicht: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
von: Levin, Leonid A.
Veröffentlicht: (2022)

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

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
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)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
von: Dorochko, Leonid, et al.
Veröffentlicht: (2026)

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

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
von: Böhnlein, Toni, et al.
Veröffentlicht: (2024)

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

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
von: Grochow, Joshua A., et al.
Veröffentlicht: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
von: Lobe, Elisabeth, et al.
Veröffentlicht: (2021)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
von: von Liechtenstein, Maximilian R. P.
Veröffentlicht: (2025)

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

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

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

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

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

Quantum Sabotage Complexity
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2021)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
von: Philip, Geevarghese, et al.
Veröffentlicht: (2026)

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