enter search term and/or author name
Richard E. Korf, Weixiong Zhang, Ignacio Thayer, Heath Hohwald
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
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
The Johnson--Lindenstrauss lemma shows that any n points in Euclidean space (i.e., ℝn with distances measured under the ℓ
Hardness of approximating the shortest vector problem in lattices
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 ℓ
Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data
Matthew Andrews, Lisa Zhang
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...