13 citations · 49 across the 57 of their papers we have counts for
5 papers · 1 filter
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…
Universal NP-Hardness of Clustering under General Utilities
Angshul Majumdar
Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperpara…
Affine Rank Minimization is ER Complete
Angshul Majumdar
We study the decision problem Affine Rank Minimization, denoted ARM(k). The input consists of rational matrices A_1,...,A_q in Q^{m x n} and rational scalars b_1,...,b_q in Q. The…