{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T20:13:27Z","timestamp":1789848807392,"version":"4.0.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1145\/2488608.2488694","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"675-684","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["The approximate rank of a matrix and its algorithmic applications"],"prefix":"10.1145","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Troy","family":"Lee","sequence":"additional","affiliation":[{"name":"Centre for Quantum Technologies, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adi","family":"Shraibman","sequence":"additional","affiliation":[{"name":"Academic college of Tel Aviv, Yaffo, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[{"name":"Georgia Tech, Atlanta, Georgia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"FOCS","author":"Aaronson S.","year":"2003","unstructured":"S. Aaronson and A. Ambainis , Quantum Search of Spatial Regions,Proc . FOCS 2003 , 200--209. S. Aaronson and A. Ambainis, Quantum Search of Spatial Regions,Proc. FOCS 2003, 200--209."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008917"},{"key":"e_1_3_2_1_3_1","volume-title":"Manuscript","author":"Alon N.","year":"2011","unstructured":"N. Alon , S. Arora , R. Manokaran , D. Moshkovitz and O. Weinstein, On the inapproximability of the densestk-subgraph problem . Manuscript , 2011 . N. Alon, S. Arora, R. Manokaran, D. Moshkovitz andO. Weinstein, On the inapproximability of the densestk-subgraph problem. Manuscript, 2011."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.30"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00008-4"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.11"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method,%","author":"Alon N.","year":"2008","unstructured":"N. Alon and J. H. Spencer , The Probabilistic Method,% Third Edition,%Wiley, 2008 , xv 352 pp. N. Alon and J. H. Spencer, The Probabilistic Method,%Third Edition,%Wiley, 2008, xv 352 pp."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103439"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-6265-7"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187886"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2047241"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v31:4"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993705"},{"key":"e_1_3_2_1_15_1","first-page":"441","article-title":"Limitations of learning via embeddings in Euclidean half spaces","volume":"3","author":"Ben-David S.","year":"2002","unstructured":"S. Ben-David , N. Eiron , and H. Simon . Limitations of learning via embeddings in Euclidean half spaces . Journal of Machine Learning Research , 3 : 441 -- 461 , 2002 . S. Ben-David, N. Eiron, and H. Simon. Limitations of learning via embeddings in Euclidean half spaces. Journal of Machine Learning Research, 3:441--461, 2002.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.18"},{"key":"e_1_3_2_1_18_1","volume-title":"Proc. of the 16th IEEE Annual Conference on Computational Complexity","author":"de Wolf R.","year":"2001","unstructured":". Buhrman, R. de Wolf . Communication Complexity Lower Bounds by Polynomials , Proc. of the 16th IEEE Annual Conference on Computational Complexity , 2001 , 120--130. . Buhrman, R. de Wolf. Communication Complexity Lower Bounds by Polynomials, Proc. of the 16th IEEE Annual Conference on Computational Complexity, 2001, 120--130."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060701"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00019-3"},{"key":"e_1_3_2_1_24_1","volume-title":"Matrix Theory","author":"Franklin N.","year":"1993","unstructured":"Joel N. Franklin , Matrix Theory , Dover Publications , 1993 . Joel N. Franklin, Matrix Theory, Dover Publications, 1993."},{"key":"e_1_3_2_1_25_1","first-page":"910","article-title":"second eigenvalue conjecture and related problems","volume":"195","author":"Friedman J.","year":"2008","unstructured":"J. Friedman , A proof of Alon's second eigenvalue conjecture and related problems . Mem. Amer. Math. Soc. 195 ( 2008 ), no. 910 , viii 100 pp. J. Friedman,A proof of Alon's second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195 (2008), no. 910, viii 100 pp.","journal-title":"Mem. Amer. Math. Soc."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1515\/form.2003.009"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283504"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00005-4"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.25"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2160-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v34:3"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.004"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0614080"},{"key":"e_1_3_2_1_36_1","volume-title":"The","author":"Pisier G.","unstructured":"G. Pisier , The Volume of Convex Bodies and Banach Space Geometry, Second Ed., Cambridge University Press, 1999 . G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, Second Ed., Cambridge University Press, 1999."},{"key":"e_1_3_2_1_37_1","volume-title":"Quantum communication complexity of symmetric predicates, arXiv:quant-ph\/0204025","author":"Razborov A. A.","year":"2002","unstructured":"A. A. Razborov , Quantum communication complexity of symmetric predicates, arXiv:quant-ph\/0204025 , 2002 . A. A. Razborov, Quantum communication complexity of symmetric predicates, arXiv:quant-ph\/0204025, 2002."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744037"},{"key":"e_1_3_2_1_39_1","first-page":"25","article-title":"A note on coverings and packings","author":"Rogers C. A.","year":"1950","unstructured":"C. A. Rogers , A note on coverings and packings . J. London Math. Soc. 25 , ( 1950 ). 327--331. C. A. Rogers, A note on coverings and packings. J. London Math. Soc. 25, (1950). 327--331.","journal-title":"J. London Math. Soc."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-33.2.208"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-8.3.447"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1112\/S002557930000190X"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0242-4"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969027"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0784009-0"},{"key":"e_1_3_2_1_46_1","first-page":"162","article-title":"arguments in low-level complexity,Lecture notes","volume":"53","author":"Valiant L. G.","year":"1977","unstructured":"L. G. Valiant ,Graph-theoretic arguments in low-level complexity,Lecture notes in Computer Science 53 ( 1977 ), Springer, 162 -- 176 . L. G. Valiant,Graph-theoretic arguments in low-level complexity,Lecture notes in Computer Science 53 (1977), Springer,162--176.","journal-title":"Computer Science"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_1_48_1","volume-title":"AMS","author":"Vempala S.","year":"2004","unstructured":"S. Vempala , The Random Projection Method , AMS , 2004 . S. Vempala, The Random Projection Method, AMS, 2004."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488694","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:20Z","timestamp":1750235960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488694"}},"subtitle":["approximate rank"],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":48,"alternative-id":["10.1145\/2488608.2488694","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488694","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}