{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:14Z","timestamp":1750307414040,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"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":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806691","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Spectral methods for matrices and tensors"],"prefix":"10.1145","author":[{"given":"Ravindran","family":"Kannan","sequence":"first","affiliation":[{"name":"Microsoft Research Labs., India, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory on Computing","year":"2002","author":"Alon N.","key":"e_1_3_2_1_1_1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10041"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380859"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225140"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/302908.303020"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219097"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441629"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132556"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/297805.297827"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496887"},{"key":"e_1_3_2_1_13_1","unstructured":"C. Brubaker and S. Vempala Hidden clique problem Manuscript 09.  C. Brubaker and S. Vempala Hidden clique problem Manuscript 09."},{"key":"e_1_3_2_1_14_1","volume-title":"Bolyai Society Mathematical Studies","volume":"19","author":"Brubaker S. C.","year":"2008"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.76"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780593"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/57167.57214"},{"key":"e_1_3_2_1_19_1","first-page":"1036","volume-title":"Proc. of SODA","author":"Dasgupta A.","year":"2007"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.56"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875542"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644147"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442702"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509922"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3%3C187::AID-RSA3%3E3.0.CO;2-U"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1772"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060701"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_30"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"A. Deshpande L. Rademacher S. Vempala and G. Wang Matrix approximation and projective clustering via volume sampling Theory of Computing 2 (2006) no. 1 225--247.  A. Deshpande L. Rademacher S. Vempala and G. Wang Matrix approximation and projective clustering via volume sampling Theory of Computing 2 (2006) no. 1 225--247.","DOI":"10.4086\/toc.2006.v002a012"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_28"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01591018"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Z. F\u00fcredi and J. Koml\u00f3s The eigenvalues of random symmetric matrices Combinatorica 1 (1981) no. 3 233--241.  Z. F\u00fcredi and J. Koml\u00f3s The eigenvalues of random symmetric matrices Combinatorica 1 (1981) no. 3 233--241.","DOI":"10.1007\/BF02579329"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"A. Frieze and R. Kannan Quick approximation to matrices and applications Combinatorica 19 (1999) no. 2 175--200.  A. Frieze and R. Kannan Quick approximation to matrices and applications Combinatorica 19 (1999) no. 2 175--200.","DOI":"10.1007\/s004930050052"},{"volume-title":"Proc. of FST & TCS","year":"2008","author":"Frieze A.","key":"e_1_3_2_1_36_1"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"A simple algorithm for constructing szemer\u00e9di's regularity partition Electronic journal of combinatorics 6 (1999).  A simple algorithm for constructing szemer\u00e9di's regularity partition Electronic journal of combinatorics 6 (1999).","DOI":"10.37236\/1449"},{"key":"e_1_3_2_1_38_1","first-page":"370","volume-title":"Proc. of FOCS","author":"Frieze A.","year":"1998"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.167.481"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_3_2_1_43_1","unstructured":"C. Hillar and Lek heng Lim Most tensor problems are np hard The Computing Research Repository (2009).  C. Hillar and Lek heng Lim Most tensor problems are np hard The Computing Research Repository (2009)."},{"key":"e_1_3_2_1_44_1","unstructured":"Har-Peled Low-rank matrix approximation in linear-time http:\/\/valis.cs.uiuc.edu\/sariel\/papers\/05\/lrank\/ 2005.  Har-Peled Low-rank matrix approximation in linear-time http:\/\/valis.cs.uiuc.edu\/sariel\/papers\/05\/lrank\/ 2005."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378559"},{"key":"e_1_3_2_1_47_1","first-page":"7","volume-title":"North-Holland","author":"Kruskal J. B.","year":"1989"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445925"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000025"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875554"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0803205106"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/060665336"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"P. Paschou M. W. Mahoney A. Javed J. Kidd A. Pakstis S. Gu K. Kidd and P. Drineas Intra- and inter-population genotype reconstruction from tagging snps Genome Research \\textbf17(1) (2007) 96--107.  P. Paschou M. W. Mahoney A. Javed J. Kidd A. Pakstis S. Gu K. Kidd and P. Drineas Intra- and inter-population genotype reconstruction from tagging snps Genome Research \\textbf17(1) (2007) 96--107.","DOI":"10.1101\/gr.5741407"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S. Teng Spectral partitioning works: Planar graphs and finite element meshes Linear Algebra and its Applications 421 (2007) no. 2-3 284 -- 305.  D. A. Spielman and S. Teng Spectral partitioning works: Planar graphs and finite element meshes Linear Algebra and its Applications 421 (2007) no. 2-3 284 -- 305.","DOI":"10.1016\/j.laa.2006.07.020"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.33"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060654"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts USA","acronym":"STOC'10"},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:36Z","timestamp":1750246776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":63,"alternative-id":["10.1145\/1806689.1806691","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806691","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}