Oct 14^th Saturday

Compressed Zip File of Program and Proceedings

9:00 AM- 11:00 AM	Linear Sketching as a Tool for Everything (Angel/Belvedre)	Frontiers in Distribution Testing (Treasure/Yerba)	Hardness Escalation in Communication Complexity and Query Complexity (Mariposa)
11:00-11:25	COFFEE BREAK
11:25 AM- 12:25 AM	Linear Sketching as a Tool for Everything (Angel/Belvedre)	Frontiers in Distribution Testing (Treasure/Yerba)	Hardness Escalation in Communication Complexity and Query Complexity (Mariposa)
12:25-2:55	LUNCH BREAK (On Own)
2:55-PM- 4:55 PM	Linear Sketching as a Tool for Everything (Angel/Belvedre)	Frontiers in Distribution Testing (Treasure/Yerba)	Hardness Escalation in Communication Complexity and Query Complexity (Mariposa)
4:55PM-5:20PM	COFFEE BREAK
5:20PM- 6:20PM	Linear Sketching as a Tool for Everything (Angel/Belvedre)	Frontiers in Distribution Testing (Treasure/Yerba)	Hardness Escalation in Communication Complexity and Query Complexity (Mariposa)
6:45PM- 9:00PM	FOCS Reception & Celebration in honor of service of Alistair Sinclair Calvin Lab, U.C. Berkeley

                                                                     Workshops Schedules:

. Linear Sketching as a Tool for Everything

Organizers: Andrew McGregor, David Woodruff and Grigory Yaroslavtsev

. Frontiers in Distribution Testing

Organizers: Clement Canonne and Gautam Kamath

. Hardness Escalation in Communication Complexity and Query Complexity

Organizers: Raghu Meka and Toni Pitassi

Oct 15^th Sunday

8:00-9:00am	BREAKFAST
	Session 1A Belvedere/Angel		Session 1B Yerba Buena/Treasure
9:00-9:20	A Nearly Optimal Lower Bound on the Approximate Degree of AC^0 Mark Bun and Justin Thaler.		On the Local Structure of Stable Clustering Instances Vincent Cohen-Addad and Chris Schwiegelshohn.
9:25-9:45	On the Quantitative Hardness of CVP Huck Bennett, Alexander Golovnev and Noah Stephens-Davidowitz.		Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson and Justin Ward.
9:50-10:10	Distributed PCP Theorems for Hardness of Approximation in P Amir Abboud, Aviad Rubinstein and Ryan Williams.		Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures Ilias Diakonikolas, Daniel Kane and Alistair Stewart.
10:15-10:35	Short Presburger arithmetic is hard Danny Nguyen and Igor Pak		On Learning Mixtures of Well-Separated Gaussians Oded Regev and Aravindan Vijayaraghavan
10:35-10:55	Coffee break
	Session 2A Belvedere/Angel		Session 2B Yerba Buena/Treasure
10:55-11:15	On small-depth Frege proofs for Tseitin for GRIDS Johan Hastad.		A Time Hierarchy Theorem for the LOCAL Model Yi-Jun Chang and Seth Pettie.
11:20-11:40	Random log(n)-CNFs are Hard for Cutting Planes Noah Fleming, Denis Pankratov, Toniann Pitassi and Robert Robere. AND Random formulas, monotone circuits, and interpolation Pavel Pudlak and Pavel Hrubes.		Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^5/4) Rounds Chien-Chung Huang, Danupon Nanongkai and Thatchaphol Saranurak.
11:45-12:05	Query-to-Communication Lifting for BPP Mika Göös, Toniann Pitassi and Thomas Watson		Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching Manuela Fischer, Mohsen Ghaffari and Fabian Kuhn
12:10-12:30	A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness Mark Braverman and Rotem Oshman.		Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve Amir Abboud, Arturs Backurs, Karl Bringmann and Marvin Kunnemann.
12:30-2:50	lunch
	Session 3A Belvedere/Angel	Session 3B Yerba Buena/Treasure
