{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T19:26:31Z","timestamp":1730316391573,"version":"3.28.0"},"publisher-location":"New York, NY, USA","reference-count":68,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6,22]]},"DOI":"10.1145\/2463664.2465217","type":"proceedings-article","created":{"date-parts":[[2013,6,25]],"date-time":"2013-06-25T19:13:21Z","timestamp":1372187601000},"page":"87-90","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sketching via hashing"],"prefix":"10.1145","author":[{"given":"Piotr","family":"Indyk","sequence":"first","affiliation":[{"name":"MIT, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2013,6,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/1646353.1646379"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.5555\/946243.946355"},{"key":"e_1_3_2_1_3_1","first-page":"381","volume-title":"COLT","author":"Akavia A.","year":"2010","unstructured":"A. Akavia . Deterministic sparse Fourier approximation via fooling arithmetic progressions . COLT , pages 381 -- 393 , 2010 . A. Akavia. Deterministic sparse Fourier approximation via fooling arithmetic progressions. COLT, pages 381--393, 2010."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.5555\/2133036.2133053"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1007\/978-3-642-32512-0_6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1109\/ALLERTON.2008.4797639"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1109\/ALLERTON.2008.4797556"},{"key":"e_1_3_2_1_8_1","volume-title":"Sho-fa: Robust compressive sensing with order-optimal complexity, measurements, and bits. arXiv preprint arXiv:1207.2335","author":"Bakshi Mayank","year":"2012","unstructured":"Mayank Bakshi , Sidharth Jaggi , Sheng Cai , and Minghua Chen . Sho-fa: Robust compressive sensing with order-optimal complexity, measurements, and bits. arXiv preprint arXiv:1207.2335 , 2012 . Mayank Bakshi, Sidharth Jaggi, Sheng Cai, and Minghua Chen. Sho-fa: Robust compressive sensing with order-optimal complexity, measurements, and bits. arXiv preprint arXiv:1207.2335, 2012."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_3_2_1_10_1","volume-title":"Rademacher chaos, random eulerian graphs and the sparse Johnson-Lindenstrauss transform. arXiv preprint arXiv:1011.2590","author":"Braverman Vladimir","year":"2010","unstructured":"Vladimir Braverman , Rafail Ostrovsky , and Yuval Rabani . Rademacher chaos, random eulerian graphs and the sparse Johnson-Lindenstrauss transform. arXiv preprint arXiv:1011.2590 , 2010 . Vladimir Braverman, Rafail Ostrovsky, and Yuval Rabani. Rademacher chaos, random eulerian graphs and the sparse Johnson-Lindenstrauss transform. arXiv preprint arXiv:1011.2590, 2010."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.5555\/646255.684566"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1137\/1.9781611973105.31"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1145\/872757.872787"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1145\/773153.773182"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1007\/978-3-540-24698-5_7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1007\/11780823_22"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1002\/cpa.20124"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1109\/TIT.2006.885507"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/2488608.2488620"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.5555\/1873601.1873696"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1145\/1806689.1806737"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1109\/TIT.2006.871582"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1145\/633025.633056"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1145\/285237.285287"},{"key":"e_1_3_2_1_25_1","volume-title":"The gelfand widths of lp-balls for 0 <","author":"Foucart S.","year":"2010","unstructured":"S. Foucart , A. Pajor , H. Rauhut , and T. Ullrich . The gelfand widths of lp-balls for 0 < p \u0142eq 1. preprint, 2010 . S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich. The gelfand widths of lp-balls for 0 < p \u0142eq 1. preprint, 2010."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.5555\/645924.671338"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1145\/509907.509933"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/509907.509966"},{"key":"e_1_3_2_1_29_1","volume-title":"Sample-optimal average-case sparse fourier transform in two dimensions. arXiv preprint arXiv:1303.1209","author":"Ghazi Badih","year":"2013","unstructured":"Badih Ghazi , Haitham Hassanieh , Piotr Indyk , Dina Katabi , Eric Price , and Lixin Shi . Sample-optimal average-case sparse fourier transform in two dimensions. arXiv preprint arXiv:1303.1209 , 2013 . Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi. Sample-optimal average-case sparse fourier transform in two dimensions. arXiv preprint arXiv:1303.1209, 2013."},{"key":"e_1_3_2_1_30_1","volume-title":"Sparse recovery using sparse matrices","author":"Gilbert A.","year":"2010","unstructured":"A. Gilbert and P. Indyk . Sparse recovery using sparse matrices . Proceedings of IEEE , 2010 . A. Gilbert and P. Indyk. Sparse recovery using sparse matrices. Proceedings of IEEE, 2010."},{"key":"e_1_3_2_1_31_1","volume-title":"Ramesh Raskar. Workshop on sparse Fourier transform etc. http:\/\/groups.csail.mit.edu\/ netmit\/sFFT\/workshop.html","author":"Gilbert Anna","year":"2013","unstructured":"Anna Gilbert , Piotr Indyk , Dina Katabi , and Ramesh Raskar. Workshop on sparse Fourier transform etc. http:\/\/groups.csail.mit.edu\/ netmit\/sFFT\/workshop.html , 2013 . Anna Gilbert, Piotr Indyk, Dina Katabi, and Ramesh Raskar. Workshop on sparse Fourier transform etc. http:\/\/groups.csail.mit.edu\/ netmit\/sFFT\/workshop.html, 2013."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1145\/73007.73010"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1145\/1806689.1806755"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1109\/Allerton.2011.6120248"},{"key":"e_1_3_2_1_35_1","volume-title":"SPIE Conference","author":"Gilbert A.","year":"2005","unstructured":"A. Gilbert , M. Muthukrishnan , and M. Strauss . Improved time bounds for near-optimal space Fourier representations . SPIE Conference , Wavelets , 2005 . A. Gilbert, M. Muthukrishnan, and M. Strauss. Improved time bounds for near-optimal space Fourier representations. SPIE Conference, Wavelets, 2005."},{"key":"e_1_3_2_1_36_1","first-page":"17","article-title":"Modern cryptography, probabilistic proofs and pseudorandomness","author":"Goldreich O.","year":"1999","unstructured":"O. Goldreich . Modern cryptography, probabilistic proofs and pseudorandomness . Algorithms and Combinatorics , 17 , 1999 . O. Goldreich. Modern cryptography, probabilistic proofs and pseudorandomness. Algorithms and Combinatorics, 17, 1999.","journal-title":"Algorithms and Combinatorics"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1137\/100785429"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1145\/1250790.1250824"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1145\/2213977.2214029"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.5555\/2095116.2095209"},{"key":"e_1_3_2_1_41_1","volume-title":"A sparse prony fft","author":"Heider Sabine","year":"2013","unstructured":"Sabine Heider , Stefan Kunis , Daniel Potts , and Michael Veit . A sparse prony fft . 2013 . Sabine Heider, Stefan Kunis, Daniel Potts, and Michael Veit. A sparse prony fft. 2013."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.5555\/1347082.1347086"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_43_1","DOI":"10.1109\/FOCS.2008.82"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1007\/s10208-009-9057-1"},{"key":"e_1_3_2_1_45_1","volume-title":"Applied And Computational Harmonic Analysis","author":"Iwen M.A.","year":"2012","unstructured":"M.A. Iwen . Improved approximation guarantees for sublinear-time Fourier algorithms . Applied And Computational Harmonic Analysis , 2012 . M.A. Iwen. Improved approximation guarantees for sublinear-time Fourier algorithms. Applied And Computational Harmonic Analysis, 2012."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1090\/conm\/026\/737400"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_47_1","DOI":"10.1109\/TIT.2009.2025528"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.1109\/TSP.2010.2082536"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_49_1","DOI":"10.1145\/103418.103466"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_50_1","DOI":"10.5555\/2095116.2095210"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1137\/100810447"},{"issue":"3","key":"e_1_3_2_1_52_1","first-page":"1102","article-title":"Randomness and non-determinism","volume":"58","author":"Levin L.A.","year":"1993","unstructured":"L.A. Levin . Randomness and non-determinism . J. Symb. Logic , 58 ( 3 ): 1102 -- 1103 , 1993 . L.A. Levin. Randomness and non-determinism. J. Symb. Logic, 58(3):1102--1103, 1993.","journal-title":"J. Symb. Logic"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.1145\/1375457.1375472"},{"key":"e_1_3_2_1_54_1","volume-title":"Adaptive sub-linear time Fourier algorithms. arXiv:1207.6368","author":"Lawlor D.","year":"2012","unstructured":"D. Lawlor , Y. Wang , and A. Christlieb . Adaptive sub-linear time Fourier algorithms. arXiv:1207.6368 , 2012 . D. Lawlor, Y. Wang, and A. Christlieb. Adaptive sub-linear time Fourier algorithms. arXiv:1207.6368, 2012."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_55_1","DOI":"10.5555\/646246.684842"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_56_1","DOI":"10.1145\/2488608.2488621"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_57_1","DOI":"10.1561\/9781933019604"},{"key":"e_1_3_2_1_58_1","volume-title":"Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. arXiv preprint arXiv:1211.1002","author":"Nelson Jelani","year":"2012","unstructured":"Jelani Nelson and Huy L Nguy\u00ean . Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. arXiv preprint arXiv:1211.1002 , 2012 . Jelani Nelson and Huy L Nguy\u00ean. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. arXiv preprint arXiv:1211.1002, 2012."},{"key":"e_1_3_2_1_59_1","volume-title":"New constructions of RIP matrices with fast multiplication and fewer rows. CoRR, abs\/1211.0986","author":"Nelson Jelani","year":"2012","unstructured":"Jelani Nelson , Eric Price , and Mary Wootters . New constructions of RIP matrices with fast multiplication and fewer rows. CoRR, abs\/1211.0986 , 2012 . Jelani Nelson, Eric Price, and Mary Wootters. New constructions of RIP matrices with fast multiplication and fewer rows. CoRR, abs\/1211.0986, 2012."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_60_1","DOI":"10.1109\/Allerton.2012.6483460"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_61_1","DOI":"10.1109\/CISS.2006.286463"},{"key":"e_1_3_2_1_62_1","volume-title":"IEEE International Symposium on Information Theory","author":"Sarvotham S.","year":"2006","unstructured":"S. Sarvotham , D. Baron , and R. G. Baraniuk . Sudocodes - fast measurement and reconstruction of sparse signals . IEEE International Symposium on Information Theory , 2006 . S. Sarvotham, D. Baron, and R. G. Baraniuk. Sudocodes - fast measurement and reconstruction of sparse signals. IEEE International Symposium on Information Theory, 2006."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_63_1","DOI":"10.1109\/TSP.2009.2027773"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_64_1","DOI":"10.5555\/1577069.1755873"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_65_1","DOI":"10.1145\/1553374.1553516"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_66_1","DOI":"10.1145\/1236360.1236403"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_67_1","DOI":"10.1109\/TIT.2010.2046199"},{"volume-title":"Efficient compressive sensing with determinstic guarantees using expander graphs","author":"Xu W.","unstructured":"W. Xu and B. Hassibi . Efficient compressive sensing with determinstic guarantees using expander graphs . IEEE Information W. Xu and B. Hassibi. Efficient compressive sensing with determinstic guarantees using expander graphs. IEEE Information","key":"e_1_3_2_1_68_1"}],"event":{"sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"acronym":"SIGMOD\/PODS'13","name":"SIGMOD\/PODS'13: International Conference on Management of Data","location":"New York New York USA"},"container-title":["Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2463664.2465217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:04:43Z","timestamp":1703185483000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2463664.2465217"}},"subtitle":["from heavy hitters to compressed sensing to sparse fourier transform"],"short-title":[],"issued":{"date-parts":[[2013,6,22]]},"references-count":68,"alternative-id":["10.1145\/2463664.2465217","10.1145\/2463664"],"URL":"https:\/\/doi.org\/10.1145\/2463664.2465217","relation":{},"subject":[],"published":{"date-parts":[[2013,6,22]]},"assertion":[{"value":"2013-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}