Downtown Los Angeles during a hazy sunset from a helicopter. The light rays shine gold from in between the building of DTLA.
June 25, 2018 – June 29, 2018

Microsoft Research @ STOC 2018

Location: Los Angeles, California

Register

k-server via multiscale entropic regularization
Monday, June 25, 2018 | 11:30 AM | Session 1A | Bunker Hill/Watercourt

Sebastien Bubeck, Michael Cohen, James R. Lee , Yin Tat Lee , Aleksander Madry

A Converse to Banach’s Fixed Point Theorem and its CLS Completeness
Monday, June 25, 2018 | 11:30 AM | Session 1B | Museum A/B

Costis Daskalakis, Christos Tzamos, Manolis Zampetakis

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Monday, June 25, 2018 | 2:30 PM | Session 2C | Hershey/Crocker

Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, Avi Wigderson

Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
Monday, June 25, 2018 | 2:50 PM | Session 2A | Bunker Hill/Watercourt

Yannai A. Gonczarowski

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Tuesday, June 26, 2018 | 10:40 AM | Session 3B | Museum A/B

Mark Bun, Robin Kothari, Justin Thaler

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
Wednesday, June 27, 2018 | 10:40 AM | Session 5B | Museum A/B

Nir Bitansky, Yael Tauman Kalai, Omer Paneth

Non-Malleable Secret Sharing
Wednesday, June 27, 2018 | 11:00 AM | Session 5B | Museum A/B

Vipul Goyal, Ashutosh Kumar

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

Ravishankar Krishnaswamy, Shi Li, Sai Sandeep

Succinct Delegation for Low-Space Non-Deterministic Computation
Wednesday, June 27, 2018 | 11:40 AM | Session 5B | Museum A/B

Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

Monotone Circuit Lower Bounds from Resolution
Wednesday, June 27, 2018 | 3:20 PM | Session 6B | Museum A/B

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

A Matrix Expander Chernoff Bound
Thursday, June 28, 2018 | 10:20 AM | Session 7C | Hershey/Crocker

Ankit Garg, Yin Tat Lee, Zhao Song , Nikhil Srivastava

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

Sebastien Bubeck, Michael B. Cohen, Yin Tat Lee , Yuanzhi Li