Seminars Sorted by Series

Some important mechanisms considered in game theory require solving optimization problems that are computationally hard. Solving these problems approximately may not help, as it may change the players’ rational behavior in the original mechanisms...

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms...

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm)...

An “oblivious subspace embedding” (OSE) is a distribution over matrices S such that for any low-dimensional subspace $V$, with high probability over the choice of $S$, $\|Sx\|_2$ approximately equals $\|x\|_2$ (up to $1 + \epsilon$ multiplicative...

Abstract: We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show: (1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up...

A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under...

Ultrametrics are special metrics satisfying a strong form of the triangle inequality: For every $x, y, z$, $d(x, z) \impliedby \max\{d(x, y), d(y, z)\}$. We consider Ramsey-type problems for metric spaces of the following flavor:

Every metric space...

Expander graphs, in general, and Ramanujan graphs, in particular, have been objects of intensive research in the last four decades. Many application came out, initially to computer science and combinatorics and more recently also to pure mathematics...

I will describe the very recent breakthrough result by Gupta, Kamath, Kayal and Saptharishi which shows that every polynomial P in n variables, of degree d which is polynomial in n, and which can be computed by a polynomial sized arithmetic circuit...

I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll...

I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms. The material of this talk will assume only little knowledge from the first talk.

There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this...

There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this...

We give an arithmetic version of the recent proof of the improved triangle removal lemma by Fox [Fox11], for the group F_2^n. A triangle in F_2^n is a tuple (x,y,z) such that x+y+z = 0. The triangle removal lemma for F_2^n states that for every \eps...

We all know Shannon's entropy of a discrete probability distribution. Physicists define entropy in thermodynamics and in statistical mechanics (there are several competing schools), and want to prove the Second Law, but they didn't succeed yet (very...

Informally, uncertainty principle says that function and its Fourier transform can not be both concentrated. Uncertainty principle has a lot of applications in areas like compressed sensing, error correcting codes, number theory and many others. In...

We study algorithms for combinatorial market design problems, where a collection of objects are priced and sold to potential buyers subject to equilibrium constraints. We introduce the notion of a combinatorial Walrasian equilibium (CWE) as a...

The Kakeya and restriction conjectures are two of the central open problems in Euclidean Fourier analysis (with the second logically implying the first, and progress on the first typically implying progress on the second). Both of these have...

A common way for lower bounding the expansion of a graph is by looking the second smallest eigenvalue of its Laplacian matrix. Also known as the easy direction of Cheeger's inequality, this bound becomes too weak when the expansion is \(o(1)\). In...

In this lecture, I will talk about moment based SDP hierarchies (which are duals of SOS relaxations for polynomial optimization) in the context of graph partitioning. The focus will be on a certain way of rounding such hierarchies, whose quality is...

Motivated by questions in Social Choice Theory I will consider the following extremal problem in Combinatorial Geometry. Call a sequence of vectors of length \(n\) with \(-1\), \(1\) entries feasible if it contains a subset whose sum is positive in...

Classical matrix perturbation bounds, such as Weyl (for eigenvalues) and David-Kahan (for eigenvectors) have, for a long time, been playing an important role in various areas: numerical analysis, combinatorics, theoretical computer science...

We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube \(\{-1,1\}^n\). As in the standard PAC learning model, a learning problem in our framework is defined by a class \(C\) of Boolean...

In this talk we will present an overview of the hypermatrix generalization of matrix algebra proposed by Mesner and Bhattacharya in 1990. We will discuss a spectral theorem for hypermatrices deduced from this algebra as well as connections with...

In a profoundly influential 1948 paper, Claude Shannon defined the entropy function \(H\), and showed that the capacity of a symmetric binary channel with noise rate (bit flip rate) \(\mathrm{eps}\) is \(1-H(\mathrm{eps})\). This means that one can...

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,\(P \not\subseteq NC_1\) ). This problem is interesting both because it is tightly related to understanding the...

We will discuss interactive coding in the setting where there are n parties attempting to compute a joint function of their inputs using error-prone pairwise communication channels. We will present a general protocol that allows one to achieve only...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

We will discuss space and parallel complexity, ranging from some classical results which motivated the study, to some recent results concerning combinatorial lower bounds in restricted settings. We will highlight some of their connections to boolean...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

I will survey what is known about the complexity of arithmetic circuits computing polynomials and rational functions with non-commuting variables, focusing on recent results and open problems. Strangely enough, some elementary questions in...

I will continue last week's discussion of this model, this time giving sketches of proofs of some of the theorems. No technical background is necessary for this lecture, but for motivation and background it is good to consult the Tue Feb 11 talk...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that this is the right answer, assuming that we do...

In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. This graph expansion...

The goal of computationally sound symbolic security is to create formal systems of cryptography which have a sound interpretation with respect to complexity-based notions of security. While there has been much progress in the development of such...

Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to...

The P != NP conjecture doesn't tell us what runtime is needed to solve NP-hard problems like 3-SAT and Hamiltonian Path. While some clever algorithms are known, they all require exponential time, and some researchers suspect that this is unavoidable...

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a...

I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1...

In the last few years, there has been a lot of activity in the area of structural analysis and derandomization of polynomial threshold functions. Tools from analysis and probability have played a significant role in many of these works. The focus of...

In this talk, we will continue, the proof of the Central Limit theorem from my last talk. We will show that that the law of "eigenregular" Gaussian polynomials is close to a Gaussian. The proof will be based on Stein's method and will be dependent...