On the Optimality of the Dimensionality Reduction Method

Berkeley, California October 21-October 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.56

47th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Alexandr Andoni Articles by Piotr Indyk Articles by Mihai Patrascu

	ASCII Text	x
	Alexandr Andoni, Piotr Indyk, Mihai Patrascu, "On the Optimality of the Dimensionality Reduction Method," Foundations of Computer Science, Annual IEEE Symposium on, pp. 449-458, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.

	BibTex	x
	@article{ 10.1109/FOCS.2006.56, author = {Alexandr Andoni and Piotr Indyk and Mihai Patrascu}, title = {On the Optimality of the Dimensionality Reduction Method}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2006}, issn = {0272-5428}, pages = {449-458}, doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.56}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - On the Optimality of the Dimensionality Reduction Method SN - 0272-5428 SP449 EP458 A1 - Alexandr Andoni, A1 - Piotr Indyk, A1 - Mihai Patrascu, PY - 2006 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Alexandr Andoni, M.I.T., USA

Piotr Indyk, M.I.T., USA

Mihai Patrascu, M.I.T., USA

We investigate the optimality of (1+\in )-approximation algorithms obtained via the dimensionality reduction method. We show that:

--Any data structure for the (1+\in )-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^{\Omega \left( {1/ \in ^2 } \right)} space.

--Any algorithm for the (1+\in )-approximate closest substring problem must run in time exponential in 1/ \in ^{2 - \gamma } for any \gamma > 0 (unless 3SAT can be solved in subexponential time)

Both lower bounds are (essentially) tight.

Citation:

Alexandr Andoni, Piotr Indyk, Mihai Patrascu, "On the Optimality of the Dimensionality Reduction Method," focs, pp.449-458, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.