Compression for data archiving and backup revisited
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Our computational model is a random access machine with n read only input registers each containing c log n bits of information and a read and write memory. We measure the time by the number of accesses to the input registers. We show that for all k there is an ε > 0 so that if n is sufficiently large then the elements distinctness problem cannot be solved in time kn with en bits of read and write memory; that is, there is no machine with this value of the parameters which decides whether there are two different input registers whose contents are identical. © 2002 Elsevier Science (USA) All rights reserved.
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Imran Nasim, Michael E. Henderson
Mathematics