Fetching the paper…
Reading the bibliography…
We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER).
Towards exact geometric computation
Chee-Keng Yap · 1912
Earlier work this paper cites.
Discrete dynamic programming and capital allocation
George Nemhauser and Zev Ullmann · 1969
Earlier work this paper cites.
Some undecidable problems involving elementary functions of a real variable
Daniel Richardson · 1969
Earlier work this paper cites.
How good is the simplex algorithm
Victor Klee and George Minty · 1970
Earlier work this paper cites.
The complexity of theorem-proving procedures
Stephen A Cook · 1971
Earlier work this paper cites.
Time bounded random access machines
Stephen Cook and Robert Reckhow · 1973
Earlier work this paper cites.
Universal sequential search problems
Leonid Anatolevich Levin · 1973
Earlier work this paper cites.
On the power of multiplciation in random-access machines
Juris Hartmanis and Janos Simon · 1974
Earlier work this paper cites.
A short proof of Chvátal’s watchman theorem
Steve Fisk · 1978
Earlier work this paper cites.
Algorithms for reporting and counting geometric intersections
Jon Bentley and Thomas Ottmann · 1979
Earlier work this paper cites.
Algorithms for reporting and counting geometric intersections
Jon Louis Bentley and Thomas A Ottmann · 1979
Earlier work this paper cites.
On the power of random access machines
Arnold Schönhage · 1979
Earlier work this paper cites.
Computational Geometry
Michael Ian Shamos · 1979
Earlier work this paper cites.
Upper bounds for sorting integers on random access machines
David Kirkpatrick and Stefan Reisch · 1984
Earlier work this paper cites.
Simulations among classes of random access machines and equivalence among numbers succinctly represented
Alberto Bertoni, Giancarlo Mauri, and Nicoletta Sabadini · 1985
Earlier work this paper cites.
Computational Geometry: An Introduction
Franco Preparata and Michael Ian Shamos · 1985
Earlier work this paper cites.
Short propositional formulas represent nondeterministic computations
Stephen Cook · 1987
Earlier work this paper cites.
Reporting and counting intersections between two sets of line segments
Harry Mairson and Jorge Stolfi · 1988
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
Nicolai Mnëv · 1988
Earlier work this paper cites.
On a theory of computation and complexity over the real numbers: n p np -completeness, recursive functions and universal machines
Lenore Blum, Mike Shub, and Steve Smale · 1989
Earlier work this paper cites.
Coordinate representation of order types requires exponential storage
Jacob Goodman, Richard Pollack, and Bernd Sturmfels · 1989
Earlier work this paper cites.
Epsilon geometry: building robust algorithms from imprecise computations
David Salesin, Jorge Stolfi, and Leonidas Guibas · 1989
Earlier work this paper cites.
Machine models and similations
Peter van Emde Boas · 1990
Earlier work this paper cites.
Some provably hard crossing number problems
Daniel Bienstock · 1991
Earlier work this paper cites.
An O ( T log T ) O(T\log T) reduction from RAM computations to satisfiability
John Robson · 1991
Earlier work this paper cites.
Stretchability of pseudolines is NP-hard
Peter Shor · 1991
Cited alongside, same era.
Efficient exact arithmetic for computational geometry
Steven Fortune and Christopher Van Wyk · 1993
Cited alongside, same era.
Surpassing the information theoretic bound with fusion trees
Michael Fredman and Dan Willard · 1993
Cited alongside, same era.
Trans-dichotomous algorithms for minimum spanning trees and shortest paths
Michael Fredman and Dan Willard · 1994
Cited alongside, same era.
An optimal algorithm for computing visibility in the plane
Paul Heffernan and Joseph Mitchell · 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.
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod · 2015
Later among the works it cites.
A polynomial upper bound on Reidemeister moves
Marc Lackenby · 2015
Later among the works it cites.
Who needs crossings? Hardness of plane graph rigidity
Zachary Abel, Erik Demaine, Martin Demaine, Sarah Eisenstat, Jayson Lynch, and Tao Schardl · 2016
Later among the works it cites.
A universality theorem for nonnegative matrix factorizations
Yaroslav Shitov · 2016
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
Jean Cardinal and Udo Hoffmann · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Complexity and Real Computation
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale · 1998
Cited alongside, same era.
Sorting and searching on the word ram
Torben Hagerup · 1998
Cited alongside, same era.
Robust proximity queries: An illustration of degree-driven algorithm design
Giuseppe Liotta, Franco P Preparata, and Roberto Tamassia · 1998
Cited alongside, same era.
The computational complexity of knot and link problems
Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger · 1999
Cited alongside, same era.
Random knapsack in expected polynomial time
René Beier and Berthold Vöcking · 2003
Cited alongside, same era.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
∀ ∃ R \forall\exists\mdmathbb{R} -completeness and area-universality
Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rza̧żewski · 2017
Later among the works it cites.
Smoothed analysis of local search for the maximum-cut problem
Michael Etscheid and Heiko Röglin · 2017
Later among the works it cites.
On the complexity of minimum-link path problems
Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals · 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 complexity of positive semidefinite matrix factorization
Yaroslav Shitov · 2017
Later among the works it cites.
The art gallery problem is ∃ R \exists\mdmathbb{R} -complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow · 2018
Later among the works it cites.
EPTAS for max clique on disks and unit balls
Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, and Stéphan Thomassé · 2018
Later among the works it cites.
A friendly smoothed analysis of the simplex method
Daniel Dadush and Sophie Huiberts · 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.
Planar graphs and faces areas – Area-Universality
Linda Kleist · 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.
A universality theorem for nested polytopes
Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow · 2019
Closest in time.
Optimal curve straightening is ∃ R \exists\mdmathbb{R} -complete
Jeff Erickson · 2019
Closest in time.
Smoothed analysis of order types
Ivor van der Hoog, Tillmann Miltzow, and Martijn van Schaik · 2019
Closest in time.
A framework for ∃ R \exists\mdmathbb{R} -completeness of two-dimensional packing problems
Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth · 2020
Closest in time.
Finding closed quasigeodesics on convex polyhedra
Erik D Demaine, Adam C Hesterberg, and Jason S Ku · 2020
Closest in time.
Smoothing the gap between np and er
Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow · 2020
Closest in time.
Training neural networks is er-complete
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow · 2021
Closest in time.
On classifying continuous constraint satisfaction problems
Tillmann Miltzow and Reinier F. Schmiermann · 2021
Closest in time.