^December January – 2010 ^February

I will begin with presenting some problems from computational and combinatorial geometry. After that I will discuss problems of the following type: Is there a constant $f=f(k)$ such that any finite set of points in the plane can be colored with $k$ colors so that any halfplane that contains at least $f$ points, also contains a point from every color class? Similarly, one can reformulate the problem by changing halfplanes to a different family of regions. For halfplanes, Pach and G. Toth proved that $f(k)=O(k^2)$. This bound was later improved by Aloupis et al. to $f(k)=O(k)$. We will see that $f(k)=2k-1$, thus completely solving this question for the case of halfplanes. The above questions are related to problems of battery consumption in sensor networks and some other fields in computational geometry.

Over the past decades the evolutionary approach has been used in many fields of computer science research. Lately, with the growth of computation power, Genetic Programming (GP) has been showing much promise. We present an attempt to apply the tree based GP approach to zero-sum deterministic full knowledge board games, using Lose Checkers as a test-case. Our system implements strongly typed GP trees, explicitly defined introns and multi-tree individuals. We use the GP trees to evaluate possible future game states. Used together with traditional search techniques the results show much promise and imply that tree based GP may be useful in finding good players for other similar games.

Digitization of health care data is creating an opportunity for a new way of studying diseases and improving medical care. Using the vast amount of patient data collected daily at hospitals can assist us in circumventing the inherent faults of current medical research of studying phenomenon using various imperfect models, as experimenting on humans is unethical and illegal. The majority of information is stored in free text written by doctors. Using that data requires adapted Natural Language Processing methods combined with domain specific knowledge. Here I will present one project that originated from challenges in Medical Hebrew Processing: In most professional domains of languages with non-Latin alphabet, proper names, named entities and adjectives are transliterated from English. We show that recognizing these words as well as the original word is important for term recognition. We developed a method for identifying said words combining unsupervised classifiers and a lexicon. The lexicon based approach produced F-Measures of 87%-92% across domains, the combined approach produced F-Measures of 93%-94% respectively. Using this classifier to improve term matching we obtained 77% more matches with precision of 92%.