Abstract
We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if it can be written as an ETR formula. Traditionally, these problems are studied in the real RAM, a model of computation that assumes that the storage and comparison of real-valued numbers can be done in constant space and time, with infinite precision.
| Original language | English |
|---|---|
| Title of host publication | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
| Number of pages | 12 |
| Publisher | IEEE |
| Publication date | 2020 |
| Pages | 1022-1033 |
| DOIs | |
| Publication status | Published - 2020 |
| Externally published | Yes |
| Event | Foundations of Computer Science - Sydney, Australia Duration: 14 Dec 2020 → 17 Dec 2020 Conference number: 61 |
Conference
| Conference | Foundations of Computer Science |
|---|---|
| Number | 61 |
| Country/Territory | Australia |
| City | Sydney |
| Period | 14/12/2020 → 17/12/2020 |
Keywords
- Existential Theory of the Real Numbers
- ER-complete
- ETR
- Real RAM
- Computational Complexity
Fingerprint
Dive into the research topics of 'Smoothing the gap between NP and ER'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver