Copertina

Universal NP-Hardness of Clustering under General Utilities

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Majumdar, Angshul
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Artificial Intelligence
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
di: Majumdar, Angshul
Pubblicazione: (2026)

Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard
di: Majumdar, Angshul
Pubblicazione: (2026)

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
di: Majumdar, Angshul
Pubblicazione: (2026)

Affine Rank Minimization is ER Complete
di: Majumdar, Angshul
Pubblicazione: (2026)

Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete
di: Majumdar, Angshul
Pubblicazione: (2026)

Sorting by Strip Swaps is NP-Hard
di: Roy, Swapnoneel, et al.
Pubblicazione: (2025)

The Existential Theory of Research: Why Discovery Is Hard
di: Majumdar, Angshul
Pubblicazione: (2026)

Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations
di: Majumdar, Angshul
Pubblicazione: (2026)

An extended Knowledge Compilation Map for Conditional Preference Statements-based and Generalized Additive Utilities-based Languages
di: Fargier, Hélène, et al.
Pubblicazione: (2021)

A Quantale-Weakness Route to $P \neq NP$ via CD Evidence Normalization and Gauge-Buffered Locked Ensembles
di: Goertzel, Ben
Pubblicazione: (2025)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
di: Nagda, Ansh, et al.
Pubblicazione: (2025)

The Relativity of AGI: Distributional Axioms, Fragility, and Undecidability
di: Majumdar, Angshul
Pubblicazione: (2026)

Sparsity Is Necessary: Polynomial-Time Stability for Agentic LLMs in Large Action Spaces
di: Majumdar, Angshul
Pubblicazione: (2026)

Greedy Is Enough: Sparse Action Discovery in Agentic LLMs
di: Majumdar, Angshul
Pubblicazione: (2026)

Bi-objective Optimization in Role Mining
di: Crampton, Jason, et al.
Pubblicazione: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
di: Chavrimootoo, Michael C., et al.
Pubblicazione: (2026)

Probabilistic Generating Circuits -- Demystified
di: Agarwal, Sanyam, et al.
Pubblicazione: (2024)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
di: Martinsson, Björn
Pubblicazione: (2024)

Over the Edge of Chaos? Excess Complexity as a Roadblock to Artificial General Intelligence
di: Susnjak, Teo, et al.
Pubblicazione: (2024)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
di: Digulescu, Mircea-Adrian
Pubblicazione: (2026)

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

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
di: Istrate, Gabriel
Pubblicazione: (2024)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
di: Cao, Yang, et al.
Pubblicazione: (2024)

Determining the Outerthickness of Graphs Is NP-Hard
di: Lee, Pin-Hsian, et al.
Pubblicazione: (2026)

Reinforced Generation of Combinatorial Structures: Ramsey Numbers
di: Nagda, Ansh, et al.
Pubblicazione: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
di: Chavrimootoo, Michael C.
Pubblicazione: (2024)

BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?
di: Chambon, Pierre, et al.
Pubblicazione: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Mathematical Algorithm Design for Deep Learning under Societal and Judicial Constraints: The Algorithmic Transparency Requirement
di: Boche, Holger, et al.
Pubblicazione: (2024)

Near-Optimal Coalition Structures in Polynomial Time
di: Majumdar, Angshul
Pubblicazione: (2025)

Journalists, Emotions, and the Introduction of Generative AI Chatbots: A Large-Scale Analysis of Tweets Before and After the Launch of ChatGPT
di: Lewis, Seth C., et al.
Pubblicazione: (2024)

Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
di: Asadi, Ali, et al.
Pubblicazione: (2026)

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
di: Eriksson, Leif, et al.
Pubblicazione: (2026)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
di: Goertzel, Ben, et al.
Pubblicazione: (2026)

The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump
di: Lu, Chien-Ping
Pubblicazione: (2026)

Parameterized Complexity Of Representing Models Of MSO Formulas
di: Kučera, Petr, et al.
Pubblicazione: (2026)

Diversity of Extensions in Abstract Argumentation
di: Fichte, Johannes K., et al.
Pubblicazione: (2026)

Debate is efficient with your time
di: Brown-Cohen, Jonah, et al.
Pubblicazione: (2026)

Solving Multiagent Path Finding on Highly Centralized Networks
di: Fioravantes, Foivos, et al.
Pubblicazione: (2024)