Smoothing the Gap Between NP and ER (Q5071086): Difference between revisions

@@ Property / cites work @@
+Who Needs Crossings? Hardness of Plane Graph Rigidity
+Normal rank
@@ Property / cites work @@
+The art gallery problem is ∃ ℝ-complete
@@ Property / cites work: The art gallery problem is ∃ ℝ-complete / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms in real algebraic geometry
@@ Property / cites work: Algorithms in real algebraic geometry / rank @@
+Normal rank
@@ Property / cites work @@
+Random knapsack in expected polynomial time
@@ Property / cites work: Random knapsack in expected polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms for Reporting and Counting Geometric Intersections
+Normal rank
@@ Property / cites work @@
+Q3750122
@@ Property / cites work: Q3750122 / rank @@
+Normal rank
@@ Property / cites work @@
+Some provably hard crossing number problems
@@ Property / cites work: Some provably hard crossing number problems / rank @@
+Normal rank
@@ Property / cites work @@
+COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
@@ Property / cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO / rank @@
+Normal rank
@@ Property / cites work @@
+On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
+Normal rank
@@ Property / cites work @@
+Intersection graphs of rays and grounded segments
@@ Property / cites work: Intersection graphs of rays and grounded segments / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition and complexity of point visibility graphs
+Normal rank
@@ Property / cites work @@
+Short propositional formulas represent nondeterministic computations
+Normal rank
@@ Property / cites work @@
+Time bounded random access machines
@@ Property / cites work: Time bounded random access machines / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+Q3413659
@@ Property / cites work: Q3413659 / rank @@
+Normal rank
@@ Property / cites work @@
+A friendly smoothed analysis of the simplex method
+Normal rank
@@ Property / cites work @@
+Q2934725
@@ Property / cites work: Q2934725 / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed Analysis of Local Search for the Maximum-Cut Problem
+Normal rank
@@ Property / cites work @@
+A short proof of Chvatal's Watchman Theorem
@@ Property / cites work: A short proof of Chvatal's Watchman Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Surpassing the information theoretic bound with fusion trees
+Normal rank
@@ Property / cites work @@
+Trans-dichotomous algorithms for minimum spanning trees and shortest paths
+Normal rank
@@ Property / cites work @@
+ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
+Normal rank
@@ Property / cites work @@
+The computational complexity of knot and link problems
+Normal rank
@@ Property / cites work @@
+An Optimal Algorithm for Computing Visibility in the Plane
+Normal rank
@@ Property / cites work @@
+Sphere and dot product representations of graphs
@@ Property / cites work: Sphere and dot product representations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Classroom examples of robustness problems in geometric computations
+Normal rank
@@ Property / cites work @@
+Upper bounds for sorting integers on random access machines
+Normal rank
@@ Property / cites work @@
+Q4051879
@@ Property / cites work: Q4051879 / rank @@
+Normal rank
@@ Property / cites work @@
+Drawing planar graphs with prescribed face areas
@@ Property / cites work: Drawing planar graphs with prescribed face areas / rank @@
+Normal rank
@@ Property / cites work @@
+Q2978407
@@ Property / cites work: Q2978407 / rank @@
+Normal rank
@@ Property / cites work @@
+A polynomial upper bound on Reidemeister moves
@@ Property / cites work: A polynomial upper bound on Reidemeister moves / rank @@
+Normal rank
@@ Property / cites work @@
+Q4071737
@@ Property / cites work: Q4071737 / rank @@
+Normal rank
@@ Property / cites work @@
+Recent progress in exact geometric computation
@@ Property / cites work: Recent progress in exact geometric computation / rank @@
+Normal rank
@@ Property / cites work @@
+Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
+Normal rank
@@ Property / cites work @@
+The complexity of drawing a graph in a polygonal region
+Normal rank
@@ Property / cites work @@
+Integer realizations of disk and segment graphs
@@ Property / cites work: Integer realizations of disk and segment graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3819622
@@ Property / cites work: Q3819622 / rank @@
+Normal rank
@@ Property / cites work @@
+Discrete Dynamic Programming and Capital Allocation
+Normal rank
@@ Property / cites work @@
+Q3694703
@@ Property / cites work: Q3694703 / rank @@
+Normal rank
@@ Property / cites work @@
+Some undecidable problems involving elementary functions of a real variable
+Normal rank
@@ Property / cites work @@
+Realization spaces of 4-polytopes are universal
@@ Property / cites work: Realization spaces of 4-polytopes are universal / rank @@
+Normal rank
@@ Property / cites work @@
+On O(Tlog T) reduction from RAM computations to satisfiability
+Normal rank
@@ Property / cites work @@
+Complexity of Some Geometric and Topological Problems
+Normal rank
@@ Property / cites work @@
+Realizability of Graphs and Linkages
@@ Property / cites work: Realizability of Graphs and Linkages / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed points, Nash equilibria, and the existential theory of the reals
+Normal rank
@@ Property / cites work @@
+Q4197343
@@ Property / cites work: Q4197343 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Positive Semidefinite Matrix Factorization
+Normal rank
@@ Property / cites work @@
+Q3974991
@@ Property / cites work: Q3974991 / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed analysis of algorithms
@@ Property / cites work: Smoothed analysis of algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385524
@@ Property / cites work: Q4385524 / rank @@
+Normal rank
@@ Property / cites work @@
+Towards exact geometric computation
@@ Property / cites work: Towards exact geometric computation / rank @@
+Normal rank