Oct 14th 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 15th 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 Õ(n5/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 16th 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 17th 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.