{"id":700798,"date":"2020-10-23T14:43:48","date_gmt":"2020-10-23T21:43:48","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-event&p=700798"},"modified":"2025-08-06T11:52:18","modified_gmt":"2025-08-06T18:52:18","slug":"focs-2020","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/focs-2020\/","title":{"rendered":"Microsoft at FOCS 2020"},"content":{"rendered":"\n\n

Website: FOCS 2020 (opens in new tab)<\/span><\/a>Opens in a new tab<\/span><\/p>\n

Microsoft is proud to be a sponsor of the 61st Annual IEEE Symposium on Foundations of Computer Science (opens in new tab)<\/span><\/a>. See more details on our contributions on the sessions tab.Opens in a new tab<\/span><\/p>\n

All times are displayed in UTC \u2013 05:00<\/em><\/p>\n

Monday, November 16<\/h2>\n

15:15 \u2013 16:00 | Session 2B
\nAn O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions<\/strong><\/a>
\nPaul Duetting, Thomas Kesselheim, Brendan Lucier<\/a><\/p>\n

24:00 \u2013 1:30 | Poster Session 2B
\nAn O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions<\/strong><\/a>
\nPaul Duetting, Thomas Kesselheim, Brendan Lucier<\/a><\/p>\n

Monday, November 17<\/h2>\n

14:15 \u2013 14:30 | Session 4A
\nDeterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes<\/strong><\/a>
\nZvika Brakerski, Yael Tauman Kalai<\/a>, Raghuvansh Saxena<\/p>\n

24:00 \u2013 1:30 | Poster Session 4A
\nDeterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes<\/strong><\/a>
\nZvika Brakerski, Yael Tauman Kalai<\/a>, Raghuvansh Saxena<\/p>\n

Wednesday, November 18<\/h2>\n

12:00 \u2013 12:15 | Session 5C
\nScheduling with Communication Delays via LP Hierarchies and Clustering<\/strong><\/a>
\nSami Davies, Janardhan Kulkarni<\/a>, Thomas Rothvoss, Jakub Tarnawski<\/a>, Yihao Zhang<\/p>\n

12:15 \u2013 12:30 | Session 5A
\nEntanglement Is Necessary for Optimal Quantum Property Testing<\/strong><\/a>
\nSebastien Bubeck<\/a>, Sitan Chen, Jerry Li<\/a><\/p>\n

14:15 \u2013 14:30 | Session 6B
\nBipartite Matching in Nearly-linear Time on Moderately Dense Graphs<\/strong><\/a>
\nJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang<\/p>\n

24:00 \u2013 1:30 | Poster Session 5A
\nEntanglement Is Necessary for Optimal Quantum Property Testing<\/strong><\/a>
\nSebastien Bubeck<\/a>, Sitan Chen, Jerry Li<\/a><\/p>\n

24:00 \u2013 1:30 | Poster Session 5C
\nScheduling with Communication Delays via LP Hierarchies and Clustering<\/strong><\/a>
\nSami Davies, Janardhan Kulkarni<\/a>, Thomas Rothvoss, Jakub Tarnawski<\/a>, Yihao Zhang<\/p>\n

24:00 \u2013 1:30 | Poster Session 6B
\nBipartite Matching in Nearly-linear Time on Moderately Dense Graphs<\/strong><\/a>
\nJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di WangOpens in a new tab<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Microsoft is proud to be a sponsor of the 61st Annual IEEE Symposium on Foundations of Computer Science.<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_startdate":"2020-11-16","msr_enddate":"2020-11-19","msr_location":"Virtual","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"","msr_event_link_redirect":false,"msr_event_time":"","msr_hide_region":false,"msr_private_event":false,"msr_hide_image_in_river":0,"footnotes":""},"research-area":[13561,243138],"msr-region":[256048],"msr-event-type":[197941],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-700798","msr-event","type-msr-event","status-publish","hentry","msr-research-area-algorithms","msr-research-area-quantum","msr-region-global","msr-event-type-conferences","msr-locale-en_us"],"msr_about":"\n\n

Website: FOCS 2020 (opens in new tab)<\/span><\/a>Opens in a new tab<\/span><\/p>\n

Microsoft is proud to be a sponsor of the 61st Annual IEEE Symposium on Foundations of Computer Science (opens in new tab)<\/span><\/a>. See more details on our contributions on the sessions tab.Opens in a new tab<\/span><\/p>\n

All times are displayed in UTC \u2013 05:00<\/em><\/p>\n

Monday, November 16<\/h2>\n

15:15 \u2013 16:00 | Session 2B
\nAn O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions<\/strong><\/a>
\nPaul Duetting, Thomas Kesselheim, Brendan Lucier<\/a><\/p>\n

24:00 \u2013 1:30 | Poster Session 2B
\nAn O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions<\/strong><\/a>
\nPaul Duetting, Thomas Kesselheim, Brendan Lucier<\/a><\/p>\n

Monday, November 17<\/h2>\n

14:15 \u2013 14:30 | Session 4A
\nDeterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes<\/strong><\/a>
\nZvika Brakerski, Yael Tauman Kalai<\/a>, Raghuvansh Saxena<\/p>\n

24:00 \u2013 1:30 | Poster Session 4A
\nDeterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes<\/strong><\/a>
\nZvika Brakerski, Yael Tauman Kalai<\/a>, Raghuvansh Saxena<\/p>\n

Wednesday, November 18<\/h2>\n

