^December January – 2004

In preparation for reading Okounkov's paper, "Random matrices and random permutations", which links the asymptotics of the longest increasing subsequence of a random permutation, to that of the largest eigenvalue of a random Hermitian matrix, we considersome results from representation theory of the symmetric group which are needed later on. the exposition will be self contained and will not rely on the previous lectures.

Databases often contain incomplete information. This is especially common when the database is formed by integrating information from heterogeneous sources or in the context of data extracted from the Web. In such situations, there may not be enough information to completely answer a query. Hence, it is of interest to find maximal answers for a given query. In this talk I will discuss semantics for incomplete query answers, and I will focus on the following topics:

(1) Semantically-Related Nodes: Given an XML document, we consider the problem of automatically determining when nodes are semantically related. I will present one method, called interconnection, that can be used to solve this problem. I will discuss how interconnection can be used even when the data being queried is incomplete.

(2) Semantic Search Engine: Building on the idea of interconnection, we developed and implemented XSEarch, a semantic search engine for XML. Using XSEarch one can efficiently find maximal subtrees of XML documents that answer a given search query and also contain semantically related nodes.

(3) Hereditary, Connected-Hereditary and Rooted-Hereditary Graph Properties: I will briefly survey other semantics for dealing with incomplete information (e.g., full disjunctions). These semantics for maximal query answers differ significantly one from another. Nonetheless, it has been shown that each of these semantics is polynomially-solvable, i.e., it is possible to generate all maximal solutions under each of these semantics in polynomial time in the size of the input and output. I will show that the above semantics can be couched as computing maximal solutions for hereditary, connected-hereditary or rooted-hereditary graph properties, and that this is the underlying reason why the semantics are polynomially-solvable. I will also present general algorithms that generate all maximal solutions for such graph properties in polynomial time in the size of the input and output. Our results include and improve upon previous results in databases, in particular, and in graph theory, in general.

The intersection graph of a family $F$ of $n$ sets is a graph on $n$ vertices which correspond to the sets. We connect two vertices by an edge iff the corresponding sets intersect. We show that if $F$ is a family of $n$ semi-algebraic sets, then the intersection graph of $F$ contains either a complete bipartite subgraph or an empty bipartite subgraph on $cn$ vertices, where $c$ is an absolute constant which depends only on the complexity of the semi-algebraic sets. For example, given a collection of $n$ balls in $R^3$, one can always find two disjoint sets of balls $S_1$ and $S_2$ ($|S_1|,|S_2|>cn$) such that either every ball from $S_1$ intersects every ball from $S_2$ or no ball from $S_1$ intersects any ball from $S_2$. We also show that the intersection graph of semi-algebraic sets has either a clique or an independent set of size $n^\epsilon$ where $\epsilon$ depends only on the complexity of the semi-algebraic sets. This shows the Erdos-Hajnal property for that rather big class of graphs.

Joint work with Noga Alon, Janos Pach, and Rados Radoicic

The intersection graph of a family $F$ of $n$ sets is a graph on $n$ vertices which correspond to the sets. We connect two vertices by an edge iff the corresponding sets intersect. We show that if $F$ is a family of $n$ semi-algebraic sets, then the intersection graph of $F$ contains either a complete bipartite subgraph or an empty bipartite subgraph on $cn$ vertices, where $c$ is an absolute constant which depends only on the complexity of the semi-algebraic sets. For example, given a collection of $n$ balls in $R^3$, one can always find two disjoint sets of balls $S_1$ and $S_2$ ($|S_1|,|S_2|>cn$) $such that either every ball from $S_1$ intersects every ball from $S_2$ or no ball from $S_1$ intersects any ball from $S_2$. We also show that the intersection graph of semi-algebraic sets has either a clique or an independent set of size $n^\epsilon$ where $\epsilon$ depends only on the complexity of the semi-algebraic sets. This shows the Erdos-Hajnal property for that rather big class of graphs.

Joint work with Noga Alon, Janos Pach, and Rados Radoicic.

Cutting planes procedures are techniques for solving, or approximating the solutions to, integer linear programs. As such, they are used in practice to attack NP-hard optimization problems. They can also be used to prove the unsatisfiability of CNF formulas. The most common examples of such procedures, those defined by Gomory and Chvatal and by Lovasz and Schrijver, are applied in rounds. For a given input, the number of rounds needed to solve the integer linear program, or to prove that the CNF is unsatisfiable, is called the rank of the input.

We present a new technique for proving rank lower bounds for these procedures when viewed as proof systems for unsatisfiability. We use this technique to prove near-optimal rank bounds for Gomory-Chvatal and Lovasz-Schrijver proofs of several prominent unsatisfiable CNF examples, including random kCNF formulas and the Tseitin graph formulas. It follows from these lower bounds that a linear number of rounds of these procedures when applied to relaxations of integer linear programs is not sufficient for reducing the integrality gap.

Joint work with: Josh Buresh-Oppenheim, Nicola Galesi, Avner Magen and Toni Pitassi

We will present the ideas behind the particle system approach to the $2\sqrt{N}$ asymptotics of the longest increasing subsequence. We will then present a generalization to the case of general distributions on the unit square due to Deuschel and Zeitouni. This is important for the applications. We will then provide ageometric interpretation of their result in terms of 2 dim Lorentzian geometry.

We will consider the problem of computing (almost) shortest paths in an unweighted undirected graph G=(V,E).

We will focus on a version of this problem in which a subset S of V is given as a part of the input, and the objective is to compute paths P(u,w) for all pairs (u,w) in SxV.

This is one of the most fundamental problems in the area of graph algorithms, and it has numerous practical and theoretical applications. We will present and outline the analysis of our recent near-optimal algorithm for this problem.