naa a22 4500 510782906 CHVBK 20180411083253.0 cr unu---uuuuu 180411e20130601xx s 000 0 eng 10.1007/s11856-012-0137-6 doi (NATIONALLICENCE)springer-10.1007/s11856-012-0137-6 Regev Oded Blavatnik School of Computer Science, Tel Aviv University, Ramat Aviv, 69978, Tel Aviv, Israel aut Entropy-based bounds on dimension reduction in L 1 [Elektronische Daten] [Oded Regev] We show that for every large enough integer N, there exists an N-point subset of L 1 such that for every D > 1, embedding it into ℓ 1 d with distortion D requires dimension d at least $${N^{\Omega (1/{D^2})}}$$ , and that for every ɛ > 0 and large enough integer N, there exists an N-point subset of L 1 such that embedding it into ℓ 1 d with distortion 1 + ɛ requires dimension d at least $${N^{\Omega (1/{D^2})}}$$ ). These results were previously proven by Brinkman and Charikar [JACM, 2005] and by Andoni, Charikar, Neiman and Nguyen [FOCS 2011]. We provide an alternative and arguably more intuitive proof based on an entropy argument. Hebrew University Magnes Press, 2013 Israel Journal of Mathematics Springer US; http://www.springer-ny.com 195/2(2013-06-01), 825-832 0021-2172 195:2<825 2013 195 11856 https://doi.org/10.1007/s11856-012-0137-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11856-012-0137-6 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Regev Oded Blavatnik School of Computer Science, Tel Aviv University, Ramat Aviv, 69978, Tel Aviv, Israel aut NATIONALLICENCE 773 0- Israel Journal of Mathematics Springer US; http://www.springer-ny.com 195/2(2013-06-01), 825-832 0021-2172 195:2<825 2013 195 11856 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer