We will revisit the paper "New algorithms for the disk scheduling problem", by Matthew Andrews, Michael Bender and Lisa Zhang, FOCS 96.

We will examine the minor algorithm of the paper from several points of view, with some examples of how it proceeds.

Contract design captures situations in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent chooses an action from a set of costly actions. The principal can only observe the outcome, which is stochastically determined by the chosen action. The principal incentivizes the desired action through a contract that specifies payments based on the observed outcome. In this talk, I will survey two papers on combinatorial contracts, which highlight different sources of complexity that arise in contract design. The first (FOCS’21) is where the agent can choose any subset of a given set of actions; the second is where the principal motivates a team of agents. We provide (approximation) algorithms and hardness results for the optimal contract problem in these scenarios.

Based on joint work with Tomer Ezra, Paul Duetting and Thomas Kesselheim.

Efficient verification of computation is fundamental to computer science.  The goal is to construct a scheme that given an arbitrary computation generates a succinct certificate that certifies the correctness of the output.  Such a certificate is referred to as a Succinct Non-Interactive ARGument (SNARG).   Recently SNARGs have had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud computing. 

In this talk, I will present some recent developments:  First, we will argue that to construct a SNARG for arbitrary (deterministic) computations it suffices to construct a SNARG for batch NP (referred to as a BARG).  Then we will show how to convert any semi-succinct BARG into a fully-succinct (rate-1) BARG.  Finally, we will show applications to improving the succinctness of known SNARGs and to SNARG composition, leading to incrementally verifiable computation.    

This is talk is based on results with Lalita Devadas, Rishab Goyal, Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs.

In this talk, I will present a new method that reduces understanding an appropriate notion of girth in hypergraphs to unraveling the spectrum of a "Kikuchi" matrix associated with the hypergraph.

I will discuss three applications of this technique:

1. Finding a refutation algorithm for smoothed instances of constraint satisfaction problems (obtained by randomly perturbing the literal patterns in a worst-case instance with a small probability) that matches the best running-time vs constraint-density trade-offs for the significantly special and easier case of random CSPs,

2. Confirming Feige's 2008 Conjecture that postulated an extremal girth vs density trade-off (a.k.a. Moore bounds) for k-uniform hypergraphs that generalizes the Alon-Hoory-Linial Moore bound for graphs,

3. Proving a cubic lower bound on the block length of 3 query locally decodable codes improving on the prior best quadratic lower bound from the early 2000s.

Based on joint works with Omar Alrabiyah, Tim Hsieh, Peter Manohar, Sidhanth Mohanty, and Venkat Guruswami.

A subset of a group is said to be product free if it does not contain the product of two elements in it. In 1985 Babai and Sos asked, how large

can a product free subset of $A_n$ be?

In the talk, we completely solve the problem when $n$ is sufficiently large.

Our proof combines an idea from representation theory (quasirandomness) with common tools from the analysis of Boolean functions, such as

hypercontractivity and dictatorship tests.

Based on joint work with Peter Keevash and Dor Minzer.

Let f:{0,1}^n \to {0,1} be a Boolean function. It can be uniquely represented as a multilinear polynomial. What is the structure of its monomials?

This question turns out to be connected to some well-studied problems, such as the log-rank conjecture in communication complexity and the

union-closed conjecture in combinatorics. I will describe these connections, and a new structural result, showing that set systems of  monomials of

boolean functions have small hitting sets, concretely of poly-logarithmic size. The proof uses a combination of algebraic, probabilistic and

combinatorial techniques.

Based on joint work with Alexander Knop, Sam McGuire, and Weiqiang Yuan.

The isoperimetric theorem bounds from below the surface area of a set with specified volume. The goal of reverse isoperimetry is to bound the surface area from above for suitable classes of sets. Such endeavors are old and useful, but in this talk I will describe recent (mostly conjectural) twists on this theme. These have various applications to topics such as clustering and rounding, which will be explained in the talk, but surely more applications await. 

In Part I, I will describe recent progress on the complexity of approximating the maximum matching, based on joint work with Soheil Behnezhad and Mohammad Roghani (arxiv.org/abs/2211.15843).

In Part II, I will share a fantasy that begins with the complexity of matching (Part I), connects to questions in fine-grained complexity, black-box-vs-white-box, and even *your* subfield.

A basic mechanism in the theory of machine learning is characterizing learnability by dimension-like quantities. The talk shall provide a high-level

description of this mechanism, and survey several characterization results. The main technical focus will be our recent work with Brukhim, Carmon,

Dinur and Moran that characterizes multiclass PAC learnability.