Fetching the paper…
Reading the bibliography…
We show that computing the minimum rank of a sign pattern matrix is NP hard.
On the density of families of sets
N Sauer · 1972
Earlier work this paper cites.
A combinatorial problem; stability and order for models and theories in infinitary languages
Saharon Shelah · 1972
Earlier work this paper cites.
Oriented matroids
J. Folkman and J. Lawrence · 1978
Earlier work this paper cites.
On determinants, matchings and random algorithms
L. Lovász · 1979
Earlier work this paper cites.
Proof of a conjecture of Burr, Grã¼nbaum, and Sloane
Jacob E. Goodman · 1980
Earlier work this paper cites.
Semispaces of configurations, cell complexes of arrangements
Jacob E. Goodman and Richard Pollack · 1984
Earlier work this paper cites.
Geometrical realization of set systems and probabilistic communication complexity
N. Alon, P. Frankl, and V. Rodl · 1985
Earlier work this paper cites.
Probabilistic communication complexity
Ramamohan Paturi and Janos Simon · 1986
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
N.E. Mnev · 1988
Earlier work this paper cites.
Stretchability of Pseudolines is NP-hard
Peter W. Shor · 1991
Earlier work this paper cites.
On the computational complexity and geometry of the first-order theory of the reals. Part I: The geometry of semi-algebraic sets. the decision problem for the existential theory of the reals
James Renegar · 1992
Cited alongside, same era.
In Jacob E. Goodman and Joseph O’Rourke, editors, Handbook of discrete and computational geometry
Jacob E. Goodman · 1997
Cited alongside, same era.
Oriented matroids
Jürgen Richter-Gebert and Günter M. Ziegler · 1997
Cited alongside, same era.
Oriented Matroids
Björner, Anders, Vergnas, White, and Ziegler · 1999
Cited alongside, same era.
The computational complexity of some problems of linear algebra
Jonathan F Buss, Gudmund S Frandsen, and Jeffrey O Shallit · 1999
Cited alongside, same era.
The folkman-lawrence topological representation theorem for oriented matroids – an elementary proof in rank 3
The minimum rank problem: a counterexample
S. Kopparty and K. P. S. Bhaskara Rao · 2007
Later among the works it cites.
Complexity measures of sign matrices
Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman · 2007
Later among the works it cites.
Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers
Avi Berman, Shmuel Friedland, Leslie Hogben, Uriel G. Rothblum, and Bryan L. Shader · 2008
Later among the works it cites.
Visibility constraints on features of 3d objects
R. Basri, P.F. Felzenszwalb, R.B. Girshick, D.W. Jacobs, and C.J. Klivans · 2009
Later among the works it cites.
The sign-rank of AC 0
Alexander A. Razborov and Alexander A. Sherstov · 2010
Later among the works it cites.
Computing a nonnegative matrix factorization – provably
Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jürgen Bokowski, Susanne Mock, and Ileana Streinu · 1999
Cited alongside, same era.
A linear lower bound on the unbounded error probabilistic communication complexity
J. Forster · 2001
Cited alongside, same era.
Rational realizations of the minimum rank of a sign pattern matrix
Marina Arav, Frank J. Hall, Selcuk Koyuncu, Zhongshan Li, and Bhaskara Rao · 2005
Cited alongside, same era.
http://aimath.org/pastworkshops/matrixspectrum.html
American institute for mathematics. workshop on spectra of families of matrices described by graphs, digraphs, and sign patterns, 2006 · 2006
Cited alongside, same era.
Fast matrix multiplication using coherent configurations
Henry Cohn and Christopher Umans · 2013
Later among the works it cites.
An almost optimal algorithm for computing nonnegative rank
Ankur Moitra · 2013
Later among the works it cites.
Sign rank, vc dimension and spectral gaps
Noga Alon, Shay Moran, and Amir Yehudayoff · 2014
Later among the works it cites.