Seminars Sorted by Series

We will describe a recently discovered connection between private information retrieval and secret sharing, and a new secret-sharing scheme for general access structures that breaks a long-conjectured exponential barrier.

Based on joint work with...

Edit distance is a widely used measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a...

For a family of graphs F, a graph G is F-universal if G contains every graph in F as a (not necessarily induced) subgraph. A natural candidate to serve as universal graph G is the random graph G(n,p). In this case, we want to find an optimal p for...

Let X be the infinite graph partially pictured below, the "free product graph" C_4 * C_4 * C_4. Let FinQuo(X) be the set of all finite graphs G that covered by X (i.e., that 'locally resemble' X; i.e., that consist of C_4's joined 3-to-a-vertex). A...

The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will describe several attempts on how to get improved bounds for it. These will lead to surprising connections with several other...

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a...

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a...

Chernoff-type bounds study concentration of sums of independent random variables and are extremely useful in various settings. In many settings, the random variables may not be completely independent but only have limited independence. One such...

In this talk, I will give an overview on how PCPs, combined with cryptographic tools, are used to generate succinct and efficiently verifiable proofs for the correctness of computations. I will focus on constructing (computationally sound) *succinct...

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs.

The...

A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit...

A matroid is an abstract combinatorial object which generalizes the notions of spanning trees, and linearly independent sets of vectors. I will talk about an efficient algorithm based on the Markov Chain Monte Carlo technique to approximately count...

The emerging theory of High-Dimensional Expansion suggests a number of inherently different notions to quantify expansion of simplicial complexes. We will talk about the notion of local spectral expansion, that plays a key role in recent advances in...

We answer a 1982 conjecture of Erd&‌#337;s and Simonovits about the growth of number of $k$-walks in a graph, which incidentally was studied earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier...

We show that, as a consequence of a remarkable new result of Attila P\'or on universal Tverberg partitions, any large-enough set $P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon point has half-space depth at least $c_d \cdot |P|$...

Constraint satisfaction problems (CSPs) are a central topic of study in computer science. A fundamental question about CSPs is as follows. Given a CSP where each constraint has the form of some predicate P and almost all of the constraints can be...

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a...

The seminal result of Kahn, Kalai and Linial implies that a coalition of a small number of players can bias the outcome of a Boolean function with respect to the uniform measure. We extend this result to arbitrary product measures, by combining...

Worst-case analysis of algorithms has been the central method of theoretical computer science for the last 60 years, leading to great discoveries in algorithm design and a beautiful theory of computational hardness. However, worst-case analysis can...

A sunflower with $r$ petals is a collection of $r$ sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least...

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...