{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:28Z","timestamp":1750693408116,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[[2012,5,19]]},"DOI":"10.1145\/2213977.2213995","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"163-172","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["On identity testing of tensors, low-rank recovery and compressed sensing"],"prefix":"10.1145","author":[{"given":"Michael A.","family":"Forbes","sequence":"first","affiliation":[{"name":"MIT, Cambridge, MA, USA"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[{"name":"Technion --- Israel Institute of Technology, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"http:\/\/dsp.rice.edu\/cs.  http:\/\/dsp.rice.edu\/cs."},{"key":"e_1_3_2_2_2_1","unstructured":"http:\/\/perception.csl.uiuc.edu\/matrix-rank\/.  http:\/\/perception.csl.uiuc.edu\/matrix-rank\/."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_2_2_5_1","unstructured":"E. Arias-Castro E. J. Candes and M. Davenport. On the fundamental limits of adaptive sensing. arXiv:1111.4646 2011.  E. Arias-Castro E. J. Candes and M. Davenport. On the fundamental limits of adaptive sensing. arXiv:1111.4646 2011."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337257"},{"key":"e_1_3_2_2_7_1","unstructured":"F. Bergadano N. H. Bshouty and S. Varricchio. Learning multivariate polynomials from substitution and equivalence queries. ECCC 3(8) 1996.  F. Bergadano N. H. Bshouty and S. Varricchio. Learning multivariate polynomials from substitution and equivalence queries. ECCC 3(8) 1996."},{"volume-title":"McGraw-Hill Book Co.","year":"1968","author":"Berlekamp E. R.","key":"e_1_3_2_2_8_1"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"crossref","unstructured":"E. Candes J. Romberg and T. Tao. Stable Signal Recovery from Incomplete and Inaccurate Measurements. arXiv:math\/0503066 Mar. 2005.  E. Candes J. Romberg and T. Tao. Stable Signal Recovery from Incomplete and Inaccurate Measurements. arXiv:math\/0503066 Mar. 2005.","DOI":"10.1117\/12.620143"},{"key":"e_1_3_2_2_10_1","unstructured":"E. J. Candes and Y. Plan. Matrix Completion With Noise. ArXiv e-prints Mar. 2009.  E. J. Candes and Y. Plan. Matrix Completion With Noise. ArXiv e-prints Mar. 2009."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2111771"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"crossref","unstructured":"E. J. Candes and T. Tao. The Power of Convex Relaxation: Near-Optimal Matrix Completion. ArXiv e-prints Mar. 2009.  E. J. Candes and T. Tao. The Power of Convex Relaxation: Near-Optimal Matrix Completion. ArXiv e-prints Mar. 2009.","DOI":"10.1109\/TIT.2010.2044061"},{"key":"e_1_3_2_2_13_1","unstructured":"G. C. F. M. R. de Prony. Essai \u00e9xperimental et analytique: sur les lois de la dilatabilit\u00e9 de fluides \u00e9lastique et sur celles de la force expansive de la vapeur de l'alkool \u00e0 diff\u00e9rentes temp\u00e9ratures. Journal de l'\u00e9cole Polytechnique 1:24--76 1795.  G. C. F. M. R. de Prony. Essai \u00e9xperimental et analytique: sur les lois de la dilatabilit\u00e9 de fluides \u00e9lastique et sur celles de la force expansive de la vapeur de l'alkool \u00e0 diff\u00e9rentes temp\u00e9ratures. Journal de l'\u00e9cole Polytechnique 1:24--76 1795."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90015-8"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.19"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Y. C. Eldar D. Needell and Y. Plan. Unicity conditions for low-rank matrix recovery. arXiv:1103.5479 2011.  Y. C. Eldar D. Needell and Y. Plan. Unicity conditions for low-rank matrix recovery. arXiv:1103.5479 2011.","DOI":"10.1117\/12.891933"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"crossref","unstructured":"A. Emad and O. Milenkovic. Information theoretic bounds for tensor rank minimization over finite fields. arXiv:1103.4435 2011.  A. Emad and O. Milenkovic. Information theoretic bounds for tensor rank minimization over finite fields. arXiv:1103.4435 2011.","DOI":"10.1109\/GLOCOM.2011.6133547"},{"issue":"2","key":"e_1_3_2_2_18_1","first-page":"102","article-title":"Optimal array error-correcting codes","volume":"21","author":"Gabidulin E. M.","year":"1985","journal-title":"Probl. Peredach. Inform."},{"issue":"1","key":"e_1_3_2_2_19_1","first-page":"1","article-title":"Theory of codes with maximum rank distance","volume":"21","author":"Gabidulin E. M.","year":"1985","journal-title":"Probl. Inform. Transm."},{"volume-title":"Zzvestiya VUZ. Radioelektronika","year":"1972","author":"Gabidulin E. M.","key":"e_1_3_2_2_20_1"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2259-3"},{"key":"e_1_3_2_2_22_1","unstructured":"D. Gross. Recovering low-rank matrices from few coefficients in any basis. ArXiv e-prints Oct. 2009.  D. Gross. Recovering low-rank matrices from few coefficients in any basis. ArXiv e-prints Oct. 2009."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.83"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.15"},{"key":"e_1_3_2_2_29_1","unstructured":"A. Khajehnejad S. Oymak and B. Hassibi. Subspace expanders and matrix rank minimization. arXiv:1102.3947v1 2011.  A. Khajehnejad S. Oymak and B. Hassibi. Subspace expanders and matrix rank minimization. arXiv:1102.3947v1 2011."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a010"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2005.12.033"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1969.1054260"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)00158-V"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.75248"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556603"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993694"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_2_42_1","unstructured":"V. Y. F. Tan L. Balzano and S. C. Draper. Rank minimization over finite fields: Fundamental limits and coding-theoretic interpretations. arXiv:1104.4302v2 2011.  V. Y. F. Tan L. Balzano and S. C. Draper. Rank minimization over finite fields: Fundamental limits and coding-theoretic interpretations. arXiv:1104.4302v2 2011."},{"key":"e_1_3_2_2_43_1","first-page":"162","volume-title":"Lecture notes in Computer Science","author":"Valiant L. G.","year":"1977"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York USA","acronym":"STOC'12"},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213995","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2213995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":43,"alternative-id":["10.1145\/2213977.2213995","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2213995","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}