Fetching the paper…
Reading the bibliography…
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent.
A decision method for elementary algebra and geometry
Alfred Tarski · 1951
Earlier work this paper cites.
Rank factorization of nonnegative matrices
A. Berman · 1973
Earlier work this paper cites.
An efficient simplex coverability algorithm in E 2 E^{2} with application to stochastic sequential machines
Charles B. Silio Jr · 1979
Earlier work this paper cites.
Finding minimal convex nested polygons
Alok Aggarwal, Heather Booth, Joseph O’Rourke, Subhash Suri, and Chee K. Yap · 1985
Earlier work this paper cites.
Some algebraic and geometric computations in pspace
John Canny · 1988
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
Nikolai E. Mnëv · 1988
Earlier work this paper cites.
The computational geometry column# 4
Joseph O’Rourke · 1988
Earlier work this paper cites.
Approximation schemes in computational geometry
Gautam Das · 1990
Earlier work this paper cites.
The complexity of minimum convex nested polyhedra
Gautam Das and Deborah Joseph · 1990
Earlier work this paper cites.
Some provably hard crossing number problems
Daniel Bienstock · 1991
Earlier work this paper cites.
Stretchability of pseudolines is np-hard
Peter Shor · 1991
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs
Mihalis Yannakakis · 1991
Earlier work this paper cites.
Minimum vertex hulls for polyhedral domains
Gautam Das and Deborah Joseph · 1992
Earlier work this paper cites.
Algorithms for polytope covering and approximation
Kenneth L. Clarkson · 1993
Earlier work this paper cites.
Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
Joel E. Cohen and Uriel G. Rothblum · 1993
Cited alongside, same era.
Intersection graphs of segments
Jan Kratochvíl and Jiří Matoušek · 1994
Cited alongside, same era.
Almost optimal set covers in finite vc-dimension
Hervé Brönnimann and Michael T. Goodrich · 1995
Cited alongside, same era.
Realization spaces of 4-polytopes are universal
Jürgen Richter-Gebert and Günter M Ziegler · 1995
Cited alongside, same era.
On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
Gautam Das and Michael T. Goodrich · 1997
Cited alongside, same era.
On the complexity of nonnegative matrix factorization
Stephen A. Vavasis · 2009
Cited alongside, same era.
Nonnegative matrix factorization requires irrationality
Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell · 2016
Later among the works it cites.
An almost optimal algorithm for computing nonnegative rank
Ankur Moitra · 2016
Later among the works it cites.
A universality theorem for nonnegative matrix factorizations
Yaroslav Shitov · 2016
Later among the works it cites.
Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
Vittorio Bilò and Marios Mavronicolas · 2017
Later among the works it cites.
Intersection graphs of rays and grounded segments
Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber · 2017
Later among the works it cites.
Recognition and complexity of point visibility graphs
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Complexity of some geometric and topological problems
Marcus Schaefer · 2010
Cited alongside, same era.
Computing a nonnegative matrix factorization - provably
Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra · 2012
Cited alongside, same era.
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf · 2012
Cited alongside, same era.
On the geometric interpretation of the nonnegative rank
Nicolas Gillis and François Glineur · 2012
Cited alongside, same era.
Integer realizations of disk and segment graphs
Colin McDiarmid and Tobias Müller · 2013
Cited alongside, same era.
An almost optimal algorithm for computing nonnegative rank
Ankur Moitra · 2013
Cited alongside, same era.
Jean Cardinal and Udo Hoffmann · 2017
Later among the works it cites.
Fixed points, Nash equilibria, and the existential theory of the reals
Marcus Schaefer and Daniel Štefankovič · 2017
Later among the works it cites.
The nonnegative rank of a matrix: Hard problems, easy solutions
Yaroslav Shitov · 2017
Later among the works it cites.
The art gallery problem is ∃ ℝ \exists\mathbb{R} -complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow · 2018
Later among the works it cites.
Smoothed analysis of the art gallery problem
Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow · 2018
Later among the works it cites.
∀ ∃ ℝ \forall\exists\mathbb{R} -completeness and area-universality
Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzażewski · 2018
Later among the works it cites.
The complexity of drawing a graph in a polygonal region
Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal · 2018
Later among the works it cites.
Smoothed analysis of order types
Ivor van der Hoog, Tillmann Miltzow, and Martijn van Schaik · 2019
Closest in time.