Seminars Sorted by Series

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

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