{"id":186650,"date":"2011-08-10T00:00:00","date_gmt":"2011-08-11T10:21:34","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/injective-tensor-norms-hardness-and-reductions-2\/"},"modified":"2016-08-22T11:30:45","modified_gmt":"2016-08-22T18:30:45","slug":"injective-tensor-norms-hardness-and-reductions-2","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/injective-tensor-norms-hardness-and-reductions-2\/","title":{"rendered":"Injective Tensor Norms: Hardness and Reductions"},"content":{"rendered":"<div class=\"asset-content\">\n<p>If a vector has one index and a matrix has two, then a tensor has k indices, where k could be 3 or more.  In this talk, I&#8217;ll consider the injective tensor norm, which for k=1 is the length of a vector and for k=2 is the largest singular value of a matrix.  Applications of calculating this norm include finding planted cliques, simulating quantum systems and finding the distortion of certain norm embeddings.<\/p>\n<p>I&#8217;ll show that much of the difficulty of calculating the injective tensor norm is captured already when k=3, and I&#8217;ll prove a hardness result in this case, even for finding an approximation with constant additive error.  Previous hardness results applied only to the case of 1\/poly(dim) accuracy.  These results are based on joint work with Ashley Montanaro, and use quantum techniques, although the presentation will not assume familiarity with anything quantum.<\/p>\n<p>I&#8217;ll conclude by discussing algorithms, and a conjecture that would imply the existence of an algorithm whose complexity would match the above lower bound.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>If a vector has one index and a matrix has two, then a tensor has k indices, where k could be 3 or more. In this talk, I&#8217;ll consider the injective tensor norm, which for k=1 is the length of a vector and for k=2 is the largest singular value of a matrix. Applications of [&hellip;]<\/p>\n","protected":false},"featured_media":196315,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13561],"msr-video-type":[],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-186650","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/d7-jT9Dehc8","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/186650"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/186650\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/196315"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=186650"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=186650"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=186650"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=186650"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=186650"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=186650"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}