Seminars Sorted by Series

In the late nineties Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given $n$ numbers, do any $r$ of them add up to $0$? His lower bound of $\Omega(n^{\lceil r/2...

We will describe definitions and algorithmic results for the ``census problem''. Informally, in a census individual respondents give private information to a trusted (and trustworthy) party, who publishes a sanitized version of the data. There are...

Ordinary 3-by-3 tic-tac-toe is trivial; the 3-dimensional 4-by-4-by-4 version is interesting but very complicated (first player wins; solved by Patashnik; heavy computer use); and the 5-by-5-by-5 version is already unsolved (expected to be a draw)...

In this talk, I'll present a new inequality which, for an arbitrary boolean function, relates the influence of its variables to decision tree computation of the function. Combining this with another inequality due to Schramm and Steif, we deduce new...

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer...

I will discuss some (very) recent results showing how techniques from the theory of Gaussian Hilbert spaces can be used in order to solve a number of open problems regarding boolean functions with low influences. I will survey some of the background...

The goal of hardness amplification is to take a function f : {0,1}^n --> {0,1} that is mildly average-case hard (i.e., very "small" circuit fails to compute f on at least a 1/poly(n) fraction of inputs), and produce a new function f' that is very...

We prove a number of general theorems about CZK, the class of problems possessing computational zero-knowledge proofs. Our results are *unconditional*, in contrast to most previous works on CZK which rely on the assumption that one-way functions...

I will present recent joint work with O. Friedland and V. Milman, where we use simple probabilistic estimates on Bernoulli random variables, together with tools from convex geometric analysis, to arrive at some new results. The first result has to...

The problem of average-case learning for decision trees is as follows: a decision tree T (over Boolean features x1,...,xn) is chosen at random from some natural distribution over decision trees. The learner is given access to uniform random examples...

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a graph G=(V,E) and a set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k). The objective is to decide if all the pairs can be...

We present new PCPs for NP-complete languages. The PCPs are only n poly log n bits long, when proving satisfiability of formulae of length n. However, the probabilistic verifier needs to query poly log n bits of the proof to verify it. In contrast...

A graph property P is said to be uniformly-testable if there is a property-tester for P that receives the error parameter \epsilon as part of the input, and whose query complexity is a function of \epsilon only. P is said to be non-uniformly...

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d>=2 and 0

The goal of Statistical Learning Theory is to construct and understand algorithms that are able to generalize from a given training data set. Statistical learning algorithms are wildly popular now due to their excellent performance on many types of...

We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we consider the possibility of computing instances of these primitives by NC0 circuits, in...

Counting homomorphisms between graphs has a surprising number of applications. Many models in statistical mechanics and many questions in extremal graph theory can be phrased in these terms. We introduce a matrix, which we call the connection matrix...

Given a polytope P with a real-valued objective function f on its vertices, we consider the problem of finding a minima of f. Arguably the simplest randomized approach is the simplex algorithm RANDOMEDGE. Sitting at a vertex of P, RANDOMEDGE chooses...

In this talk we will consider settings where multiple agents each pursue their own selfish interests, each represented by his own objective function. Traditional algorithms design assumes that the problem is described by a single objective function...

The well-known Max Cut problem asks for the largest bipartite subgraph of a graph G. This problem has been the subject of extensive research, both from the algorithmic perspective in computer science and the extremal perspective in combinatorics...

Given a hypergraph H=(V,E), its conflict-free chromatic number (CF-chromatic number) is the minimum number of colors needed to color the vertex set V such that, for every hyperedge S, there is at least one element v \in S whose color is unique (in S...

A ranking of n web pages is to be chosen from outputs of k search engines. How do we choose one ranking minimizing the "disagreement" with the k rankings? A clustering of n genes is to be chosen from outputs of k clustering algorithms. How do we...

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and...

We study the multicommodity buy-at-bulk network design problem where the goal is to buy capacity on edges of a network so as to enable the demands between a given set of source-sink pairs to be routed - the objective is to minimize the cost of such...

For an undirected graph G=(V,E), let G^n denote the graph whose vertex set is V^n in which two distinct vertices (u_1, u_2, ... ,u_n) and (v_1, v_2, ... ,v_n) are adjacent iff for all i between 1 and n, u_i and v_i are either equal or adjacent. The...

There has been substantial work in learning theory and game theory on adaptive "no-regret" algorithms for problems of repeated decision-making. For example, one could use such an algorithm to choose a path to drive to work each day so that no matter...

Many algorithms can intuitively be classified into one of a few basic paradigms of algorithms, such as greedy algorithms, dynamic programming, LP rounding, local search, etc. It is natural to ask which problems can be solved using these paradigms...

Given a set of variables, and a set of local constraints over them (e.g. a 3CNF formula) define the "satisfiability-gap" of the system as the smallest fraction of unsatisfiable constraints. We will describe a new proof for the PCP theorem of [AS...

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the...

I will talk about a family of graphs which originally arose in cryptography, in studying the difficulty of the discrete logarithm problem on elliptic curves. These graphs can be shown to be expanders, assuming the generalized Riemann hypothesis (GRH...

Szemeredi's regularity lemma asserts, roughly speaking, that any large dense graph can be approximated to any specified accuracy by a much simpler "finite complexity" object; it has had many applications in graph theory, combinatorial number theory...

We construct an extractor that can extract from a constant number of independent sources of length $n$, each of which have min-entropy $n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our constructions are different from recent extractor...

Earthmover metrics are popular similarity measures in computer vision, and they are also used in the design of approximation algorithms for classification problems. Motivated by the existing nearest neighbor search databases for L_1 metrics, it was...

I will discuss the following two results. I will assume no prior knowledge of quantum information or the PCP theorem. 1) The membership of $x$ in $SAT$ (for $x$ of length $n$) can be proved by a logarithmic-size quantum state $\Psi$, together with a...

Unique games were introduced by Uriel Feige and Laszlo Lovasz. We are given a graph G, a set of labels [k] = {1,...,k}, and permutations pi_{uv} on the set [k] (for all edges (u,v)). Our goal is to find an assignment of labels to variables x(u) (for...

A code is said to be locally testable if an algorithm can distinguish between a codeword and a vector being essentially far from the code using a number of queries that is independent of the code's length. The question of characterizing codes that...

We prove a general result bridging the fields of Secure Protocols and Game Theory. We show that ANY mediated game with incomplete information can be perfectly simulated by the players alone, essentially by means of an extensive-form game in which...

Biological networks have so many possible states that exhaustive sampling is impossible. Successful analysis thus depends on simplifying hypotheses, but experiments on many systems hint that complicated, higher order interactions among large groups...

Ramanujan complexes of type ${\tilde A}_n$ have been constructed by Lubotzky, Samuels and Vishne. In this talk I would like to propose a definition of Ramanujan complexes associated with buildings of any affine type. This involves defining...

Internal conflict is considered to be a fundamental psychological phenomenon, and many behaviors in both humans and animals have been attributed to it. However, from a biological standpoint, internal conflict is counterintuitive, in that it appears...

Perhaps the most appealing conjectures in asymptotic convex geometry are (i) slicing (or isotropic constant) and (ii) variance. Together, they imply that for a random point X from an isotropic convex body in \R^n, the variance of |X|^2 is O(n). We...

We present a novel tree representation for the hard-core lattice gas model (weighted independent sets) on a general graph. We use this representation to show that for any graph of maximum degree D, the Gibbs measure is unique (the influence of any...

Counting connected components and Betti numbers was a known technique in algebraic complexity theory in the late 1970's and early 1980's. Speculation arose as to whether such methods could attack lower bounds in Boolean complexity theory (e.g., P vs...

In this talk I will prove the following counterpoint to a result by Kashin and Szarek (cf. Theorem 1, C. R. Acad. Sci. Paris, Ser. I, 1336 (2003) 931-936)): There exists a map \phi from infinite-dimensional euclidean space into the space of...