Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 52 Issue 5, September 2005

Frontier search
Richard E. Korf, Weixiong Zhang, Ignacio Thayer, Heath Hohwald
Pages: 715-748
DOI: 10.1145/1089023.1089024
The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the...

Lattice problems in NP ∩ coNP
Dorit Aharonov, Oded Regev
Pages: 749-765
DOI: 10.1145/1089023.1089025
We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of &nradic; lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice...

On the impossibility of dimension reduction in l1
Bo Brinkman, Moses Charikar
Pages: 766-788
DOI: 10.1145/1089023.1089026
The Johnson--Lindenstrauss lemma shows that any n points in Euclidean space (i.e., ℝn with distances measured under the ℓ2 norm) may be mapped down to O((log n)/ε2)...

Hardness of approximating the shortest vector problem in lattices
Subhash Khot
Pages: 789-808
DOI: 10.1145/1089023.1089027
Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓp norm within a constant factor. Under the stronger...

Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data
Matthew Andrews, Lisa Zhang
Pages: 809-834
DOI: 10.1145/1089023.1089028
In a wireless network, a basestation transmits data to mobiles at time-varying, mobile-dependent rates due to the ever changing nature of the communication channels. In this article, we consider a wireless system in which the channel...