{"id":192144,"date":"2015-03-30T00:00:00","date_gmt":"2015-03-30T08:30:09","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/theory-day-session-1\/"},"modified":"2016-07-15T15:23:05","modified_gmt":"2016-07-15T22:23:05","slug":"theory-day-session-1","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/theory-day-session-1\/","title":{"rendered":"Theory Day Session 1"},"content":{"rendered":"<div class=\"asset-content\">\n<p>Noam Nisan &#8211; On the borders of Border&#8217;s Theorem<\/p>\n<p>Border&#8217;s theorem characterizes the possible (interim) allocation probabilities in a single item auction.  It has received much interest lately in Algorithmic Mechanism Design as it allows optimization in Mechanism Design using polynomial-size linear programs rather than the natural exponential-size ones.  Known Generalizations of Border&#8217;s theorem beyond the simple case of single item auctions are either very limited or are only approximate. This talk will explain why significant extensions of Border\u2019s theorem are impossible, assuming standard Computational  Complexity assumption.  Our proof will take us on a journey from simple questions regarding marginal probabilities in  probability spaces, to Revenue maximization in Mechanism Design, to Boolean function Analysis, to #P,  and back.  Joint work with Parikshit Gopalan and Tim Roughgarden.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Noam Nisan &#8211; On the borders of Border&#8217;s Theorem Border&#8217;s theorem characterizes the possible (interim) allocation probabilities in a single item auction. It has received much interest lately in Algorithmic Mechanism Design as it allows optimization in Mechanism Design using polynomial-size linear programs rather than the natural exponential-size ones. Known Generalizations of Border&#8217;s theorem beyond [&hellip;]<\/p>\n","protected":false},"featured_media":198968,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-192144","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/IS1Icuoc-58","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/192144","targetHints":{"allow":["GET"]}}],"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\/192144\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/198968"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=192144"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=192144"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=192144"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=192144"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=192144"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=192144"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=192144"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=192144"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=192144"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=192144"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}