12:00 \u2013 12:15 | Session 5C
\nScheduling with Communication Delays via LP Hierarchies and Clustering<\/strong><\/a>
\nSami Davies, Janardhan Kulkarni<\/a>, Thomas Rothvoss, Jakub Tarnawski<\/a>, Yihao Zhang<\/p>\n

12:15 \u2013 12:30 | Session 5A
\nEntanglement Is Necessary for Optimal Quantum Property Testing<\/strong><\/a>
\nSebastien Bubeck<\/a>, Sitan Chen, Jerry Li<\/a><\/p>\n

14:15 \u2013 14:30 | Session 6B
\nBipartite Matching in Nearly-linear Time on Moderately Dense Graphs<\/strong><\/a>
\nJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang<\/p>\n

24:00 \u2013 1:30 | Poster Session 5A
\nEntanglement Is Necessary for Optimal Quantum Property Testing<\/strong><\/a>
\nSebastien Bubeck<\/a>, Sitan Chen, Jerry Li<\/a><\/p>\n

24:00 \u2013 1:30 | Poster Session 5C
\nScheduling with Communication Delays via LP Hierarchies and Clustering<\/strong><\/a>
\nSami Davies, Janardhan Kulkarni<\/a>, Thomas Rothvoss, Jakub Tarnawski<\/a>, Yihao Zhang<\/p>\n

24:00 \u2013 1:30 | Poster Session 6B
\nBipartite Matching in Nearly-linear Time on Moderately Dense Graphs<\/strong><\/a>
\nJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di WangOpens in a new tab<\/span><\/p>\n","tab-content":[{"id":0,"name":"About","content":"Microsoft is proud to be a sponsor of the 61st Annual IEEE Symposium on Foundations of Computer Science<\/a>. See more details on our contributions on the sessions tab."},{"id":1,"name":"Sessions","content":"All times are displayed in UTC \u2013 05:00<\/em>\r\n

Monday, November 16<\/h2>\r\n15:15 \u2013 16:00 | Session 2B\r\nAn O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions<\/strong><\/a>\r\nPaul Duetting, Thomas Kesselheim, Brendan Lucier<\/a>\r\n\r\n24:00 \u2013 1:30 | Poster Session 2B\r\nAn O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions<\/strong><\/a>\r\nPaul Duetting, Thomas Kesselheim, Brendan Lucier<\/a>\r\n

Monday, November 17<\/h2>\r\n14:15 \u2013 14:30 | Session 4A\r\nDeterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes<\/strong><\/a>\r\nZvika Brakerski, Yael Tauman Kalai<\/a>, Raghuvansh Saxena\r\n\r\n24:00 \u2013 1:30 | Poster Session 4A\r\nDeterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes<\/strong><\/a>\r\nZvika Brakerski, Yael Tauman Kalai<\/a>, Raghuvansh Saxena\r\n

Wednesday, November 18<\/h2>\r\n12:00 \u2013 12:15 | Session 5C\r\nScheduling with Communication Delays via LP Hierarchies and Clustering<\/strong><\/a>\r\nSami Davies, Janardhan Kulkarni<\/a>, Thomas Rothvoss, Jakub Tarnawski<\/a>, Yihao Zhang\r\n\r\n12:15 \u2013 12:30 | Session 5A\r\nEntanglement Is Necessary for Optimal Quantum Property Testing<\/strong><\/a>\r\nSebastien Bubeck<\/a>, Sitan Chen, Jerry Li<\/a>\r\n\r\n14:15 \u2013 14:30 | Session 6B\r\nBipartite Matching in Nearly-linear Time on Moderately Dense Graphs<\/strong><\/a>\r\nJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang\r\n\r\n24:00 \u2013 1:30 | Poster Session 5A\r\nEntanglement Is Necessary for Optimal Quantum Property Testing<\/strong><\/a>\r\nSebastien Bubeck<\/a>, Sitan Chen, Jerry Li<\/a>\r\n\r\n24:00 \u2013 1:30 | Poster Session 5C\r\nScheduling with Communication Delays via LP Hierarchies and Clustering<\/strong><\/a>\r\nSami Davies, Janardhan Kulkarni<\/a>, Thomas Rothvoss, Jakub Tarnawski<\/a>, Yihao Zhang\r\n\r\n24:00 \u2013 1:30 | Poster Session 6B\r\nBipartite Matching in Nearly-linear Time on Moderately Dense Graphs<\/strong><\/a>\r\nJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang"}],"msr_startdate":"2020-11-16","msr_enddate":"2020-11-19","msr_event_time":"","msr_location":"Virtual","msr_event_link":"","msr_event_recording_link":"","msr_startdate_formatted":"November 16, 2020","msr_register_text":"Watch now","msr_cta_link":"","msr_cta_text":"","msr_cta_bi_name":"","featured_image_thumbnail":null,"event_excerpt":"Microsoft is proud to be a sponsor of the 61st Annual IEEE Symposium on Foundations of Computer Science.","msr_research_lab":[],"related-researchers":[],"msr_impact_theme":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-opportunities":[],"related-publications":[656511,700822,700834,700843,700852],"related-videos":[],"related-posts":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/700798","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-event"}],"version-history":[{"count":3,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/700798\/revisions"}],"predecessor-version":[{"id":1146921,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/700798\/revisions\/1146921"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=700798"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=700798"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=700798"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=700798"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=700798"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=700798"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=700798"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=700798"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=700798"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}