{"id":492302,"date":"2018-06-25T13:58:40","date_gmt":"2018-06-25T20:58:40","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-event&p=492302"},"modified":"2025-08-06T11:57:06","modified_gmt":"2025-08-06T18:57:06","slug":"stoc-2018","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/stoc-2018\/","title":{"rendered":"Microsoft Research @ STOC 2018"},"content":{"rendered":"\n\n

Venue:<\/strong> Omni Hotel at California Plaza (opens in new tab)<\/span><\/a>
\n251 South Olive Street
\nLos Angeles, CA 90012<\/p>\n

Website:<\/strong>\u00a0STOC 2018 (opens in new tab)<\/span><\/a>Opens in a new tab<\/span><\/p>\n

Microsoft is excited to be a sponsor of the 50th<\/sup> ACM Symposium on Theory of Computing (STOC 2018) (opens in new tab)<\/span><\/a>. STOC 2018 will be part of a 5-day TheoryFest and includes invited speaker Monia Ghobadi<\/a> and twelve accepted papers from Microsoft Research.<\/p>\n

Microsoft is proud to also be sponsoring the inaugural TC Women Meeting. TCS Women is a new community for women researchers in Theoretical Computer Science (TCS) and related areas.<\/p>\n

Invited Speakers<\/h2>\n

Programming the Topology of Networks: Technology and Algorithms
\nMonday, June 25, 2018 | 4:10 PM-4:35PM<\/h4>\n

Monia Ghobadi<\/strong><\/a><\/p>\n

Workshops<\/h2>\n

TCS Women Panel
\nTuesday, June 26, 2018<\/h4>\n

Lenore Blum, Cynthia Dwork<\/strong><\/a>, Yael Kalai<\/strong><\/a>, Valerie King, Nina Mishra, Ronitt Rubinfeld, Virginia Vassilevska Williams<\/p>\n

Opens in a new tab<\/span><\/p>\n

k-server via multiscale entropic regularization
\nMonday, June 25, 2018 | 11:30 AM | Session 1A | Bunker Hill\/Watercourt<\/h4>\n

Sebastien Bubeck<\/strong><\/a>, Michael Cohen, James R. Lee , Yin Tat Lee , Aleksander Madry<\/p>\n

A Converse to Banach’s Fixed Point Theorem and its CLS Completeness
\nMonday, June 25, 2018 | 11:30 AM | Session 1B | Museum A\/B<\/h4>\n

Costis Daskalakis, Christos Tzamos<\/strong><\/a>, Manolis Zampetakis<\/p>\n

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
\nMonday, June 25, 2018 | 2:30 PM | Session 2C | Hershey\/Crocker<\/h4>\n

Zeyuan Allen-Zhu<\/strong><\/a>, Ankit Garg<\/strong><\/a>, Yuanzhi Li, Rafael Oliveira, Avi Wigderson<\/p>\n

Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
\nMonday, June 25, 2018 | 2:50 PM | Session 2A | Bunker Hill\/Watercourt<\/h4>\n

Yannai A. Gonczarowski<\/strong><\/p>\n

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
\nTuesday, June 26, 2018 | 10:40 AM | Session 3B | Museum A\/B<\/h4>\n

Mark Bun, Robin Kothari<\/strong><\/a>, Justin Thaler<\/p>\n

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
\nWednesday, June 27, 2018 | 10:40 AM | Session 5B | Museum A\/B<\/h4>\n

Nir Bitansky, Yael Tauman Kalai<\/strong><\/a>, Omer Paneth<\/p>\n

Non-Malleable Secret Sharing
\nWednesday, June 27, 2018 | 11:00 AM | Session 5B | Museum A\/B<\/h4>\n

Vipul Goyal, Ashutosh Kumar<\/strong><\/p>\n

Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
\nWednesday, June 27, 2018 | 11:40 AM | Session 5A | Bunker Hill\/Watercourt<\/h4>\n

Ravishankar Krishnaswamy<\/strong><\/a>, Shi Li, Sai Sandeep<\/strong><\/p>\n

Succinct Delegation for Low-Space Non-Deterministic Computation
\nWednesday, June 27, 2018 | 11:40 AM | Session 5B | Museum A\/B<\/h4>\n

Saikrishna Badrinarayanan, Yael Tauman Kalai<\/strong><\/a>, Dakshita Khurana, Amit Sahai, Daniel Wichs<\/p>\n

Monotone Circuit Lower Bounds from Resolution
\nWednesday, June 27, 2018 | 3:20 PM | Session 6B | Museum A\/B<\/h4>\n

Ankit Garg<\/strong><\/a>, Mika G\u00f6\u00f6s, Pritish Kamath, Dmitry Sokolov<\/p>\n

A Matrix Expander Chernoff Bound
\nThursday, June 28, 2018 | 10:20 AM | Session 7C | Hershey\/Crocker<\/h4>\n

Ankit Garg<\/strong><\/a>, Yin Tat Lee, Zhao Song , Nikhil Srivastava<\/p>\n

A homotopy method for lp regression provably beyond self-concordance and in input-sparsity time
\nThursday, June 28, 2018 | 11:20 AM | Session 7C | Hershey\/Crocker<\/h4>\n

Sebastien Bubeck<\/strong><\/a>, Michael B. Cohen, Yin Tat Lee , Yuanzhi Li<\/p>\n

Opens in a new tab<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Microsoft is proud to also be sponsoring the inaugural TC Women Meeting. TCS Women is a new community for women researchers in Theoretical Computer Science (TCS) and related areas.<\/p>\n","protected":false},"featured_media":492560,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_startdate":"2018-06-25","msr_enddate":"2018-06-29","msr_location":"Los Angeles, California","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"http:\/\/acm-stoc.org\/stoc2018\/registration.html","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":[13559],"msr-region":[197900],"msr-event-type":[197941],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-492302","msr-event","type-msr-event","status-publish","has-post-thumbnail","hentry","msr-research-area-social-sciences","msr-region-north-america","msr-event-type-conferences","msr-locale-en_us"],"msr_about":"\n\n