2:50-3:10	Local List Recovery of High-rate Tensor Codes & Applications Brett Hemenway, Noga Ron-Zewi and Mary Wootters.	Approximating Geometric Knapsack via L-packings Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan and Andreas Wiese
3:15-3:35	Optimal repair of Reed-Solomon codes: Achieving the cut-set bound Itzhak Tamo, Min Ye and Alexander Barg.	Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments Mark de Berg.
3:40-4:00	Average-case reconstruction for the deletion channel: subpolynomially many traces suffice Yuval Peres and Alex Zhai.	Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations Shi Li.
4:05-4:25	Optimal Interactive Coding for Insertions, Deletions, and Substitutions Alexander Sherstov and Pei Wu.	Fast & Space-Efficient Approximations of Language Edit Distance and RNA-Folding: An Amnesic Dynamic Programming Approach Barna Saha.
4:30-4:50	The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes Daniel Kane, Shachar Lovett and Sankeerth Rao.	A Dichotomy for Regular Expression Membership Testing Karl Bringmann, Allan Grønlund and Kasper Green Larsen
4:50-5:20	COFFEE BREAK
	Session 4 Islands Ballroom
5:20-5:40	A dichotomy theorem for nonuniform CSPs Andrei Bulatov.
5:45-6:05	A Proof of CSP Dichotomy Conjecture Dmitriy Zhuk.
9:00pm	business meeting at Belvedere/Angel room

Oct 16^th Monday

7:30-8:35	BREAKFAST
	Session 5A Belvedere/Angel	Session 5B Yerba Buena/Treasure
8:35-8:55	Learning Graphical Models Using Multiplicative Weights Adam Klivans and Raghu Meka.	Quantum SDP-Solvers: Better upper and lower bounds Joran van Apeldoorn, Andras Gilyen, Sander Gribling and Ronald de Wolf. AND Quantum Speed-ups for Semidefinite Programming Fernando Brandao and Krysta Svore.
9:00-9:20	Active classification with comparison queries Daniel Kane, Shachar Lovett, Shay Moran and Jiapeng Zhang.	Local Hamiltonians Whose Ground States are Hard to Approximate Lior Eldar and Aram Harrow.
9:25-9:45	Capacity of Neural Networks for Lifelong Learning of Composable Tasks Leslie Valiant.	On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma Andras Pal Gilyen and Or Sattath.
9:50-10:10	Efficient Bayesian estimation from few samples: community detection and related problems Samuel Hopkins and David Steurer.	Variable Version Lovász Local Lemma: Beyond Shearer's Bound Kun He, Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia.
10:15-10:35	Robust polynomial regression up to the information theoretic limit Daniel Kane, Sushrut Karmalkar and Eric Price.	Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model Yinan Li and Youming Qiao.
10:35-10:55	Coffee break
	Session 6A Belvedere/Angel	Session 6B Yerba Buena/Treasure
10:55-11:15	Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff and Mobin Yahyazadeh.	Learning Multi-item Auctions with (or without) Samples Yang Cai and Constantinos Daskalakis.
11:20-11:40	First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate Zeyuan Allen-Zhu and Yuanzhi Li.	Oracle-Efficient Online Learning and Auction Design Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis and Jennifer Wortman Vaughan.
11:45-12:05	Weighted k-Server Bounds via Combinatorial Dichotomies Nikhil Bansal, Marek Elias and Grigorios Koumoutsos.	Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs Paul Duetting, Michal Feldman, Thomas Kesselheim and Brendan Lucier.
12:10-12:30	An input Sensitive Online Algorithm for the metric Bipartite Matching problem Krati Nayyar and Sharath Raghvendra.	Tight Lower Bounds for Differentially Private Selection Thomas Steinke and Jonathan Ullman.
12:30-2:50	lunch
	Session 7A Belvedere/Angel	Session 7B Yerba Buena/Treasure
