^October November – 2007 ^December

Motivated by battery consumption in sensor networks we study two hypergraph coloring problems: 1. For a hypergraph $H=(V,E)$ (The elements of E are subsets of V) define the parameter $p=p(k)$ to be the minimum number p for which there exists a coloring of V with k colors such that every hyperedge in E with cardinality at least p(k) contains elements from all color classes. If such a coloring does not exist then we say that $p(k) = \infty$. We show that $p(k) < 4k$ when the vertices of H is a finite set P of points in $R^2$ and E consists of all subsets of P that can be obtained by intersecting P with some closed half-plane.

This improves a previous bound of Pach and Toth of $O(k^2)$

We also study the following parameter: 2. For a hypergraph $H = (V,E)$, Let $c = c(k)$ denote the minimum number c such that there exists a coloring of H with c colors such that every hyperedge with cardinality at least k contains elements from some k distinct colors. We show for example that for some geometrically defined hypergraphs, $c(k) = O(k)$ (When H is the hypergraph defined by intersecting a set of points in $R^3$ with all half spaces, the statement $c(2) = 4$ is equivalent to the Four-Color Theorem)

Joint work with G. Aloupis, J. Cardinal, S Collette and S. langerman from Universite Libre de Bruxelles (ULB)

Effective resizing of images should not only use geometric constraints, but consider the image content as well. We present a simple image operator called seam carving that supports content-aware image resizing for both reduction and expansion. A seam is an optimal 8-connected path of pixels on a single image from top to bottom, or left to right, where optimality is defined by an image energy function. By repeatedly carving out or inserting seams in one direction we can change the aspect ratio of an image. By applying these operators in both directions we can retarget the image to a new size. The selection and order of seams protect the content of the image, as defined by the energy function. Seam carving can also be used for image content enhancement and object removal. We support various visual saliency measures for defining the energy of an image, and can also include user input to guide the process. By storing the order of seams in an image we create multi-size images, that are able to continuously change in real time to fit a given size.

Text remains the main medium to convey information and knowledge. Machine-readable text has become plentiful and accessible through search engines. Many applications are concerned with transforming text from one to another. The field that studies such transformation is called text to text generation (T2T). T2T is a sub-field of natural language generation (NLG), and stands in contrast with data to text (D2T) generation (where the input data is any non-textual representation).

In T2T, textual units (sentences, clauses, phrases) are extracted from one context and recombined into a new text. As in NLG in general, one can split the overall task of generation into several steps:

• Content selection
• Content organization
• Realization: the rendering of the selected content into fluent language.

In T2T, "content" is encoded as textual units - generally called "SCU" (Shared Content Unit). The input to a T2T system includes a collection of texts that are related in topic, for example a collection of news reports describing the same event (from different sources or published at different times). Content selection and organization in D2T applications is generally related to knowledge representation and inferencing. In the case of T2T, it is related to Information Extraction, which includes named entity recognition, coreference resolution, entity identification, relation identification and scenario identification.

Realization is the linguistic component of generation, and is organized around the following steps:

• Lexicalization (selection of the words)
• Aggregation
• Referring expression generation
• Rhetorical structuring and ordering
• Centering and salience
• Syntactic realization (ordering of the words, morphological inflection)

In the lecture, I will review sample T2T applications and the corresponding methods. I will focus on the type of knowledge required to perform T2T and how it can be acquired. I will end with a review of open issues and possible topics for further research.

For a function g from natural numbers to natural numbers, a g-regressive coloring of pairs of natural numbers is a coloring C satisfying $C(m,n) \le g(\min{m,n})$ for all $m,n$.

The g-regressive Ramsey number of k is the least N so that for every g-regressive coloring C there exists a subset H of of size at least k which is min-homogeneous for C, namely, the color $C(m,n)$ of a pair ${m,n}$ of H depends only on $\min(m,n)$.

We compute a sharp threshold on g at which g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian. We prove:

Suppose g is nondecreasing and unbounded. Then the g-regressive Ramsey number is bounded by some primitive recursive function in k if and only if for every $t>0$ there is some $M(t)$ so that for all $n \ge M(t)$, $g(n) < n^{1/t}$ and $M(t)$ is primitive recursive in t.

We also give an extremely large lower bound on the identity-regressive Ramsey number of k=82. Joint work with Menachem Kojman, Gyesik Lee and Andreas Weiermann.

This talk is about the application of Boolean SAT solvers to the problem of determining program termination. Proving termination is all about the search for suitable ranking functions. The key idea in this work is to encode the search for particular forms of ranking functions to Boolean statements which are satisfiable if and only if such ranking functions exist. In this way, proving termination can be performed using a state-of-the-art Boolean satisfaction solver.

We have applied this approach to several variants of the so-called LPO termination problem which comes up in the context of term rewrite systems. Experimental results are unequivocal, indicating orders of magnitude speedups in comparison with previous implementations for LPO termination. Our results have had a direct impact on the design of several major termination analyzers for term rewrite systems. Moreover, there are an increasing number of new results illustrating additional applications of SAT to proving termination.

A function is Turing computable if it can be specified by a Turing machine. Turing's definition [1936] of a function, computable by a Turing machine, was followed in his dissertation [1939], in which he defined the notion of a set $A$ being computable relative to a set $B$. We then say $A$ is Turing reducible to $B$ ($A\leq_T B$). We identify a degree as an equivalence class of sets of natural numbers, each reducible to the other

The least degree is the set of all recursive subsets of $\omega$, denoted $\deg{0}$. A degree $\deg{b}$ is minimal if $\deg{b}>\deg{0}$ and there is no $\deg{c}$ such that $\deg{0}<\deg{c}<\deg{b}$. That is, it is minimal in the ordering of degrees. I will present Spector's result [1956]: There is a minimal degree. It follows that the ordering $\leq$ on $\D$ (the structure of the degrees) is not dense. This result proved to be useful in many embedability results as well as other results concerning the structure of $\D$.

The parallel repetition theorem, proven by Raz in 1995, is a fundamental result that in addition to its philosophical appeal, plays a key role in complexity theory. The theorem studies the behavior of success probabilities of two prover games, when many copies of such a game are played in parallel. It shows that the success probability decreases exponentially in the number of repetitions, but the parameters given by the theorem do not seem tight. It is natural to ask what are the best parameters for which the theorem holds, and improving them would have complexity theoretic implications.

This talk describes an attempt to improve the parameters in a very special case of the parallel repetition theorem. Our attempt had only limited success, but it turns out that the reason we got stuck was that the following seemingly hard question from the geometry of "foams" was hidden in the special case that we were trying to solve: What is the least surface area of a cell that tiles $R^d$ by the lattice $Z^d$? Very little about this foam problem is known. It is interesting to see such a geometric question encoded inside the problem of parallel repetition in two prover games.