Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Streaming Complexity of Checking Priority Queues   This work is in the line of designing efficient checkers for testing the
reliability of some massive data structures. Given a sequential access to the
insert/extract operations on such a structure, one would like to decide, a
posteriori only, if it corresponds to the evolution of a reliable structure. In
a context of massive data, one would like to minimize both the amount of
reliable memory of the checker and the number of passes on the sequence of
operations. Chu, Kannan and McGregor initiated the study of checking priority
queues in this setting. They showed that use of timestamps allows to check a
priority queue with a single pass and memory space O(N^(1/2)), up to a
polylogarithmic factor. Later, Chakrabarti, Cormode, Kondapally and McGregor
removed the use of timestamps, and proved that more passes do not help. We show
that, even in the presence of timestamps, more passes do not help, solving a
previously open problem. On the other hand, we show that a second pass, but in
reverse direction, shrinks the memory space to O((log N)^2), extending a
phenomenon the first time observed by Magniez, Mathieu and Nayak for checking
well-parenthesized expressions.

25
The categories of this paper are: patt-sol
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
21
The categories of this paper are: adap-org
13
The categories of this paper are: quant-ph
9
The categories of this paper are: nlin
7
The categories of this paper are: hep-th
37
The categories of this paper are: supr-con
3
The categories of this paper are: physics
19
The categories of this paper are: eess
20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
34
The categories of this paper are: chem-ph