Seminars Sorted by Series

I will introduce two notions that generalize the idea of real rootedness to multivariate polynomials: real stability and hyperbolicity. I will then show two applications of these types of polynomials that will (hopefully) be of interest to the CS...

The sum-of-squares (SOS) method is a conceptually simple algorithmic technique for polynomial optimization that---quite surprisingly---captures and generalizes the best known efficient algorithms for a wide range of NP-hard optimization problems...

We prove that there exists a constant $\epsilon > 0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player ($n \times n$) game requires quasi-polynomial time, $n^{\log^{1-o...

In the matrix completion problem, we have a matrix $M$ where we are only given a small number of its entries and our goal is to fill in the rest of the entries. While this problem is impossible to solve for general matrices, it can be solved if $M$...

Seeded and seedless non-malleable extractors are non-trivial generalizations of the more commonly studied seeded and seedless extractors. The original motivation for constructing such non-malleable extractors are from applications to cryptography...

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient...

In this talk I will review some of the classical (and fundamental) results in the theory of graph rigidity.

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size...

Let $P:\{0,1\}^k \to \{0,1\}$ be a $k$-ary predicate. A random instance of a constraint satisfaction problem (CSP(P)) where each of the $\Delta n$ constraints is $P$ applied to $k$ literals on $n$ variables chosen at random is unsatisfiable with...

This will be a bit of a "grab bag" talk where I discuss some results and open questions in combinatorial geometry which are either approachable by the polynomial method or which I hope are approachable by the polynomial method! I will talk about...

The sensitivity conjecture is a famous open problem in the theory of boolean functions. Let $f$ be a boolean function defined on the hypercube. The sensitivity of a node $x$ is the number of its neighbours in the hypercube, for which $f$ give the...

Sketching for distance estimation is the problem where we need to design a possibly randomized function $F$ from a metric space to short strings, such that for any points $x,y$ from the metric space, the "sketches" $F(x)$ and $F(y)$ are sufficient...

In recent years, there has been a surge of exciting research activity at the interface of optimization (in particular polynomial, semidefinite, and sum of squares optimization) and the theory of dynamical systems. In this talk, we focus on two...

We provide a duality framework for Bayesian Mechanism Design. Specifically, we show that the dual problem to revenue maximization is a search over virtual transformations. This approach yields a unified view of several recent breakthroughs in...

This talk will survey recent progress on program obfuscation from feasibility results to applications in cryptography and complexity theory. We will also describe a simple obfuscation construction based on cryptographic multi-linear maps and give a...

The celebrated Brascamp-Lieb (BL) inequalities are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. I will survey the well...

Invariant theory deals with properties of symmetries - actions of groups on sets of objects.It has been slower to join its sibling mathematical theories in the computer science party, but we now see it more and more in studies of computational...

Indistinguishability obfuscation has turned out to be an outstanding notion with strong implications not only to cryptography, but also other areas such as complexity theory, and differential privacy. Nevertheless, our understanding of how to...

Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint...

We will give a high-level overview of computable analysis---an area studying the computational properties of continuous objects such as functions and measures on $\mathbb R^d$. We will then discuss some applications to the computability and...

I will give an introduction to computational techniques in noncommutative probability for people (like myself) that are less interested in the details of the theory and more interested using results in the theory to help understand the behavior of...

I will discuss methods for deriving bounds on the roots of polynomials, and how one can use such bounds to assert the existence of combinatorial structures with certain spectral properties. This will include introducing the "method of interlacing...

Communication complexity studies the minimal amount of information two parties need to exchange to compute a joint function of their inputs. Results, especially lower bounds in this basic model found applications in many other areas of computer...

I will survey some elementary (to state!) problems on groups, matrices, and tensors, and discuss their motivations arising from several major problems in computational complexity theory. On each problem there was some exciting recent progress which...

Invariant theory studies the actions of groups on vector spaces and what polynomial functions remain invariant under these actions. An important object related to a group action is the null cone, which is the set of common zeroes of all homogeneous...

Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.For example, for any constant $k$, we construct linear decision...

A cap set in $(F_q)^n$ is a set not containing a three term arithmetic progression. Last year, in a surprising breakthrough, Croot-Lev-Pach and a follow up paper of Ellenberg-Gijswijt showed that such sets have to be of size at most $c^n$ with $c q...

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and...

A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object...

Neural networks have been around for many decades. An important question is what has led to their recent surge in performance and popularity. I will start with an introduction to deep neural networks, covering the terminology and standard approaches...

Geometric Complexity Theory (GCT) was developed by Mulmuley and Sohoni as an approach towards the algebraic version of the P vs NP problem, VP vs VNP, and, more generally, proving lower bounds on arithmetic circuits. Exploiting symmetries, it...

Proof complexity studies the problem computer scientists and mathematicians face every day: given a statement, how can we prove it? A natural and well-studied question in proof complexity is to find upper and lower bounds on the length of the...

We study the complexity of constructing a hitting set for the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we...

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality...

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$...

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent...

The talk will motivate recent work on saturation of ultrapowers from a general mathematical point of view, emphasizing some connections to combinatorics.

In a sequence of extremely fundamental results in the 80's, Kaltofen showed that any factor of n-variate polynomial with degree and arithmetic circuit size poly(n) has an arithmetic circuit of size poly(n). In other words, the complexity class VP is...

We will discuss a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform a...

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the...

Let F be a family of subsets over a domain X that is closed under taking intersections. Such structures are abundant in various fields of mathematics such as topology, algebra, analysis, and more. In this talk we will view these objects through the...

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...

Algorithmic graph partitioning tasks are naturally related to geometric issues. Over the past decades, several deeper connections of this type have emerged. In this talk, we will describe one example by showing that, up to lower order factors, the...

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth...

We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.

Dadush and...

Tensors occur throughout mathematics. Their rank, defined in analogy with matrix rank, is however much more poorly understood, both from a structural and algorithmic viewpoints.

This will be an introductory talk to some of the basic issues...

These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

M...