Smoothing the Gap Between NP and ER
From MaRDI portal
Publication:5071086
DOI10.1137/20M1385287MaRDI QIDQ5071086
Tillmann Miltzow, Ivor van der Hoog, Jeff Erickson
Publication date: 20 April 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.02278
Related Items
Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, Topological art in simple galleries, Unnamed Item
Uses Software
Cites Work
- A polynomial upper bound on Reidemeister moves
- Recognition and complexity of point visibility graphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- Towards exact geometric computation
- On O(Tlog T) reduction from RAM computations to satisfiability
- Upper bounds for sorting integers on random access machines
- Short propositional formulas represent nondeterministic computations
- Some provably hard crossing number problems
- A short proof of Chvatal's Watchman Theorem
- Surpassing the information theoretic bound with fusion trees
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Intersection graphs of rays and grounded segments
- The complexity of drawing a graph in a polygonal region
- Recent progress in exact geometric computation
- Time bounded random access machines
- Integer realizations of disk and segment graphs
- Classroom examples of robustness problems in geometric computations
- Realizability of Graphs and Linkages
- Algorithms for Reporting and Counting Geometric Intersections
- Discrete Dynamic Programming and Capital Allocation
- Who Needs Crossings? Hardness of Plane Graph Rigidity
- The computational complexity of knot and link problems
- ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
- Complexity of Some Geometric and Topological Problems
- Smoothed analysis of algorithms
- Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
- An Optimal Algorithm for Computing Visibility in the Plane
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Drawing planar graphs with prescribed face areas
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Realization spaces of 4-polytopes are universal
- Smoothed Analysis of Local Search for the Maximum-Cut Problem
- The art gallery problem is ∃ ℝ-complete
- A friendly smoothed analysis of the simplex method
- The Complexity of Positive Semidefinite Matrix Factorization
- Sphere and dot product representations of graphs
- Some undecidable problems involving elementary functions of a real variable
- The complexity of theorem-proving procedures
- Random knapsack in expected polynomial time
- Algorithms in real algebraic geometry
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
