Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on self-improving sorting with hidden partitions
437
0
0.0
(
0
)
Added by
Kai Jin
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study self-improving sorting with hidden partitions. Our result is an optimal algorithm which runs in expected time O(H(pi(I)) + n), where I is the given input which contains n elements to be sorted, pi(I) is the output which are the ranks of all element in I, and H(pi(I)) denotes the entropy of the output.
rate research
Read More
Ailon et al. [SICOMP11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,cdots,x_n$ follow some unknown emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $mathsf{D}_i$, and the $x_i$s are drawn independently. After spending $O(n^{1+varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/varepsilon)$, where $H in {H_mathrm{S},H_mathrm{DT}}$, and $H_mathrm{S}$ and $H_mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$s under the emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$s are well-behaved. After an $O(mathrm{poly}(n))$-time training phase, we achieve $O(n + H_mathrm{S})$ and $O(nalpha(n) + H_mathrm{DT})$ expected running times for sorting and DT, respectively, where $alpha(cdot)$ is the inverse Ackermann function.
The construction of an unbounded polyhedron from a jagged convex cap is described, and several of its properties discussed, including its relation to Alexandrovs limit angle.
Taxonomies have been widely used in various machine learning and text mining systems to organize knowledge and facilitate downstream tasks. One critical challenge is that, as data and business scope grow in real applications, existing taxonomies need to be expanded to incorporate new concepts. Previous works on taxonomy expansion process the new concepts independently and simultaneously, ignoring the potential relationships among them and the appropriate order of inserting operations. However, in reality, the new concepts tend to be mutually correlated and form local hypernym-hyponym structures. In such a scenario, ignoring the dependencies of new concepts and the order of insertion may trigger error propagation. For example, existing taxonomy expansion systems may insert hyponyms to existing taxonomies before their hypernym, leading to sub-optimal expanded taxonomies. To complement existing taxonomy expansion systems, we propose TaxoOrder, a novel self-supervised framework that simultaneously discovers the local hypernym-hyponym structure among new concepts and decides the order of insertion. TaxoOrder can be directly plugged into any taxonomy expansion system and improve the quality of expanded taxonomies. Experiments on the real-world dataset validate the effectiveness of TaxoOrder to enhance taxonomy expansion systems, leading to better-resulting taxonomies with comparison to baselines under various evaluation metrics.
Let $T(d,r) = (r-1)(d+1)+1$ be the parameter in Tverbergs theorem, and call a partition $mathcal I$ of ${1,2,ldots,T(d,r)}$ into $r$ parts a Tverberg type. We say that $mathcal I$ occurs in an ordered point sequence $P$ if $P$ contains a subsequence $P$ of $T(d,r)$ points such that the partition of $P$ that is order-isomorphic to $mathcal I$ is a Tverberg partition. We say that $mathcal I$ is unavoidable if it occurs in every sufficiently long point sequence. In this paper we study the problem of determining which Tverberg types are unavoidable. We conjecture a complete characterization of the unavoidable Tverberg types, and we prove some cases of our conjecture for $dle 4$. Along the way, we study the avoidability of many other geometric predicates. Our techniques also yield a large family of $T(d,r)$-point sets for which the number of Tverberg partitions is exactly $(r-1)!^d$. This lends further support for Sierksmas conjecture on the number of Tverberg partitions.
Nicolas and DeSalvo and Pak proved that the partition function $p(n)$ is log concave for $n geq 25$. Chen, Jia and Wang proved that $p(n)$ satisfies the third order Tur{a}n inequality, and that the associated degree 3 Jensen polynomials are hyperbolic for $n geq 94$. More recently, Griffin, Ono, Rolen and Zagier proved more generally that for all $d$, the degree $d$ Jensen polynomials associated to $p(n)$ are hyperbolic for sufficiently large $n$. In this paper, we prove that the same result holds for the $k$-regular partition function $p_k(n)$ for $k geq 2$. In particular, for any positive integers $d$ and $k$, the order $d$ Tur{a}n inequalities hold for $p_k(n)$ for sufficiently large $n$. The case when $d = k = 2$ proves a conjecture by Neil Sloane that $p_2(n)$ is log concave.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
