Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Selection in the Presence of Memory Faults, with Applications to
  In-place Resilient Sorting   The selection problem, where one wishes to locate the $k^{th}$ smallest
element in an unsorted array of size $n$, is one of the basic problems studied
in computer science. The main focus of this work is designing algorithms for
solving the selection problem in the presence of memory faults. These can
happen as the result of cosmic rays, alpha particles, or hardware failures.
  Specifically, the computational model assumed here is a faulty variant of the
RAM model (abbreviated as FRAM), which was introduced by Finocchi and Italiano.
In this model, the content of memory cells might get corrupted adversarially
during the execution, and the algorithm is given an upper bound $\delta$ on the
number of corruptions that may occur.
  The main contribution of this work is a deterministic resilient selection
algorithm with optimal O(n) worst-case running time. Interestingly, the running
time does not depend on the number of faults, and the algorithm does not need
to know $\delta$.
  The aforementioned resilient selection algorithm can be used to improve the
complexity bounds for resilient $k$-d trees developed by Gieseke, Moruz and
Vahrenhold. Specifically, the time complexity for constructing a $k$-d tree is
improved from $O(n\log^2 n + \delta^2)$ to $O(n \log n)$.
  Besides the deterministic algorithm, a randomized resilient selection
algorithm is developed, which is simpler than the deterministic one, and has
$O(n + \alpha)$ expected time complexity and O(1) space complexity (i.e., is
in-place). This algorithm is used to develop the first resilient sorting
algorithm that is in-place and achieves optimal $O(n\log n + \alpha\delta)$
expected running time.

3
The categories of this paper are: physics
18
The categories of this paper are: econ
29
The categories of this paper are: funct-an
21
The categories of this paper are: adap-org
19
The categories of this paper are: eess
36
The categories of this paper are: cmp-lg
27
The categories of this paper are: comp-gas
9
The categories of this paper are: nlin
25
The categories of this paper are: patt-sol
20
The categories of this paper are: acc-phys
31
The categories of this paper are: ao-sci
7
The categories of this paper are: hep-th
8
The categories of this paper are: hep-ex
28
The categories of this paper are: alg-geom
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg