Vi undersöker optimaliteten av (1+ ) - approximation algoritmer som erhållits via dimensionality reduktion metod. Vi visar att: • Alla datastruktur för (1 + )-ungefärliga närmaste granne problem i Hamming utrymme, som använder konstant antal sonder för att svara på varje fråga, måste använda n 2 ) utrymme. • Varje algoritm för (1 + )-ungefärligt närmaste substring problem måste köras i tid exponentiellt i 1/ 2−γ för alla γ > 0 (om inte 3SAT kan lösas i subexponentiell tid) Båda nedre gränser är (i huvudsak) tight.
Andoni, Indyk och P-traşcu REF visar att för små > 0, alla O(1)-probe algoritm för (1 + )-ungefärlig nära granne problem måste använda utrymme n  på 1 2 ).
On the Optimality of the Dimensionality Reduction Method
{'venue': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'journal': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'mag_field_of_study': ['Mathematics', 'Computer Science']}