קולוקוויום וסמינרים

כדי להצטרף לרשימת תפוצה של קולוקוויום מדעי המחשב, אנא בקר בדף מנויים של הרשימה.

קולוקוויום וסמינרים בקרוב

  • On the Growth Constants of Polyominoes and Polycubes

    דובר:
    מירא שלח, הרצאה סמינריונית לדוקטורט
    תאריך:
    יום ראשון, 7.9.2014, 14:30
    מקום:
    טאוב 401
    מנחה:
    Prof. G. Barequet

    Lattice Animals, which can be defined as connected subgraphs of the dual graph of a given lattice, are well-known combinatorial objects, studied both in pure and recreational mathematics, and in various other fields, such as statistical physics and computational geometry. Of particular interest are lattice animals on the standard rectangular lattice (called polyominoes in the two dimensional case and polycubes for higher dimensions). Enumeration of lattice animals, as well as computing their asymptotic growth rate, are popular problems in discrete geometry, challenging mathematicians, computer scientists, and theoretical physicists alike. These are difficult combinatorial problems; even for the relatively simple case of the two-dimensional rectangular lattice not much is known, and much less is known in higher dimensions. The exact value of the growth rate limit of polyominoes (also known as Klarner’s constant) is the major open problem in the field. In this research, we investigate two types of lattice animals: 1. Polyominoes on Twisted Cylinders: We study this type of polyominoes to obtain improved lower bounds on the growth constant of polyominoes in the plane (Klarner's constant). We prove for the first time, that the growth rate of polyominoes in the plane is bounded from below by 4.00, breaking this mythical barrier. 2. Proper Polycubes: A d-dimensional polycube of size n is a connected set of n cubes in d dimensions, where connectivity is through (d-1)-dimensional faces. A polycube is said to be proper in d dimensions if the convex hull of the centers of its cubes is d-dimensional. In this work we develop a general framework and an automatic tool for computing formulae enumerating polycubes of size n which are proper in n-k dimensions, for a fixed value of k. (Such formulae are central in the literature of statistical physics.) We reaffirm the already-proven formulae for k =1,2,3, and aim to provide the first proof for k=4.

  • Massively parallel query processing of large tree and graph structured databases

    דובר:
    לילה שניידרמן, הרצאה סמינריונית לדוקטורט
    תאריך:
    יום רביעי, 10.9.2014, 10:00
    מקום:
    טאוב 601
    מנחה:
    Prof. O. Shmueli

    In light of the rapidly increasing amount of data and demand for fast query processing, increasing the efficiency of database operations continues to be a challenging and important task. XML is based on a tree-structured data model. Naturally, the most popular XML querying language (XPath) uses patterns of selection predicates on multiple hierarchically structured elements. These patterns are often abstracted by twig patterns. Finding all occurrences of such a (XML query) twig pattern in an XML document is a core operation for XML query processing. I present the Parallel Path Stack algorithm (PPS) and the Parallel Twig Stack algorithm (PTS). PPS and PTS are novel and efficient algorithms for matching (i.e., finding) XML query twig patterns over a parallel multi-threaded computing platform. PPS and PTS are based on the PathStack and TwigStack algorithms. These algorithms employ a sophisticated search technique for limiting the processing to specific subtrees. Another, recently popular, approach is to leverage the power of parallel hardware platforms. With the introduction of general purpose GPU (Graphics Processing Unit) computing, massively parallel hardware has become available as commodity hardware. I present a new algorithm, GPU-Twig, for matching twig patterns in large XML documents, using a GPU. The algorithm is based on parallel matching in a bottom-up fashion, followed by a consolidation phase. Fast query processing is important also in the Graph Databases field. I present, GGQ, algorithm that finds matches between TPQs (Tree Pattern Queries), and graph databases using the GPU platform. Its principle of operation is very different than that of GPU-Twig; it operates by relying on thread identifiers (IDs) to coordinate automated massive computing task distribution. It also addresses scale-up issues.

  • Observing the Observers: Social Context Analysis Using Computer Vision

    דובר:
    מאיר כהן, הרצאה סמינריונית לדוקטורט
    תאריך:
    יום רביעי, 10.9.2014, 12:00
    מקום:
    טאוב 601
    מנחה:
    Prof. E. Rivlin

    It is quite common that multiple human observers attend to a single point of interest. Mutual awareness activity (MAWA) refers to the dynamic of this social phenomena. A peak of a MAWA is known as a mutual awareness event (MAWE) and can be interpreted as a "buzz" event, which draws the attention of many observers. A preferred way to monitor those social phenomenon is with a camera that captures the human observers while they observe the activity in the scene. Our work studies the underlying geometric constraints of MAWEs (joint work with Amit Adam) and the related dynamics of MAWAs. Those constraints are reformulated in terms of image measurements, which are collected using existing face detection and head pose estimation algorithms. Those constraints are then used in a method that (1) detects how many such points of interest exist if any, (2) determines where each point is located, (3) identifies which observer attends to what, (4) reports where and when each observer was while attending, and (5) tracks the above quantities over a long time in an on-line manner. The suggested method is unsupervised and can deal with the general case of an uncalibrated camera in a general environment and an unconstrained activity in the scene. This is in contrast to other work on similar problems that inherently assume a known environment or a calibrated camera or a restricted occurrence in the scene. In addition, the current work attaches a social semantics to the detected MAWA. A deeper social interpretation is suggested by exploiting and analyzing the spatiotemporal correlations between the MAWA and the activity in the scene, i.e. the dynamics of the events which occur in the visual field of view of the observers. The statistics of those social interpretation are aggregated over a long time yielding social characteristics of an individual observer, the entire group, and of the activity in the scene. The method was tested on about 75 images from various scenes. In addition, the method was tested on videos of interesting activities, including: a single moving human observer that fixates on a single static interest point, a panel of several participants, and a classroom with many observers. The method robustly detected MAWEs and MAWAs, estimated their related attributes, and linked them with various social interpretations.

  • Parameterized Automata Constructions and Their Applications

    דובר:
    רן בן-בשט, הרצאה סמינריונית למגיסטר
    תאריך:
    יום שני, 22.9.2014, 15:30
    מקום:
    טאוב 701
    מנחה:
    Prof. Hadas Schachnai

    Parameterization is a useful tool for handling NP-hard problems in the real world. It aims to reduce the running times of algorithms for such problems, by confining the combinatorial explosion to some parameter k. As this parameter is often significantly smaller than the input size, it allows to develop practical algorithms for non-trivial classes of instances for these problems. In this talk we present a novel framework for developing parameterized algorithms, using constructions of automata for the corresponding languages. Our automata-based framework gives a different view of the parameterized versions of several classic problems, including Traveling Salesman and 3D-Matching. We show that many of the previously used techniques for solving these problems imply automata constructions for some implicitly related regular languages. We use automata tools also to infer lower bounds for these techniques. Finally, we note that our framework allows clean and simple design of algorithms for a family of problems, where a design of a single automaton for a specific problem yields deterministic, randomized and approximate witness counting algorithms for the problem.