Venue:<\/strong> Omni Hotel at California Plaza (opens in new tab)<\/span><\/a>
\n251 South Olive Street
\nLos Angeles, CA 90012<\/p>\n

Website:<\/strong>\u00a0STOC 2018 (opens in new tab)<\/span><\/a>Opens in a new tab<\/span><\/p>\n

Microsoft is excited to be a sponsor of the 50th<\/sup> ACM Symposium on Theory of Computing (STOC 2018)<\/a>. STOC 2018 will be part of a 5-day TheoryFest and includes invited speaker Monia Ghobadi<\/a> and twelve accepted papers from Microsoft Research.<\/p>\n

Microsoft is proud to also be sponsoring the inaugural TC Women Meeting. TCS Women is a new community for women researchers in Theoretical Computer Science (TCS) and related areas.<\/p>\n

Invited Speakers<\/h2>\n

Programming the Topology of Networks: Technology and Algorithms
\nMonday, June 25, 2018 | 4:10 PM-4:35PM<\/h4>\n

Monia Ghobadi<\/strong><\/a><\/p>\n

Workshops<\/h2>\n

TCS Women Panel
\nTuesday, June 26, 2018<\/h4>\n

Lenore Blum, Cynthia Dwork<\/strong><\/a>, Yael Kalai<\/strong><\/a>, Valerie King, Nina Mishra, Ronitt Rubinfeld, Virginia Vassilevska Williams<\/p>\n

Opens in a new tab<\/span><\/p>\n

k-server via multiscale entropic regularization
\nMonday, June 25, 2018 | 11:30 AM | Session 1A | Bunker Hill\/Watercourt<\/h4>\n

Sebastien Bubeck<\/strong><\/a>, Michael Cohen, James R. Lee , Yin Tat Lee , Aleksander Madry<\/p>\n

A Converse to Banach’s Fixed Point Theorem and its CLS Completeness
\nMonday, June 25, 2018 | 11:30 AM | Session 1B | Museum A\/B<\/h4>\n

Costis Daskalakis, Christos Tzamos<\/strong><\/a>, Manolis Zampetakis<\/p>\n

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
\nMonday, June 25, 2018 | 2:30 PM | Session 2C | Hershey\/Crocker<\/h4>\n

Zeyuan Allen-Zhu<\/strong><\/a>, Ankit Garg<\/strong><\/a>, Yuanzhi Li, Rafael Oliveira, Avi Wigderson<\/p>\n

Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
\nMonday, June 25, 2018 | 2:50 PM | Session 2A | Bunker Hill\/Watercourt<\/h4>\n

