Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Sublinear-time Reductions for Big Data Computing   With the rapid popularization of big data, the dichotomy between tractable
and intractable problems in big data computing has been shifted. Sublinear
time, rather than polynomial time, has recently been regarded as the new
standard of tractability in big data computing. This change brings the demand
for new methodologies in computational complexity theory in the context of big
data. Based on the prior work for sublinear-time complexity classes
\cite{DBLP:journals/tcs/GaoLML20}, this paper focuses on sublinear-time
reductions specialized for problems in big data computing. First, the
pseudo-sublinear-time reduction is proposed and the complexity classes
\Pproblem and \PsT are proved to be closed under it. To establish
\PsT-intractability for certain problems in \Pproblem, we find the first
problem in $\Pproblem \setminus \PsT$. Using the pseudo-sublinear-time
reduction, we prove that the nearest edge query is in \PsT but the algebraic
equation root problem is not. Then, the pseudo-polylog-time reduction is
introduced and the complexity class \PsPL is proved to be closed under it. The
\PsT-completeness under it is regarded as an evidence that some problems can
not be solved in polylogarithmic time after a polynomial-time preprocessing,
unless \PsT = \PsPL. We prove that all \PsT-complete problems are also
\Pproblem-complete, which gives a further direction for identifying
\PsT-complete problems.

0
The categories of this paper are: hep-ph
12
The categories of this paper are: nucl-th
4
The categories of this paper are: cond-mat
27
The categories of this paper are: comp-gas
14
The categories of this paper are: math-ph
19
The categories of this paper are: eess
5
The categories of this paper are: gr-qc
10
The categories of this paper are: q-bio
17
The categories of this paper are: q-fin
36
The categories of this paper are: cmp-lg
37
The categories of this paper are: supr-con
15
The categories of this paper are: nucl-ex
16
The categories of this paper are: stat
22
The categories of this paper are: chao-dyn
3
The categories of this paper are: physics
11
The categories of this paper are: hep-lat