Seminars Sorted by Series

The choiceless computation model of Blass, Gurevich and Shelah (1999, 2002) is an algorithmic framework for computing isomorphism-invariant properties of unordered structures. Machines in this model have the power of parallel execution, but lack the...

The problem of learning arithmetic circuits is the following: given a polynomial as a black box that is promised to have a small arithmetic circuit computing it, can we find this arithmetic circuit? This problem is hard in the worst case and so...

Scaling problems, such as operator scaling and tensor scaling, have recently found several applications in diverse areas of math and CS. They have been used to give efficient algorithms for non-commutative rational identity testing, compute the...

A (k,m)-Furstenberg set K in F^n, where F is a finite field, is a set such that any k-dimensional subspace of F^n can be shifted so that it intersects K in at least m points. Such sets generalize in a natural way finite field Kakeya sets (in which k...

In this work, we exploit the ill-posedness of linear inverse
problems to design algoithms to release differentially private data or
measurements of the physical system. We discuss the spectral
requirements on a matrix such that only a small amount...

I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a “stability” version of Harper’s edge-isoperimetric inequality, which was first proved by Friedgut, Kalai and Naor for half...

In this talk, I'll illustrate how to lift a "small" locally testable code via a high dimensional expander (HDX) to a "large" locally testable code. Given a D-left regular bipartite graph G = ([n], [m], E) and a "small" code C \in {0,1}^D, the Tanner...

Given a family of m matchings in a graph G (where each matching can be thought of as a color class), a rainbow matching is a choice of edges of distinct colors that forms a matching. How many matchings of size n are needed to guarantee the existence...

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple...

Given an increasing family F in {0,1}^n, its measure according to mu_p increases and often exhibits a threshold behavior, growing quickly as p increases from near 0 to near 1 around a specific value p_c. Thresholds of families have been of great...

Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is the equality function. However, in many examples where randomness helps, having an efficient way...

MIP* (pronounced “M-I-P star”) denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of MIP*. Most notably, there was no known computable upper...

Expanders have grown to be one of the most central and studied notions in modern graph theory. It is thus only natural to research extremal properties of expanding graphs. In this talk we will adapt the following (rather relaxed) definition of...

We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2]...

Given a separation oracle for a convex set $K \subset \mathbb{R}^n$ that is contained in a box of radius $R$, the goal is to either compute a point in $K$ or prove that $K$ does not contain a ball of radius $\epsilon$. We propose a new cutting plane...

Machine Learning is invaluable for extracting insights from large volumes of data. A key assumption enabling many methods, however, is having access to training data comprising independent observations from the entire distribution of relevant...

To connect to the CSDM Seminar via Zoom, please do the following: 1 - If you have Zoom installed on your device, enter the following meeting ID: 360043913 , click Join Meeting. 2 - If you do not have Zoom installed, click the following link to...

We say a body B tiles the space R^n if the shifted bodies (B+z), for z\in Z^n, are all disjoint and cover R^n. In this talk, we consider the problem of finding the least surface area a tiling body B can have, for bodies B symmetric under coordinate...

A theorist's dream is to show that hard instances/obstructions for an (optimal) algorithm can be used as gadgets to prove tight hardness reductions (which proves optimality of the algorithm). An example of such a result is that of Prasad Raghavendra...

I'll be presenting some joint work with Ian Mertz scheduled to appear at STOC 2020. The study of the Tree Evaluation Problem (TEP), introduced by S. Cook et al. (TOCT 2012), is a promising approach to separating L from P. Given a label in [k] at...

There are significant gaps between legal and technical thinking around data privacy. Technical standards such as k-anonymity and differential privacy are described using mathematical language whereas legal standards are not rigorous from a...

The dichotomy between structure and randomness plays an important role in areas such as combinatorics and number theory. I will discuss a similar dichotomy in complexity theory, and illustrate it with three examples of my own work: (i) An...

A weighted graph H is a sparsifier of a graph G if H has much fewer edges than G and, in an appropriate technical sense, H "approximates" G. Sparsifiers are useful as compressed representations of graphs and to speed up certain graph algorithms...

We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned into k communities, and a graph is sampled...

In randomized experiments, such as a medical trials, we randomly assign the treatment, such as a drug or a placebo, that each experimental subject receives. Randomization can help us accurately estimate the difference in treatment effects with...

Linear dynamical systems are a continuous subclass of reinforcement learning models that are widely used in robotics, finance, engineering, and meteorology. Classical control, since the work of Kalman, has focused on dynamics with Gaussian i.i.d...

It is known that any opened necklace with beads of n types can be partitioned by at most (k-1)n cuts into intervals that can be distributed into k collections, each containing the same number of beads of each type (up to 1). The proof is topological...

In this talk I will introduce constructions of finite graphs which resemble some given infinite graph both in terms of their local neighborhoods, and also their spectrum. These graphs can be thought of as expander graphs with local constraints in a...

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel t times is at most $t^{-\Omega(1)}. Previously, only a bound of roughly 1 /...

We introduce two new notions for polynomials associated with discrete set-valued probability distributions. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under a number of...

We prove new lower bounds on the well known Gap-Hamming problem in communication complexity. Our main technical result is an anti-concentration bound for the inner product of two independent random vectors. We show that if A, B are arbitrary subsets...

Suppose we have a cancellative binary associative operation * on a finite set X. We say that it is delta-associative if the proportion of triples x, y, z such that x*(y*z) = (x*y)*z is at least delta.

Gowers and Long studied somewhat associative...

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new...

What can we say on a convex body from seeing its projections? In the 80s, Lutwak introduced a collection of measurements that capture this question. He called them the affine quermassintegrals. They are affine invariant analogues of the classical...

What combinatorial properties are likely to be satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball of fixed radius? What about any combinatorial rectangle of fixed side...

A recent line of work has focused on the following question: Can one prove strong unconditional lower bounds on the number of samples needed for learning under memory constraints? We study an extractor-based approach to proving such bounds for a...