Yannai A. Gonczarowski<\/strong><\/p>\n

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
\nTuesday, June 26, 2018 | 10:40 AM | Session 3B | Museum A\/B<\/h4>\n

Mark Bun, Robin Kothari<\/strong><\/a>, Justin Thaler<\/p>\n

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
\nWednesday, June 27, 2018 | 10:40 AM | Session 5B | Museum A\/B<\/h4>\n

Nir Bitansky, Yael Tauman Kalai<\/strong><\/a>, Omer Paneth<\/p>\n

Non-Malleable Secret Sharing
\nWednesday, June 27, 2018 | 11:00 AM | Session 5B | Museum A\/B<\/h4>\n

Vipul Goyal, Ashutosh Kumar<\/strong><\/p>\n

Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
\nWednesday, June 27, 2018 | 11:40 AM | Session 5A | Bunker Hill\/Watercourt<\/h4>\n

Ravishankar Krishnaswamy<\/strong><\/a>, Shi Li, Sai Sandeep<\/strong><\/p>\n

Succinct Delegation for Low-Space Non-Deterministic Computation
\nWednesday, June 27, 2018 | 11:40 AM | Session 5B | Museum A\/B<\/h4>\n

Saikrishna Badrinarayanan, Yael Tauman Kalai<\/strong><\/a>, Dakshita Khurana, Amit Sahai, Daniel Wichs<\/p>\n

Monotone Circuit Lower Bounds from Resolution
\nWednesday, June 27, 2018 | 3:20 PM | Session 6B | Museum A\/B<\/h4>\n

Ankit Garg<\/strong><\/a>, Mika G\u00f6\u00f6s, Pritish Kamath, Dmitry Sokolov<\/p>\n

A Matrix Expander Chernoff Bound
\nThursday, June 28, 2018 | 10:20 AM | Session 7C | Hershey\/Crocker<\/h4>\n

Ankit Garg<\/strong><\/a>, Yin Tat Lee, Zhao Song , Nikhil Srivastava<\/p>\n

A homotopy method for lp regression provably beyond self-concordance and in input-sparsity time
\nThursday, June 28, 2018 | 11:20 AM | Session 7C | Hershey\/Crocker<\/h4>\n

Sebastien Bubeck<\/strong><\/a>, Michael B. Cohen, Yin Tat Lee , Yuanzhi Li<\/p>\n

Opens in a new tab<\/span><\/p>\n","tab-content":[{"id":0,"name":"About","content":"Microsoft is excited to be a sponsor of the 50th<\/sup> ACM Symposium on Theory of Computing (STOC 2018)<\/a>. STOC 2018 will be part of a 5-day TheoryFest and includes invited speaker Monia Ghobadi<\/a> and twelve accepted papers from Microsoft Research.\r\n\r\nMicrosoft is proud to also be sponsoring the inaugural TC Women Meeting. TCS Women is a new community for women researchers in Theoretical Computer Science (TCS) and related areas.\r\n

Invited Speakers<\/h2>\r\n

Programming the Topology of Networks: Technology and Algorithms\r\nMonday, June 25, 2018 | 4:10 PM-4:35PM<\/h4>\r\n

Monia Ghobadi<\/strong><\/a><\/p>\r\n\r\n

Workshops<\/h2>\r\n

TCS Women Panel\r\nTuesday, June 26, 2018<\/h4>\r\n

Lenore Blum, Cynthia Dwork<\/strong><\/a>, Yael Kalai<\/strong><\/a>, Valerie King, Nina Mishra, Ronitt Rubinfeld, Virginia Vassilevska Williams<\/p>"},{"id":1,"name":"Accepted Papers","content":"

k-server via multiscale entropic regularization\r\nMonday, June 25, 2018 | 11:30 AM | Session 1A | Bunker Hill\/Watercourt<\/h4>\r\n

Sebastien Bubeck<\/strong><\/a>, Michael Cohen, James R. Lee , Yin Tat Lee , Aleksander Madry<\/p>\r\n\r\n

A Converse to Banach's Fixed Point Theorem and its CLS Completeness\r\nMonday, June 25, 2018 | 11:30 AM | Session 1B | Museum A\/B<\/h4>\r\n

