Yi Zhou, Parikshit Ram, et al.
ICLR 2023
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.
Yi Zhou, Parikshit Ram, et al.
ICLR 2023
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Leo Liberti, James Ostrowski
Journal of Global Optimization