81 citations · 168 across the 67 of their papers we have counts for
18 papers · 1 filter
A Measure-Theoretic Derivation of Zadeh Fuzzy Logic
Angshul Majumdar
Zadeh fuzzy logic is normally introduced by assigning scalar membership degrees and postulating standard complement, minimum conjunction, and maximum disjunction. We derive this ca…
Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
Angshul Majumdar
We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversariall…
Quantum-Stable Robust Principal Component Analysis: Theory and Evidence from NISQ Regimes
Angshul Majumdar
Robust Principal Component Analysis (RPCA) is a fundamental technique for extracting low-rank structures from data corrupted by sparse anomalies and noise. While classical RPCA and…
Clustering as Approximation by Constrained Projectors: Theory and Guarantees
Angshul Majumdar
This paper develops a unified theoretical framework showing that a broad family of clustering methods, including k-means, fuzzy c-means, kernel k-means, kernel FCM, and spectral cl…
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…
Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels
Angshul Majumdar
We study the exact decision problem for feedback capacity of finite-state channels (FSCs). Given an encoding of a binary-input binary-output rational unifilar FSC with specifie…
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…
The Relativity of AGI: Distributional Axioms, Fragility, and Undecidability
Angshul Majumdar
We study whether Artificial General Intelligence (AGI) admits a coherent theoretical definition that supports absolute claims of existence, robustness, or self-verification. We for…
Greedy Is Enough: Sparse Action Discovery in Agentic LLMs
Angshul Majumdar
Modern agentic systems operate in environments with extremely large action spaces, such as tool-augmented language models with thousands of available APIs or retrieval operations.…
Sparsity Is Necessary: Polynomial-Time Stability for Agentic LLMs in Large Action Spaces
Angshul Majumdar
Tool-augmented LLM systems expose a control regime that learning theory has largely ignored: sequential decision-making with a massive discrete action universe (tools, APIs, docume…
Quantum-Compatible Dictionary Learning via Doubly Sparse Models
Angshul Majumdar
Dictionary learning (DL) is a core tool in signal processing and machine learning for discovering sparse representations of data. In contrast with classical successes, there is cur…
Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and Relaxations
Angshul Majumdar
We study coalition structure generation (CSG) when coalition values are not given but must be learned from episodic observations. We model each episode as a sparse linear regressio…