Costis Daskalakis, Christos Tzamos<\/strong><\/a>, Manolis Zampetakis<\/p>\r\n\r\n

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing\r\nMonday, June 25, 2018 | 2:30 PM | Session 2C | Hershey\/Crocker<\/h4>\r\n

Zeyuan Allen-Zhu<\/strong><\/a>, Ankit Garg<\/strong><\/a>, Yuanzhi Li, Rafael Oliveira, Avi Wigderson<\/p>\r\n\r\n

Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality\r\nMonday, June 25, 2018 | 2:50 PM | Session 2A | Bunker Hill\/Watercourt<\/h4>\r\n

Yannai A. Gonczarowski<\/strong><\/p>\r\n\r\n

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials\r\nTuesday, June 26, 2018 | 10:40 AM | Session 3B | Museum A\/B<\/h4>\r\n

Mark Bun, Robin Kothari<\/strong><\/a>, Justin Thaler<\/p>\r\n\r\n

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions\r\nWednesday, June 27, 2018 | 10:40 AM | Session 5B | Museum A\/B<\/h4>\r\n

Nir Bitansky, Yael Tauman Kalai<\/strong><\/a>, Omer Paneth<\/p>\r\n\r\n

Non-Malleable Secret Sharing\r\nWednesday, June 27, 2018 | 11:00 AM | Session 5B | Museum A\/B<\/h4>\r\n

Vipul Goyal, Ashutosh Kumar<\/strong><\/p>\r\n\r\n

Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding\r\nWednesday, June 27, 2018 | 11:40 AM | Session 5A | Bunker Hill\/Watercourt<\/h4>\r\n

Ravishankar Krishnaswamy<\/strong><\/a>, Shi Li, Sai Sandeep<\/strong><\/p>\r\n\r\n

Succinct Delegation for Low-Space Non-Deterministic Computation\r\nWednesday, June 27, 2018 | 11:40 AM | Session 5B | Museum A\/B<\/h4>\r\n

Saikrishna Badrinarayanan, Yael Tauman Kalai<\/strong><\/a>, Dakshita Khurana, Amit Sahai, Daniel Wichs<\/p>\r\n\r\n

Monotone Circuit Lower Bounds from Resolution\r\nWednesday, June 27, 2018 | 3:20 PM | Session 6B | Museum A\/B<\/h4>\r\n

Ankit Garg<\/strong><\/a>, Mika G\u00f6\u00f6s, Pritish Kamath, Dmitry Sokolov<\/p>\r\n\r\n

A Matrix Expander Chernoff Bound\r\nThursday, June 28, 2018 | 10:20 AM | Session 7C | Hershey\/Crocker<\/h4>\r\n

Ankit Garg<\/strong><\/a>, Yin Tat Lee, Zhao Song , Nikhil Srivastava<\/p>\r\n\r\n

A homotopy method for lp regression provably beyond self-concordance and in input-sparsity time\r\nThursday, June 28, 2018 | 11:20 AM | Session 7C | Hershey\/Crocker<\/h4>\r\n

Sebastien Bubeck<\/strong><\/a>, Michael B. Cohen, Yin Tat Lee , Yuanzhi Li<\/p>"}],"msr_startdate":"2018-06-25","msr_enddate":"2018-06-29","msr_event_time":"","msr_location":"Los Angeles, California","msr_event_link":"http:\/\/acm-stoc.org\/stoc2018\/registration.html","msr_event_recording_link":"","msr_startdate_formatted":"June 25, 2018","msr_register_text":"Watch now","msr_cta_link":"http:\/\/acm-stoc.org\/stoc2018\/registration.html","msr_cta_text":"Watch now","msr_cta_bi_name":"Event Register","featured_image_thumbnail":"\"Downtown","event_excerpt":"Microsoft is proud to also be sponsoring the inaugural TC Women Meeting. TCS Women is a new community for women researchers in Theoretical Computer Science (TCS) and related areas.","msr_research_lab":[199562,199563,199565],"related-researchers":[],"msr_impact_theme":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-opportunities":[],"related-publications":[],"related-videos":[],"related-posts":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/492302","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":4,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/492302\/revisions"}],"predecessor-version":[{"id":1147101,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/492302\/revisions\/1147101"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/492560"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=492302"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=492302"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=492302"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=492302"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=492302"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=492302"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=492302"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=492302"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=492302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}