18 papers
Tensor Spectral Threshold is -Hard
Angshul Majumdar
We study the decision version of tensor spectral norm from the viewpoint of real algebraic complexity. For a rationally specified tensor, the tensor spectral threshold problem asks…
How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
Angshul Majumdar
This paper studies the computational difficulty of clustering problems that are defined directly on a continuous probability density. Rather than working with finite samples, we as…
-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
Angshul Majumdar
We study the computational complexity of singularity for multilinear maps. While the determinant characterizes singularity for matrices, its multilinear analogue -- the hyperdeterm…
The Existential Theory of Research: Why Discovery Is Hard
Angshul Majumdar
Can scientific discovery be made arbitrarily easy by choosing the right representation, collecting enough data, and deploying sufficiently powerful algorithms? This paper argues th…
Constrained Nonnegative Gram Feasibility is -Complete
Angshul Majumdar
We study the computational complexity of constrained nonnegative Gram feasibility. Given a partially specified symmetric matrix together with affine relations among selected entrie…
Diminishing Returns in Expanding Generative Models and Godel-Tarski-Lob Limits
Angshul Majumdar
Modern generative modelling systems are increasingly improved by expanding model capacity, training data, and computational resources. While empirical studies have documented such…