FoCS Theory Day 2023

Schedule

Morning Session

Tea and Coffee (9:45 - 10:00)

Welcome Remarks (10:00 - 10:10)

Long Talks (10:10 - 11:10)

• Marcel Dall'Agnol - Kilian's protocol: from PCPs to succinct arguments

• Mary Scott - On the differentially private comparison of probability distributions

• Henry Sinclair-Banks - The Complexity of Coverability in Vector Addition Systems with States

Coffee Break (11:10 - 11:40)

Long Talks (11:40 - 12:20)

• Hugo Aaronson - Distribution-Free Proofs of Proximity

• Siddharth Gupta - Drawing Graphs on the Grid: How Easy Is It?

Lunch

Lunch and Photo Session (12:20 - 14:00)

Afternoon Session

Talk by Alex Dixon - The Carefully-Guarded Secret To A Good Explanation (14:00 - 14:25)

Talk by Ranko Lazic - An ostrich for ten squares, and learning better by starting very small (14:25 - 14:50)

Coffee Break (14:50 - 15:15)

Short Talks (15:15 - 16:15)

• Namrata - The hardness of Gray code problems

• Martin Costa - Streaming Edge Coloring

• Christian Ikenmeyer - Homogeneous Algebraic Complexity

• Peter Strulo - Parameterized Fault Tolerant Oracles

Coffee Break (16:15 - 16:45)

Open Problem Session (16:45 - 17:30)

• Gopinath Mishra - Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond

• Martin Costa - Low Recourse Dynamic Edge Coloring

• Gregory Rosenthal - Open problems in quantum state and unitary complexity

• Marcel Dall'Agnol - Classical vs. Quantum IPPs.

• Hugo Aaronson - Distribution-Free IPP Separation.

Research Discussions (17:30 - 18:00)

Dinner

Dinner at Radcliffe (18:00 - 19:30)

For any information about this event, please contact the organizers: Martin Costa, Anish Mukherjee, Hugo Aaronson

Talk Abstracts

Mary Scott - On the differentially private comparison of probability distributions

In this talk, we focus on privately estimating the distance between the distribution of data evolving with time to probe the traits of their development. It is very 

important to be able to compare the histograms of data while preserving the privacy of the users. For example, we might have a snapshot of a distribution from last year, and we would like to compare it to the distribution of values held by a large population. The private comparison of data distributions can be extended to mainstream machine learning to facilitate a privacy-preserving comparison of training sets with the public knowledge of the test set.

Henry Sinclair-Banks - The Complexity of Coverability in Vector Addition Systems with States

A d-dimensional vector addition system with states can be seen as a directed graph whose edges are labelled with d-dimensional integer vectors. The coverability problem asks from an initial node whether there exists a path to a target node such that sum of the vectors observed along the path remains non-negative on all k components. The problem and its complexity has been studied in great detail, as already since the late seventies, coverability is known to require exponential space but can also be decided using exponential space. In this presentation I will define the problem, overview its history, and describe the state-of-the-art.

Hugo Aaronson - Distribution-Free Proofs of Proximity

We give a simple example of a proof of proximity in the distribution-free setting demonstrating a complexity separation between testing and verification.

Siddharth Gupta - Drawing Graphs on the Grid: How Easy Is It?

Grid graphs, and, more generally, $k \times r$ grid graphs, form one of the most basic classes of geometric graphs. Over the past few decades, a large body of work has studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is particularly hard -- it was shown to be NP-hard even on trees of pathwidth 3 already in 1987. In this talk, I will talk about a positive result in this regard in the framework of parameterized complexity. I will also briefly talk about the area of Graph Drawing and Parameterized Complexity whose intersection this problem lies in.

Alex Dixon - The Carefully-Guarded Secret To A Good Explanation

There are many skills involved in being a competent and capable public speaker. We've all been to talks, seminars or lectures where, through no fault of our own, we leave understanding less than when we arrived. In this talk we shall speak about some simple, low-effort ways to improve your communication skills and create deep understanding in your audience.

Namrata - The hardness of Gray code problems

It is well-known that the Hamilton Path problem is NP-complete for grid graphs. Stated another way, the Hamilton Path problem is NP-compete for the induced subgraphs of rectangular grid graphs. In this work, we establish the same result for the induced subgraphs of dozens of natural families of graphs. Each result is obtained by a polynomial-time induced subgraph reduction to a rectangular grid graph, hypercube, or permutohedron. Our work is motivated by the computational complexity of determining if Gray codes exist for subsets of combinatorial objects under simple operations.

Martin Costa - Streaming Edge Coloring

Edge coloring is a fundamental problem in combinatorics that has been extensively studied by computer scientists across many computational models. In many computational models, it is fairly trivial to obtain a (2D - 1)-edge coloring, where D is the maximum degree of the graph. One exception to this is the streaming setting, where even just obtaining a O(D)-edge coloring is a non-trivial task. In this talk, I will illustrate some of the technical challenges present in this setting, as well as recent developments that have successfully made progress in this area.

Christian Ikenmeyer - Homogeneous Algebraic Complexity

In this short talk we compare algebraic circuit models with AFFINE linear inputs with algebraic circuit models with HOMOGENEOUS linear inputs, which are commonly used in the study of fast matrix multiplication.

Peter Strulo - Parameterized Fault Tolerant Oracles

This talk will introduce and discuss some recent results on fault-tolerant fixed-parameter oracles, a recent extension of sensitivity oracles to NP-hard problems.