Seminars Sorted by Series

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections...

The complexity of simple stochastic games (SSGs) has been open since they were defined by Condon in 1992. Such a game is played by two players, Min and Max, on a graph consisting of max nodes, min nodes, and average nodes. The goal of Max is to...

We study the local testabilty of sparse linear codes. This problem is intimately connected to the problem of tolerant linearity testing of Boolean functions under nonuniform distributions. We give linearity tests for several natural and interesting...

Non-relativization of complexity issues can be interpreted as giving evidence that these issues cannot be resolved by “black-box” techniques. We show that the assumption $DistNP \subseteq AvgP$ does not imply that $NP\subseteq BPP$ by relativizing...

We define a polynomial threshold function to be a function of the form f(x) = sgn(p(x)) for p a polynomial. We discuss some recent techniques for dealing with polynomial threshold functions, particular when evaluated on random Gaussians. We show how...

In this talk, I will give new proofs for the hardness amplification of fficiently samplable predicates and of weakly verifiable puzzles. More oncretely, in the first part of the talk, I will give a new proof of Yao's XOR-Lemma as well as related...

Given a matrix $A$, it can be shown that there is a vector $z \in 0,1^n$ for which $|Az|/|Z| \geq |A|_2/C \log(n)$ (a0/1 sum of columns of $A$ which witnesses its large spectral norm) for instance by discretizing the top singular vector of $A$ and...

How to color $3$ colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses $n^{0.2130}$ colors. We explore the possibility that more levels of Lasserre Hierarchy can give improvements over...

Decompositions in theorems in classical Fourier analysis which decompose a function into large Fourier coefficients and a part that is pseudorandom with respect to (has small correlation with) linear functions. The Goldreich-Levin theorem [GL89] can...

We show existence of rigid combinatorial objects that previously were not known to exist. Specifically, we consider two families of objects: 1. A family of permutations on n elements is t-wise independent if it acts uniformly on tuples of t elements...

A locally correctable code (LCC) is an error correcting code mapping d symbols to n symbols, such that for every codeword c and every received word r that is \delta-close to c, we can recover any coordinate of c (with high probability) by only...

We present a unified approach to various topics in mathematics including: Ergodic theory, graph limit theory, hypergraph regularity, and Higher order Fourier analysis. The main theme is that very large complicated structures can be treated as...

We present a unified approach to various topics in mathematics including: Ergodic theory, graph limit theory, hypergraph regularity, and Higher order Fourier analysis. The main theme is that very large complicated structures can be treated as...

We prove that a uniformly chosen proper coloring of Z_{2n}^d with 3 colors has a very rigid structure when the dimension d is sufficiently high. The coloring takes one color on almost all of either the even or the odd sub-lattice. In particular, one...

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are...

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are...

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. Many hardness reductions and constructions of integrality gap instances use the long code as a core gadget. However, this...

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. Many hardness reductions and constructions of integrality gap instances use the long code as a core gadget. However, this...

This is a survey talk about different attempts to deal with the very troubling phenomena of independence in Set Theory.

For modern SAT solvers based on DPLL with clause learning, the two major bottlenecks are the time and memory used by the algorithm. This raises the question of whether this memory bottleneck is inherent to Resolution based approaches, or an artifact...

The P vs. NP problem has sometimes been unofficially paraphrased as asking whether it is possible to improve on exhaustive search for such problems as Satisfiability, Clique, Graph Coloring, etc. However, known algorithms for each of these problems...

The Resolution proof system is among the most basic and popular for proving propositional tautologies, and underlies many of the automated theorem proving systems in use today. I'll start by defining the Resolution system, and its place in the proof...

A randomness extractor is an efficient algorithm which extracts high-quality randomness from a low-quality random source. Randomness extractors have important applications in a wide variety of areas, including pseudorandomness, cryptography...

In this talk I will present a colored version of Tverberg's theorem about partitioning finite point sets in R^d into rainbow groups whose convex hulls intersect. This settles the famous Bárány-Larman conjecture (1992) for primes minus one, and...

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. I will describe this approach and show how it can be used to show that bounded independence fools polynomial threshold functions over...

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. This is a continuation of my talk from last week, and I will continue to describe this approach and show how it can be used to show...

The polynomial Freiman-Ruzsa conjecture is one of the important open problems in additive combinatorics. In computer science, it already has several diverse applications: explicit constructions of two-source extractors; improved bounds for the log...

A basic fact of algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only...

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs...

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching 1 while simultaneously allowing for sublinear-time error-correction. In this...

A property of finite graphs is called nondeterministically testable if it has a "certificate'' such that once the certificate is specified, its correctness can be verified by random local testing. In this talk we consider certificates that consist...

We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once constant depth circuits with unbounded fan-in AND, OR, NOT and...

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin and Efremenko and are the only known families of LDCs with a...

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a...

A $q$-query Locally Decodable Code (LDC) is an error-correcting code that allows to read any particular symbol of the message by reading only $q$ symbols of the code word. In this talk we present a new approach for the construction of LDCs from the...

In this seminar I will discuss the details of the result that knottedness is in NP assuming the generalized Riemann hypothesis. The main part of the work is to properly understand Koiran's construction that solvability of a system of algebraic...

Shor's algorithm, the hallmark quantum algorithmic breakthrough, has been successfully generalized to address a variety of related algebraic problems. Generalizations to nonabelian settings could have striking consequences, but such efforts have...

A twenty-year old conjecture by Manickam, Mikl\'os, and Singhi asked whether for any integers $n, k$ satisfying $n \ge 4k$, every set of $n$ real numbers with nonnegative sum always has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is...

One of the major insights of the ``fixed-parameter tractability’’ (FPT) approach to algorithm design is that, for many NP-hard problems, it is possible to efficiently *shrink* instances which have some underlying simplicity. This preprocessing can...

I present some of the very fundamental notions in game theory, with emphasis on their role in the theory of mechanism design and implementation. Examples include (1) normal-form games: Nash equilibrium and full implementation, dominant strategy...

Many problems from complexity theory can be phrased in terms of tensors. I will begin by reviewing basic properties of tensors and discussing several measures of the complexity of a tensor. I'll then focus on the complexity of matrix multiplication...