Seminars Sorted by Series

The notion of a ``market'' has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by companies such as Google, Yahoo!, Amazon, MSN and Ebay. These markets are computationally...

Valiant's theory of holographic algorithms is a new design method to produce polynomial time algorithms. Information is represented in a superposition of linear vectors in a holographic mix. This mixture creates the possibility for exponential sized...

A network creation game abstracts a network construction by selfish agent who build a network by buying links to each other. Each player pays a fixed cost per link, and suffers an additional communication cost (which is the sum of distances to the...

I will present a result that shows hardness of weak PAC-learning intersection of two halfspaces using a hypothesis which is an intersection of k halfspaces for any (fixed) integer k. Specifically, for every integer k and an arbitrarily small...

A graph separator is a set of edges whose deletion partitions the graph into two (or more) pieces. Finding small graph separators is a fundamental combinatorial problem with numerous applications. Interest in it also derives from its theoretical...

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1 - p. 2. At each stage k comparisons can be performed in parallel and a noisy answer...

Hardness amplification is a major line of research that mainly seeks to transform a given lower bound (e.g. a function that has correlation at most 99% with small circuits) into a strongly average-case one (i.e. a function that has negligible...

Avoider-Enforcer games are a misere version of somewhat more popular Maker-Breaker games. An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph H=(V,E) (typically the vertices of H are the edges of the...

A given function f(x) is "hard on average" with respect to an algorithm A , if A(x) disagrees with f(x) on "many" inputs x. Applications in cryptography and derandomization require functions that are "very hard on average" (essentially unpredictable...

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where...

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption...

The disjointness function---determining if a number of sets share a common element---is a notorious example in communication complexity of a function which is hard, but it is hard to show it is hard. Determining both the randomized and quantum...

A Freiman isomorphism is a fundamental object in additive combinatorics that allows one to move an additive problem from one group to another, all while preserving the salient additive properties. In this talk, we will discuss a new mapping result...

We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that ``a distribution property in the class is testable if and only if the Canonical Tester tests it''. We...

Learning theory, and in particular PAC learning, was introduced by Valiant in 1984 and has since become a major area of research in theoretical and applied computer science. One natural question that was posed at the very inception of the field is...

We prove that every key exchange protocol in the random oracle model in which the honest users make at most $n$ queries to the oracle can be broken by an adversary making $O(n^2)$ queries to the oracle. This improves on the previous $\Tilde{O}(n^6)$...

Let G be a finitely generated group equipped with the word metric. Assume that G does not admit a bi-Lipschitz embedding into Hilbert space. How can we quantify the extent to which G is non-Hilbertian? A natural approach is to consider the Hilbert...

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption...

Recently, algebraic codes which achieve the optimal trade-off between rate and (list) error-correction radius were constructed by a careful "folding" of the Reed-Solomon code. The "low-degree'' nature of this folding operation was crucial to the...

A Kakeya set in F^n , where F is a finite field, is a set containing a line in every direction. The finite field Kakeya conjecture states that the size of such sets is bounded from below by C_n*|F|^n , where C_n depends only on the dimension n . I...

In 1982 Linial and Berge conjectured that there is some form of duality between partitioning the vertices of a directed graph to disjoint paths and finding a big set of vertices in it with a small chromatic number. In the talk I will discuss the...

I will discuss this problem: given rational functions f and g over a field K , determine whether there are nonconstant rational functions u and v over K such that u(f(x)) = v(g(x)) . An equivalent problem is to compute the intersection of two fields...

We present the first local list-decoding algorithm for the r-th order Reed-Muller code RM(r,m) over F_2 for r>1 . Given an oracle for a received word R: F_2^m to F_2 , our randomized local list-decoding algorithm produces a list containing all...

We study the model of approximation and calculation of constant degree multivariate polynomials over finite fields. We prove that if a constant degree polynomial can be approximated by a function of a constant number of lower degree polynomials, it...

This talk describes new explicit constructions of dispersers for affine sources of dimension below the notorious n/2 threshold. The main novelty in our construction lies in the method of proof which relies (solely) on elementary properties of...

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Denoting by val(G) the value of a two-prover unique game G, and by sdp(G) the value of a natural semidefinite program to...

Razborov and Rudich have shown that so-called natural proofs are not useful for separating P from NP unless hard pseudorandom number generators do not exist. This famous result is widely regarded as a serious barrier to proving strong lower bounds...

We give a (1+eps)-speed Theta(1/eps^2)-competitive nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of total response time.

For a graph G , let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. We study the problem of bounding t(G) for graphs which do not contain a complete graph K_r on r vertices. This problem was posed twenty years...

Getting the deterministic complexity closer to the best known randomized complexity is an important goal in algorithms and communication protocols. In this work, we investigate the case where instead of one input, the algorithm/protocol is given...

Recently, Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi introduced a natural metric on the space of dense graphs, and identified the completion of the metric space that arises. Independently and simultaneously, Janson, Riordan and I defined a...

The ``direct product code'' of a function $f$ gives its values on all $k$-tuples $(f(x_1),\dots,f(x_k))$. This basic construct underlies “hardness amplification” in cryptography, circuit complexity and PCPs. A recent breakthrough by Dinur and...

We study combinatorial group testing schemes for learning d-sparse boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise...

Since the work of Karp and Lipton in the 1980s, complexity theorists know and love the /poly operator, which adds a polynomial-sized advice string to any complexity class. But it's interesting to consider much more general kinds of "advice objects"...

This series of three talks will give a nontechnical, high level overview of geometric complexity theory (GCT), which is an approach to the P vs. NP problem via algebraic geometry, representation theory, and the theory of a new class of quantum...

Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using...

We bound the time it takes for a group of birds to reach steady state in a standard flocking model. We prove that (i) within single exponential time fragmentation ceases and each bird settles on a fixed flying direction; (ii) the flocking network...

A local graph partitioning algorithm finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph $G$, starting from a specified vertex. For the algorithm to be local, its complexity must be...

We prove that NP is different from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k=(1 - e)log(n) players, where e>0 is any constant. Prior to our work, the problem was open even...

The local ratio framework introduced by Bar Yehuda and Evan in 1981 provides a unified framework for many approximation algorithms. Recently, the local ratio technique has been used to provide efficient approximation algorithms for a number of...

A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. I will show a general approach to deriving inapproximability results in the value oracle model, based on...