Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Cardinal Complexity of Comparison-based Online Algorithms   We consider ordinal online problems, i.e., those tasks that only depend on
the pairwise comparisons between elements in the input. E.g., the secretary
problem and the game of googol. The natural approach to these tasks is to use
ordinal online algorithms that at each step only consider relative ranking
among the arrived elements, without looking at the numerical values of the
input. We formally study the question of how cardinal algorithms (that can use
numerical values of the input) can improve upon ordinal algorithms.
  We give a universal construction of the input distribution for any ordinal
online problem, such that the advantage of the cardinal algorithms over the
ordinal algorithms is at most $1+\varepsilon$ for arbitrary small $\varepsilon>
0$. However, the value range of the input elements in this construction is
huge: $O\left(\frac{n^3\cdot n!}{\varepsilon}\right)\uparrow\uparrow (n-1)$ for
an input sequence of length $n$. Surprisingly, we also identify a natural
family of hardcore problems that achieve a matching advantage of $1+ \Omega
\left(\frac{1}{\log^{(c)}N}\right),$ where $\log^{(c)}N=\log\log\ldots\log N$
with $c$ iterative logs and $c$ is an arbitrary constant $c\le n-2$. We also
consider a simpler variant of the hardcore problem, which we call maximum
guessing and is closely related to the game of googol. We provide a much more
efficient construction with cardinal complexity
$O\left(\frac{1}{\varepsilon}\right)^{n-1}$ for this easier task. Finally, we
study the dependency on $n$ of the hardcore problem. We provide an efficient
construction of size $O(n)$, if we allow cardinal algorithms to have constant
factor advantage against ordinal algorithms.

14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th
15
The categories of this paper are: nucl-ex
22
The categories of this paper are: chao-dyn
9
The categories of this paper are: nlin
34
The categories of this paper are: chem-ph
8
The categories of this paper are: hep-ex
24
The categories of this paper are: dg-ga
4
The categories of this paper are: cond-mat
18
The categories of this paper are: econ
10
The categories of this paper are: q-bio
31
The categories of this paper are: ao-sci
28
The categories of this paper are: alg-geom
20
The categories of this paper are: acc-phys
13
The categories of this paper are: quant-ph
29
The categories of this paper are: funct-an