Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConvex Hull of Arithmetic Automata
265
0
0.0
(
0
)
Added by
Jerome Leroux
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Jer^ome Leroux
Ask ChatGPT about the research
No Arabic abstract
Arithmetic automata recognize infinite words of digits denoting decompositions of real and integer vectors. These automata are known expressive and efficient enough to represent the whole set of solutions of complex linear constraints combining both integral and real variables. In this paper, the closed convex hull of arithmetic automata is proved rational polyhedral. Moreover an algorithm computing the linear constraints defining these convex set is provided. Such an algorithm is useful for effectively extracting geometrical properties of the whole set of solutions of complex constraints symbolically represented by arithmetic automata.
rate research
Read More
We study the question of how to compute a point in the convex hull of an input set $S$ of $n$ points in ${mathbb R}^d$ in a differentially private manner. This question, which is trivial non-privately, turns out to be quite deep when imposing differential privacy. In particular, it is known that the input points must reside on a fixed finite subset $Gsubseteq{mathbb R}^d$, and furthermore, the size of $S$ must grow with the size of $G$. Previous works focused on understanding how $n$ needs to grow with $|G|$, and showed that $n=Oleft(d^{2.5}cdot8^{log^*|G|}right)$ suffices (so $n$ does not have to grow significantly with $|G|$). However, the available constructions exhibit running time at least $|G|^{d^2}$, where typically $|G|=X^d$ for some (large) discretization parameter $X$, so the running time is in fact $Omega(X^{d^3})$. In this paper we give a differentially private algorithm that runs in $O(n^d)$ time, assuming that $n=Omega(d^4log X)$. To get this result we study and exploit some structural properties of the Tukey levels (the regions $D_{ge k}$ consisting of points whose Tukey depth is at least $k$, for $k=0,1,...$). In particular, we derive lower bounds on their volumes for point sets $S$ in general position, and develop a rather subtle mechanism for handling point sets $S$ in degenerate position (where the deep Tukey regions have zero volume). A naive approach to the construction of the Tukey regions requires $n^{O(d^2)}$ time. To reduce the cost to $O(n^d)$, we use an approximation scheme for estimating the volumes of the Tukey regions (within their affine spans in case of degeneracy), and for sampling a point from such a region, a scheme that is based on the volume estimation framework of Lovasz and Vempala (FOCS 2003) and of Cousins and Vempala (STOC 2015). Making this framework differentially private raises a set of technical challenges that we address.
Given a finite set of points $P subseteq mathbb{R}^d$, we would like to find a small subset $S subseteq P$ such that the convex hull of $S$ approximately contains $P$. More formally, every point in $P$ is within distance $epsilon$ from the convex hull of $S$. Such a subset $S$ is called an $epsilon$-hull. Computing an $epsilon$-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many real world applications, the set $P$ is too large to fit in memory. We consider the streaming model where the algorithm receives the points of $P$ sequentially and strives to use a minimal amount of memory. Existing streaming algorithms for computing an $epsilon$-hull require $O(epsilon^{-(d-1)/2})$ space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an $epsilon$-hull of $P$, which we denote by $text{OPT}$, can be much smaller. A natural question is whether a streaming algorithm can compute an $epsilon$-hull using only $O(text{OPT})$ space. We begin with lower bounds that show that it is not possible to have a single-pass streaming algorithm that computes an $epsilon$-hull with $O(text{OPT})$ space. We instead propose three relaxations of the problem for which we can compute $epsilon$-hulls using space near-linear to the optimal size. Our first algorithm for points in $mathbb{R}^2$ that arrive in random-order uses $O(log ncdot text{OPT})$ space. Our second algorithm for points in $mathbb{R}^2$ makes $O(log(frac{1}{epsilon}))$ passes before outputting the $epsilon$-hull and requires $O(text{OPT})$ space. Our third algorithm for points in $mathbb{R}^d$ for any fixed dimension $d$ outputs an $epsilon$-hull for all but $delta$-fraction of directions and requires $O(text{OPT} cdot log text{OPT})$ space.
A subset $A$ of a Banach space is called Banach-Saks when every sequence in $A$ has a Ces{`a}ro convergent subsequence. Our interest here focusses on the following problem: is the convex hull of a Banach-Saks set again Banach-Saks? By means of a combinatorial argument, we show that in general the answer is negative. However, sufficient conditions are given in order to obtain a positive result.
We describe convex hulls of the simplest compact space curves, reducible quartics consisting of two circles. When the circles do not meet in complex projective space, their algebraic boundary contains an irrational ruled surface of degree eight whose ruling forms a genus one curve. We classify which curves arise, classify the face lattices of the convex hulls, and determine which are spectrahedra. We also discuss an approach to these convex hulls using projective duality.
High-throughput computational materials searches generate large databases of locally-stable structures. Conventionally, the needle-in-a-haystack search for the few experimentally-synthesizable compounds is performed using a convex hull construction, which identifies structures stabilized by manipulation of a particular thermodynamic constraint (for example pressure or composition) chosen based on prior experimental evidence or intuition. To address the biased nature of this procedure we introduce a generalized convex hull framework. Convex hulls are constructed on data-driven principal coordinates, which represent the full structural diversity of the database. Their coupling to experimentally-realizable constraints hints at the conditions that are most likely to stabilize a given configuration. The probabilistic nature of our framework also addresses the uncertainty stemming from the use of approximate models during database construction, and eliminates redundant structures. The remaining small set of candidates that have a high probability of being synthesizable provide a much needed starting point for the determination of viable synthetic pathways.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