2:50-3:10	How to Achieve Non-Malleability in One or Two Rounds Dakshita Khurana and Amit Sahai.	Optimality of the Johnson-Lindenstrauss lemma Kasper Green Larsen and Jelani Nelson.
3:15-3:35	Two-Round and Non-interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles Huijia Lin, Rafael Pass and Pratik Soni.	Optimal compression of approximate inner products and dimension reduction Noga Alon and Bo'Az Klartag.
3:40-4:00	Garbled Protocols and Two-Round MPC from Bilinear Maps Sanjam Garg and Akshayaram Srinivasan.	Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average Michael Kapralov.
4:05-4:25	Obfuscating Compute-and-Compare Programs under LWE Daniel Wichs and Giorgos Zirdelis. AND Lockable Obfuscation Rishab Goyal, Venkata Koppula and Brent Waters.	Fast Similarity Sketching Søren Dahlgaard, Mathias Bæk Tejs Knudsen and Mikkel Thorup.
4:30-4:50	White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing Moni Naor, Ilan Komargodski and Eylon Yogev.	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices Cameron Musco and David P. Woodruff.
4:50-5:20	COFFEE BREAK
Session 8 Islands Ballroom
5:20-5:40	Hardness Results for Structured Linear Systems Rasmus Kyng and Peng Zhang.
5:45-6:05	The Matching Problem in General Graphs is in Quasi-NC Ola Svensson and Jakub Tarnawski.

Oct 17^th Tuesday

8:00-9:00am	BREAKFAST
	Session 9A Belvedere/Angel	Session 9B Yerba Buena/Treasure
9:00-9:20	On The Power of Statistical Zero Knowledge Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler and Prashant Vasudevan.	Faster (and still pretty simple) unbiased estimators for network (un)reliability David Karger.
9:25-9:45	The Power of Sum-of-Squares for Detecting Hidden Structures Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm and David Steurer.	Minor-free graphs have light spanners Glencora Borradaile, Hung Le and Christian Wulff-Nilsen.
9:50-10:10	A Time-Space Lower Bound for a Large Class of Learning Problems Ran Raz.	Polylogarithmic approximation for minimum planarization (almost) Ken-Ichi Kawarabayashi and Anastasios Sidiropoulos.
10:15-10:35	From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan.	Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time Chandra Chekuri and Kent Quanrud.
10:35-10:55	Coffee break
	Session 10A Belvedere/Angel	Session 10B Yerba Buena/Treasure
10:55-11:15	Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space Jack Murtagh, Omer Reingold, Aaron Sidford and Salil Vadhan.	Testing Hereditary Properties of Ordered Graphs and Matrices Noga Alon, Omri Ben-Eliezer and Eldar Fischer.
11:20-11:40	Deterministic search for CNF satisfying assignments in almost polynomial time Rocco Servedio and Li-Yang Tan.	A characterization of testable hypergraph properties Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus.
11:45-12:05	Fooling intersections of low-weight halfspaces Rocco Servedio and Li-Yang Tan.	Boolean Unateness Testing with ~O(n^{3/4}) Adaptive Queries Xi Chen, Erik Waingarten and Jinyu Xie.
12:10-12:30	Exponentially Hard gap-CSP and local PRG via Local Hardcore Functions Benny Applebaum.	Generalized Uniformity Testing Tugkan Batu and Clément Canonne.
12:30-2:50	lunch
	Session 11A Belvedere/Angel	Session 11B Yerba Buena/Treasure
2:50-3:10	Much Faster Algorithms for Matrix Scaling Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira and Avi Wigderson and Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods Michael B. Cohen, Aleksander Mądry, Dimitris Tsipras and Adrian Vladu.	Optimal Las Vegas Locality Sensitive Data Structures Thomas Dybdahl Ahle.
3:15-3:35	Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices Nima Anari, Leonid Gurvits, Shayan Oveis Gharan and Amin Saberi.	Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen.
3:40-4:00	Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees David Durfee, John Peebles, Richard Peng and Anup B. Rao.	Fast and Compact Exact Distance Oracle for Planar Graphs Vincent Cohen-Addad, Søren Dahlgaard and Christian Wulff-Nilsen.
4:00-4:20	COFFEE BREAK
	Session 12A Belvedere/Angel	Session 12B Yerba Buena/Treasure
4:25-4:45	High dimensional expanders are agreement expanders Irit Dinur and Tali Kaufman.	Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani.
4:50-5:10	The Ising Partition Function: Zeros and Deterministic Approximation Jingcheng Liu, Alistair Sinclair and Piyush Srivastava.	Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration Javad B. Ebrahimi, Damian Straszak and Nisheeth K. Vishnoi.
5:15-5:35	Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion Yin Tat Lee and Santosh Vempala.	Hashing-Based-Estimators for Kernel Density in High Dimensions Moses Charikar and Paris Siminelakis.