{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:06:35Z","timestamp":1768028795154,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,9,26]],"date-time":"2008-09-26T00:00:00Z","timestamp":1222387200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,12]]},"DOI":"10.1007\/s00454-008-9110-x","type":"journal-article","created":{"date-parts":[[2008,9,25]],"date-time":"2008-09-25T19:11:31Z","timestamp":1222369891000},"page":"615-630","source":"Crossref","is-referenced-by-count":90,"title":["Fast Dimension Reduction Using Rademacher Series on\u00a0Dual BCH Codes"],"prefix":"10.1007","volume":"42","author":[{"given":"Nir","family":"Ailon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edo","family":"Liberty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,9,26]]},"reference":[{"key":"9110_CR1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26, 189\u2013206 (1984)","journal-title":"Contemp. Math."},{"key":"9110_CR2","doi-asserted-by":"crossref","unstructured":"Ailon, N., Chazelle, B.: Approximate nearest neighbors and the fast Johnson\u2013Lindenstrauss transform. In: Proceedings of the 38st Annual Symposium on the Theory of Compututing (STOC), pp. 557\u2013563. Seattle, WA (2006)","DOI":"10.1145\/1132516.1132597"},{"key":"9110_CR3","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P. Frankl","year":"1987","unstructured":"Frankl, P., Maehara, H.: The Johnson\u2013Lindenstrauss lemma and the sphericity of some graphs. J.\u00a0Combin. Theory Ser. A 44, 355\u2013362 (1987)","journal-title":"J.\u00a0Combin. Theory Ser. A"},{"key":"9110_CR4","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"9110_CR5","unstructured":"Matousek, J.: On variants of the Johnson\u2013Lindenstrauss lemma. Private communication (2006)"},{"issue":"2","key":"9110_CR6","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/S0097539798347177","volume":"30","author":"E. Kushilevitz","year":"2000","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput. 30(2), 457\u2013474 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9110_CR7","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn. 2(4), 285\u2013318 (1988)","journal-title":"Mach. Learn."},{"key":"9110_CR8","doi-asserted-by":"crossref","unstructured":"Arriaga, R.I., Vempala, S.: An algorithmic theory of learning: Robust concepts and random projection. In: FOCS \u201999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.\u00a0616. Washington, DC, USA, IEEE Computer Society (1999)","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"9110_CR9","doi-asserted-by":"crossref","unstructured":"Indyk, P.: On approximate nearest neighbors in non-Euclidean spaces. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 148\u2013155 (1998)","DOI":"10.1109\/SFCS.1998.743438"},{"key":"9110_CR10","doi-asserted-by":"crossref","unstructured":"Vempala, S.: The Random Projection Method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (2004)","DOI":"10.1090\/dimacs\/065"},{"key":"9110_CR11","doi-asserted-by":"crossref","unstructured":"Sarl\u00f3s, T.: Improved approximation algorithms for large matrices via random projections. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Berkeley, CA (2006)","DOI":"10.1109\/FOCS.2006.37"},{"key":"9110_CR12","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: A replacement for Voronoi diagrams of near linear size. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 94\u2013103. Las Vegas, Nevada, USA (2001)","DOI":"10.1109\/SFCS.2001.959884"},{"issue":"1\u20133","key":"9110_CR13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N. Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics I. Discrete Math. 273(1\u20133), 31\u201353 (2003)","journal-title":"Discrete Math."},{"key":"9110_CR14","unstructured":"Sudan, M.: Essential coding theory (class notes)"},{"key":"9110_CR15","doi-asserted-by":"crossref","unstructured":"Khot, S.: Hardness of approximating thee shortest vector problem in lattices. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2004)","DOI":"10.1109\/FOCS.2004.31"},{"issue":"2","key":"9110_CR16","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N. Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005)","journal-title":"J. ACM"},{"key":"9110_CR17","unstructured":"Razborov, A.A.: Expander codes and somewhat Euclidean sections in \u2113 1 n . ECCC (2007)"},{"key":"9110_CR18","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Uncertainty principles, extractors, and explicit embeddings of l2 into l1. In: Proceedings of the 39th Annual ACM Symposium on the Theory of Computing (2007)","DOI":"10.1145\/1250790.1250881"},{"issue":"34","key":"9110_CR19","first-page":"67","volume":"1","author":"S. Artstein-Avidan","year":"2004","unstructured":"Artstein-Avidan, S., Milman, V.: Logarithmic reduction of the level of randomness in some probabilistic geometric constructions. SIAM J. Comput. 1(34), 67\u201388 (2004)","journal-title":"SIAM J. Comput."},{"key":"9110_CR20","doi-asserted-by":"crossref","unstructured":"Frieze, A.M., Kannan, R., Vempala, S.: Fast Monte-Carlo algorithms for finding low-rank approximations. In: IEEE Symposium on Foundations of Computer Science, pp. 370\u2013378 (1998)","DOI":"10.1109\/SFCS.1998.743487"},{"key":"9110_CR21","doi-asserted-by":"crossref","unstructured":"Drineas, P., Kannan, R.: Fast Monte-Carlo algorithms for approximate matrix multiplication. In: IEEE Symposium on Foundations of Computer Science, pp. 452\u2013459 (2001)","DOI":"10.1109\/SFCS.2001.959921"},{"key":"9110_CR22","unstructured":"Drineas, P., Kannan, R., Mahoney, M.: Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix (2004)"},{"key":"9110_CR23","unstructured":"Drineas, P., Kannan, R., Mahoney, M.: Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition (2004)"},{"key":"9110_CR24","unstructured":"Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Yale Computer Science Technical Reports, YALE\/DCS\/TR1380 (2007)"},{"key":"9110_CR25","unstructured":"Drineas, P., Mahoney, M.W., Muthukrishnan, S., Sarlos, T.: Faster least squares approximation. http:\/\/arxiv.org\/abs\/0710.1435 (2007)"},{"key":"9110_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-66451-9","volume-title":"Interpolation Spaces","author":"J. Bergh","year":"1976","unstructured":"Bergh, J., Lofstrom, J.: Interpolation Spaces. Springer, Berlin (1976)"},{"key":"9110_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20212-4","volume-title":"Probability in Banach Spaces: Isoperimetry and Processes","author":"M. Ledoux","year":"1991","unstructured":"Ledoux, M., Talagrand, M.: Probability in Banach Spaces: Isoperimetry and Processes. Springer, Berlin (1991)"},{"key":"9110_CR28","volume-title":"The Theory of Error Correcting Codes","author":"F.J. MacWilliams","year":"1983","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland, Amsterdam (1983)"},{"key":"9110_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/crll.1999.511.1","volume":"511","author":"C.S.H. K\u00f6nig","year":"1999","unstructured":"K\u00f6nig, C.S.H., Jaegermann, N.T.: Projection constants of symmetric spaces and variants of Khintchine\u2019s inequality. J. Reine Angew. Math. 511, 1\u201342 (1999)","journal-title":"J. Reine Angew. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9110-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-008-9110-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9110-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:35Z","timestamp":1559087255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-008-9110-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,26]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9110"],"URL":"https:\/\/doi.org\/10.1007\/s00454-008-9110-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9,26]]}}}