Fetching the paper…
Reading the bibliography…
We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard.
D. Hilbert, “Mathematical problems,” Bull. Amer. Math. Soc
1902
Earlier work this paper cites.
F. L. Hitchcock, “The expression of a tensor or a polyadic as a sum of products,” J. Math. Phys
1927
Earlier work this paper cites.
F. L. Hitchcock, “Multiple invariants and generalized rank of a p p -way matrix or tensor,” J. Math. Phys
1927
Earlier work this paper cites.
A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem,” Proc. Lond. Math. Soc
1937
Earlier work this paper cites.
S. Banach, “Über homogene polynome in ( L 2 ) (L^{2}) ,” Studia Math
1938
Earlier work this paper cites.
M. Davis, H. Putnam, and J. Robinson, “The decision problem for exponential diophantine equations,” Ann. of Math
1961
Earlier work this paper cites.
G. H. Golub and W. Kahan, “Calculating the singular values and pseudo-inverse of a matrix,” J. Soc. Indust. Appl. Math. Ser. B
1965
Earlier work this paper cites.
T. Motzkin and E. G. Straus, “Maxima for graphs and a new proof of a theorem of Turán,” Canad. J. Math
1965
Earlier work this paper cites.
J. Edmonds, “Systems of distinct representatives and linear algebra,” J. Res. Nat. Bur. Standards
1967
Earlier work this paper cites.
V. Strassen, “Gaussian elimination is not optimal,” Numer. Math
1969
Earlier work this paper cites.
B. Buchberger, “Ein algorithmisches kriterium für die Lösbarkeit eines algebraischen Gleichungssystems,” Aequationes Math
1970
Earlier work this paper cites.
G. H. Golub and C. Reinsch, “Singular value decomposition and least squares solutions,” Numer. Math
1970
Earlier work this paper cites.
Y. V. Matijasevič, “The Diophantineness of enumerable sets,” Dokl. Akad. Nauk SSSR
1970
Earlier work this paper cites.
S. Cook, “The complexity of theorem proving procedures,” Proc. ACM Symp. Theory Comput
1971
Earlier work this paper cites.
R. M. Karp, “Reducibility among combinatorial problems,” pp. 85–103, in R.E. Miller and J.W. Thatcher (Eds), Complexity of Computer Computations
1972
Earlier work this paper cites.
L. A. Levin, “Universal sequential search problems,” Probl. Inf. Transm
1973
Earlier work this paper cites.
D. E. Knuth, “A terminology proposal,” SIGACT News
1974
Earlier work this paper cites.
D. E. Knuth, “Postscript about NP-hard problems,” SIGACT News
1974
Earlier work this paper cites.
M. Davis, Y. Matijasevich, and J. Robinson, “Diophantine equations: positive aspects of a negative solution,” pp. 323–378, Mathematical Developments Arising from Hilbert Problems
1976
Earlier work this paper cites.
M. R. Garey and D. S. Johnson, Computers and Intractability
1979
Earlier work this paper cites.
L. G. Khachiyan, “A polynomial algorithm in linear programming,” Dokl. Akad. Nauk SSSR
1979
Earlier work this paper cites.
L. G. Valiant, “Completeness classes in algebra,” Proc. ACM Symp. Theory Comput
1979
Earlier work this paper cites.
L. G. Valiant, “The complexity of computing the permanent,” Theoret. Comput. Sci
1979
Earlier work this paper cites.
D. Bayer, The Division Algorithm and the Hilbert Scheme
1982
Earlier work this paper cites.
J. P. Jones, “Universal Diophantine equation,” J. Symbolic Logic
1982
Earlier work this paper cites.
J. P. Jones and Y. V. Matijasevič, “Register machine proof of the theorem on exponential diophantine representation of enumerable sets,” J. Symbolic Logic
1984
Earlier work this paper cites.
D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer,” Proc. Roy. Soc. London Ser. A
1985
Earlier work this paper cites.
T. F. Coleman and A. Pothen, “The null space problem I: Complexity,” SIAM J. Algebraic Discrete Methods
1986
Earlier work this paper cites.
K. G. Murty and S. N. Kabadi, “Some NP-complete problems in quadratic and nonlinear programming,” Math. Programming
1987
Earlier work this paper cites.
L. Blum, M. Shub, and S. Smale, “On a theory of computation and complexity over the real numbers,” Bull. Amer. Math. Soc
1989
Earlier work this paper cites.
R. Coppi and S. Bolasco (Eds.), Multiway Data Analysis
1989
Earlier work this paper cites.
J. Håstad, “Tensor rank is NP-complete,” J. Algorithms
1990
Earlier work this paper cites.
D. S. Hochbaum and J. G. Shanthikumar, “Convex separable optimization is not much harder than linear optimization,” J. Assoc. Comput. Mach
1990
Earlier work this paper cites.
J. Friedman, “The spectra of infinite hypertrees,” SIAM J. Comput
1991
Earlier work this paper cites.
S. A. Vavasis, Nonlinear Optimization: Complexity Issues
1991
Earlier work this paper cites.
I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, “Hyperdeterminants,” Adv. Math
1992
Earlier work this paper cites.
B. Reznick, “Sums of even powers of real linear forms,” Mem. Amer. Math. Soc
1992
Earlier work this paper cites.
A. I. Barvinok, “Feasibility testing for systems of real quadratic equations,” Discrete Comput. Geom
1993
Earlier work this paper cites.
Y. V. Matijasevič, Hilbert’s Tenth Problem
1993
Earlier work this paper cites.
P. Comon, “Independent component analysis: a new concept?,” Signal Process
1994
Earlier work this paper cites.
I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants
1994
Earlier work this paper cites.
L. Lovász, “Stable sets and polynomials,” Discrete Math
1994
Earlier work this paper cites.
M. Aigner, “Turán’s graph theorem,” Amer. Math. Monthly
1995
Earlier work this paper cites.
A. I. Barvinok, “New algorithms for linear k k -matroid intersection and matroid k k -parity problems,” Math. Programming
1995
Earlier work this paper cites.
J. A. De Loera, “Gröbner bases and graph colorings,” Beiträge Algebra Geom
1995
Earlier work this paper cites.
J. Friedman and A. Wigderson, “On the second eigenvalue of hypergraphs,” Combinatorica
1995
Cited alongside, same era.
M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. Assoc. Comput. Mach
1995
Cited alongside, same era.
B. K. Natarajan, “Sparse approximate solutions to linear systems,” SIAM J. Comput
1995
Cited alongside, same era.
P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic Complexity Theory
1996
Cited alongside, same era.
E. Bernstein and U. Vazirani, “Quantum complexity theory,” SIAM J. Comput
1997
Cited alongside, same era.
S. Cohen and C. Tomasi. “Systems of bilinear equations,” Technical Report
D. Steinberg, Computation of Matrix Norms with Applications to Robust Optimization
2005
Later among the works it cites.
N. Alon and A. Naor, “Approximating the cut-norm via Grothendieck’s inequality,” SIAM J. Comput
2006
Later among the works it cites.
D. Zuckerman, “Linear degree extractors and the inapproximability of max clique and chromatic number,” Proc. ACM Symp. Theory Comput
2006
Later among the works it cites.
D. A. Cox, J.B. Little, and D. O’Shea, Ideals, Varieties, and Algorithms
2007
Later among the works it cites.
M. Fürer, “Faster integer multiplication,” Proc. ACM Symp. Theory Comput
2007
Later among the works it cites.
V. Halava, T. Harju, and M. Hirvensalo, “Undecidability bounds for integer matrices using Claus instances,” Internat. J. Found. Comput. Sci
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
1997
Cited alongside, same era.
S. Hill and W. K. Wootters, “Entanglement of a pair of quantum bits,” Phys. Rev. Lett
1997
Cited alongside, same era.
D. S. Hochbaum (Ed.), Approximation Algorithms for NP-Hard Problems
1997
Cited alongside, same era.
W. Kahan, IEEE Standard 754 for Binary Floating-Point Arithmetic
1997
Cited alongside, same era.
V. Y. Pan, “Solving a polynomial equation: some history and recent progress,” SIAM Rev
1997
Cited alongside, same era.
L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation
1998
Cited alongside, same era.
J. Bochnak, M. Coste, and M. F. Roy, Real Algebraic Geometry
1998
Cited alongside, same era.
2007
Later among the works it cites.
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, “Optimal inapproximability results for max-cut
2007
Later among the works it cites.
B. Lambov, “RealLib: An efficient implementation of exact real arithmetic,” Mathematical Structures in Comp. Sci
2007
Later among the works it cites.
G. Ni, L. Qi, F. Wang, and Y. Wang, “The degree of the E-characteristic polynomial of an even order tensor,” J. Math. Anal. Appl
2007
Later among the works it cites.
A. Pappas, Y. Sarantopoulos, and A. Tonge, “Norm attaining polynomials,” Bull. Lond. Math. Soc
2007
Later among the works it cites.
L. Qi, “Eigenvalues and invariants of tensors,” J. Math. Anal. Appl
2007
Later among the works it cites.
E. S. Allman and J. A. Rhodes, “Phylogenetic ideals and varieties for the general Markov model,” Adv. in Appl. Math
2008
Later among the works it cites.
C. Bachoc and F. Vallentin, “New upper bounds for kissing numbers from semidefinite programming,” J. Amer. Math. Soc
2008
Later among the works it cites.
P. Comon, G. H. Golub, L.-H. Lim, and B. Mourrain, “Symmetric tensors and symmetric tensor rank,” SIAM J. Matrix Anal. Appl
2008
Later among the works it cites.
A. De, P. P. Kurur, C. Saha, and R. Saptharishi, “Fast integer multiplication using modular arithmetic,” Proc. ACM Symp. Theory Comput
2008
Later among the works it cites.
E. De Klerk, “The complexity of optimizing over a simplex, hypercube or sphere: a short survey,” Cent. Eur. J. Oper. Res
2008
Later among the works it cites.
J. A. De Loera, J. Lee, P. N. Malkin, and S. Margulies, “Hilbert’s nullstellensatz and an algorithm for proving combinatorial infeasibility,” Proc. Int. Symposium Symb. Algebr. Comput
2008
Later among the works it cites.
V. De Silva and L.-H. Lim, “Tensor rank and the ill-posedness of the best low-rank approximation problem,” SIAM J. Matrix Anal. Appl
2008
Later among the works it cites.
N. J. Higham, Functions of Matrices: Theory and computation
2008
Later among the works it cites.
C. Hillar and T. Windfeldt, “Algebraic characterization of uniquely vertex colorable graphs,” J. Combin. Theory Ser. B
2008
Later among the works it cites.
P. Huggins, B. Sturmfels, J. Yu, and D. S. Yuster, “The hyperdeterminant and triangulations of the 4-cube,” Math. Comp
2008
Later among the works it cites.
T. Schultz and H.-P. Seidel, “Estimating crossing fibers: a tensor decomposition approach,” IEEE Trans. Vis. Comput. Graphics
2008
Later among the works it cites.
C. Bachoc, G. Nebe, F.M. de Oliveira Filho, and F. Vallentin, “Lower bounds for measurable chromatic numbers,” Geom. Funct. Anal
2009
Closest in time.
C. Beltrán and L. M. Pardo, “Efficient polynomial system-solving by numerical methods,” J. Fixed Point Theory Appl
2009
Closest in time.
S. C. Brubaker and S. S. Vempala , “Random tensors and planted cliques,” pp. 409–419, in Dinur et al. (Eds.), APPROX and RANDOM 2009
2009
Closest in time.
D. A. Cartwright, S. M. Brady, D. A. Orlando, B. Sturmfels, and P. N. Benfey, “Reconstructing spatiotemporal gene expression data from partial observations,” Bioinform
2009
Closest in time.
L. Fortnow, “The status of the P versus NP problem,” Comm. ACM
2009
Closest in time.
S. A. Vavasis, “On the complexity of nonnegative matrix factorization,” SIAM J. Optim
2009
Closest in time.
J. Briët, F. M. de Oliveira Filho, and F. Vallentin, “The positive semidefinite Grothendieck problem with rank constraint,” pp. 31–42, in S. Abramsky et al. (Eds), Automata, Languages and Programming
2010
Closest in time.
2010
Closest in time.
B. Grenet, P. Koiran, and N. Portier, “The multivariate resultant is NP-hard in any characteristic,” pp. 477–488 in P. Hliněný and A. Kučera (Eds), Mathematical Foundations of Computer Science
2010
Closest in time.
S. He, Z. Li, and S. Zhang, “Approximation algorithms for homogeneous polynomial optimization with quadratic constraints,” Math. Programming Ser. B
2010
Closest in time.
J. M. Hendrickx and A. Olshevsky, “Matrix p p -norms are NP-hard to approximate if p ≠ 1 , 2 , ∞ p\neq 1,2,\infty ,” SIAM J. Matrix Anal. Appl
2010
Closest in time.
P. J. C. Dickinson and L. Gijben, “On the computational complexity of membership problems for the completely positive cone and its dual,” preprint
2011
Closest in time.
S. Arora, R. Ge, R. Kannan, and A. Moitra, “Computing a nonnegative matrix factorization — provably,” Proc. ACM Symp. Theory Comput
2012
Closest in time.
P. J. Freitas, S. Friedland, and G. Porta, “Upper bounds on the magnitude of solutions of certain linear systems with integer coefficients,” Electron. J. Linear Algebra
2012
Closest in time.
J. M. Landsberg, Tensors: Geometry and Applications
2012
Closest in time.
B. Poonen, “Undecidable problems: a sampler,” http://arxiv.org/abs/1204.0299
2012
Closest in time.
M. Sipser, Introduction to the Theory of Computation, 3rd Ed., Cengage Learning, Boston, MA, 2012
2012
Closest in time.
A. A. Ahmadi, A. Olshevsky, P. A. Parrilo, and J. N. Tsitsiklis, “NP-hardness of deciding convexity of quartic polynomials and related problems,” Math. Program. Ser. A
2013
Closest in time.
D. A. Cartwright and B. Sturmfels, “The number of eigenvalues of a tensor,” Linear Algebra Appl
2013
Closest in time.
D. Kressner, “Bivariate matrix functions,” Oper. Matrices
2013
Closest in time.
L.-H. Lim, “Tensors and hypermatrices,” in: L. Hogben (Ed.), Handbook of Linear Algebra
2013
Closest in time.
L.-H. Lim and T. Schultz, “Moment tensors and high angular resolution diffusion imaging,” preprint
2013
Closest in time.