Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Reinier F. Schmiermann

dblp:294/5077 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 50% Computational geometry · 50%

Topics — the 2 heaviest of 2, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › decision problems
existential theory of the reals
0.512021
On Classifying Continuous Constraint Satisfaction problems · FOCS 2021
Computational geometry › packing and covering
geometric packing
0.512021
On Classifying Continuous Constraint Satisfaction problems · FOCS 2021

Methods — techniques the papers use, named apart from their topics

real RAM computation · 0.5polynomial-time many-one reduction · 0.5
YearPublicationVenuePosition
2021 On Classifying Continuous Constraint Satisfaction problems
abstract
A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain$U\subset \mathbb{R}$. We engage in a systematic study to classify CCSPs that are complete of the Existential Theory of the Reals, i.e.,$\exists \mathbb{R}$-complete. To define this class, we first consider the problem ETR, which also stands for Existential Theory of the Reals. In an instance of this problem we are given some sentence of the form$\exists x_{1}, \ldots, x_{n}\in \mathbb{R}$:$\Phi(x_{1},\ldots,\ x_{n})$, where$\Phi$is a well-formed quantifier-free formula consisting of the symbols$\{0,1,\ x_{1},\ldots,\ x_{n},\ +,\ \cdot,\ \geq,\ >, \ \wedge,\ \vee,\ \neg\}$, the goal is to check whether this sentence is true. Now the class$\exists \mathbb{R}$is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP$\subseteq\exists \mathbb{R}\subseteq$PSPACE. We restrict our attention on CCSPs with addition constraints$(x+y=z)$and some other mild technical condition. Previously, it was shown that multiplication constraints$(x\cdot y=z)$, squaring constraints$(x^{2}=y)$, or inversion constraints$(x\cdot y=1)$are sufficient to establish$\exists \mathbb{R}$-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical condition) that have any one well-behaved curved equality constraint$(f(x,\ y)=0)$are$\exists \mathbb{R}$-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint$(f(x,\ y)\geq 0$and$g(x,\ y)\geq 0)$imply$\exists \mathbb{R}$-completeness on the class of such CCSPs. Here, we call a function$f: U^{2}\rightarrow\mathbb{R}$well-behaved if it is a$C^{2}$-function,$f(0,0)=0$, all its partial derivatives$f_{x}, f_{y}, f$are rational in$(0,0), f_{x}(0,0)\neq 0$or$f_{y}(0,0)\neq 0$, and it can be computed on a real RAM. Furthermore we call$f$curved if the curvature of the curve given by$f(x,\ y)=0$is nonzero, at the origin. In this case we call$f$either convexly curved if the curvature is negative, or concavely curved if it is positive. We apply our findings to geometric packing and answer an open question by Abrahamsen et al. [1, FOCS 2020]. Namely, we establish$\exists\mathbb{R}$-completeness of packing convex pieces into a square container under rotations and translations. This work is based on the master's thesis of the second author [2]. The full version of this paper can be found on arXiv [3].
Tillmann Miltzow, Reinier F. Schmiermann
FOCS2