Ettekande kiled. [pdf]

*Abstract:*
Many organisations often gather sensitive data from individuals. Due
to legal restrictions on how the data can be processed, it is hard or
even impossible to learn global properties or trends from the
collected data. Moreover, the privacy of the participants is not
guaranteed when the administrative measures fail. Therefore, we apply
secure multi-party computation methods to make data aggregation
privacy-preserving and secure. We *have designed and implemented* a
programming framework which allows us to quickly prototype and
evaluate privacy-preserving aggregation and data mining
algorithms.

Ettekande kiled. [pdf]

*Abstract:*
In prokaryotes (organisms with no nuclei in cells) there is about the
same number of proteins and genes. Alternative splicing is a gene
regulation phenomenon which results in more than one protein per gene
in eukaryotes (organisms with nuclei). This offers higher efficiency
because information can be stored much more economically. As
alternative splicing favours the emergence of new proteins also, it is
hypothesized to be one of the most powerful tools in the evolution of
eukaryotic organisms.

We have studied tissue-specific alternative splicing using the EST-data (Expressed Sequence Tags) aiming to discover proteins which are produced only (or mostly) in some specific tissue. I am going to describe the biological system of splicing in mathematical terms as well as present the tools we have developed to achieve our goals. (joint work with Jaak Vilo)

Ettekande kiled. [pdf]

*Abstract:*
The simplest way to measure the similarity between two strings is to
use edit distance, also known as the Levenshtein distance. The
conventional edit distance considers only a limited number of
transformations that all have the same weight. In this work we propose
an extended edit distance algorithm that works with a larger set of
transformations that can have different weights. In addition, we
extend the edit distance to work with the multibyte encodings like
UTF8. To achieve greater efficiency, our implementation of the
extended edit distance algorithm uses tries. Finally, we consider a
version of the edit distance algorithm that learns the weights of
transformations from the weights of existing transformations.

Ettekande kiled. [pdf]

*Abstract:*
In a dependency graph, nodes correspond to operations. Edges between
nodes connect producers of data to their consumers. A dependency graph
makes explicit, which data is used where; this information is not so
clearly presented in other types of program representation, such as
abstract syntax trees or control flow graphs. Certain forms of program
dependency graphs can also be given semantics, although it is in
general more tricky than for more orthodox representations.

Program (or protocol) dependency graphs make certain program transformations convenient, in particular those that correspond to definitions of cryptographic primitives. These transformations do not observably change the semantics of a protocol, but may change it syntactically in such a way that its security becomes more obvious. In our talk, we present a prototype protocol analyser, the transformations that we have implemented, and the insights gained.

Ettekande kiled. [pdf]

*Abstract:*
There are two main tasks in cryptography. One can either try to
discover or enhance cryptographic primitives such as encryption or
alternatively try to combine existing primitives in order to meet some
practical design criterion. Although a construction of complex
protocols is clearly an engineering task, security analysis of such
protocols often resembles to witchcraft; sometimes the results are
clearly wrong or too vague. Hence, many famous cryptographers have
tried to come up with rigorous methods. Nevertheless, we still do not
have formal machine verifiable methodology that is common in other
engineering disciplines.

Usually, the security definitions are specified as a game between an adversary and a challenger, where the challenger conducts the game. The latter complicates the security proofs, as one must give a reduction - construct a new adversary from the old one. However, there is an alternative - one can specify the security definitions in adversary-centric way [BR06]. Then the security proof contains no reductions. Instead one performs a set of clearly specified code transformations. As a result security proofs for many protocols can be formally constructed and verified. Moreover, the analysis is precise and sharp opposed to polynomial security model.

[BR02] Bellare and Rogaway, Code-Based Game-Playing Proofs and the Security of Triple Encryption, Eurocrypt 2006.

Ettekande kiled. [pdf]

*Abstract:*
The primary task of data-mining is to develop models about aggregated
data, for example about the habits of Internet users, about loyal
customers, etc. The main question of privacy-preserving data-mining
(PPDM) is, can we develop accurate models without access to precise
information in individual data records? The latter question has proven
to be difficult to solve. One can divide the techniques of PPDM in two
large groups: the randomization approach (related to the well-known
statistical Randomized Response Technique), and the cryptographic
approach.

In this tutorial, we will give an overview of the cryptographic approach that has many benefits but also several drawbacks. A major sociological problem with the cryptographic approach is that cryptographic and data mining communities are currently distinctly separated. On the one hand, without a special cryptographic training one is tended to propose protocols for PPDM that are not as secure or at least not as efficient as the up-to-date cryptographic protocols. On the other hand, without special training in data mining, one can often try to solve the wrong problem. In particular, the security definitions for different PPDM tasks are application-dependent and have their roots in data mining.

A major technical problem is that data mining tasks routinely deal with huge amounts of data. Mining this data, even without any privacy concerns, is non-trivial. Cryptography, even on much smaller amounts of data, is also non-trivial. Mixing the two usually results in PPDM solutions that are very complicated, and --- most importantly --- unlikely to be practical. Given this, it is important, in a collaboration between two communities, to come up with security definitions for PPDM that potentially have efficient cryptographic implementations.

Ettekande kiled. [pdf]

*Abstract:*
Binary search for one-dimensional sorted array is well-known. In the
seminar, we try to design efficient algorithms for searching
from multi-dimensional sorted arrays.

*Viited:*

- Bird, R.: Improving Saddleback Search: A Lesson in Algorithm Design. In Uustalu, T. (ed.): Proceedings of 8th International Conference in Mathematics in Program Construction. Lecture Notes in Computer Science 4014 (2006) 82-89.
- Dijkstra, E.W.: The Saddleback Search. Note EWD-934. (1985)

Ettekande kiled. [pdf]

*Abstract:*
New developments and decreasing costs of electronic appliances enable
the realization of pervasive systems in our daily environment. In this
work, I focus on eHome systems. The price of individual development
and adaption of the software making up these systems is one of the
major problems preventing their large-scale adoption. In this talk, I
introduce an approach built upon functionality composition for
automatic service configuration in different environments. The
repetitive development process is transformed to a single development
process followed by a repetitive configuration process. This
configuration process is supported by our tool suite, the
eHomeConfigurator. The result is a deployable configuration graph,
capable of describing dependencies and contexts of components in the
eHome field. The tool suite is used to configure and deploy various
services on different home environments. Compared to the classical
development process, the effort for setting up eHome systems is
reduced significantly. For demonstration purposes, I will also bring
a small eHome-model made from Lego to show this configuration process
and various eHome services. The demonstration will provide a platform
to discuss eHome systems and future extensions (i.e. voice control) in
general.

Ettekande kiled. [pdf]

*Abstract:*
T-algebra is a project for creating interactive problem solving
environment for basic school expression manipulation exercises:
calculation of the values of numerical expressions; operations with
fractions; solving of linear equations, inequalities and linear
equation systems; operations with monomials and polynomials. The
presentation demonstrates and motivates solution step interface and
error diagnostics developed in T-algebra.

Ettekande kiled. [pdf]

*Abstract:*
Ettekandes kirjeldatakse staatilise tüübikontrolli raamistikku
magasinipõhiste madaltaseme programmeerimiskeelte jaoks, näit. Forth,
PostScript, jt. Magasinipõhist arhitektuuri leiame mitmetes
populaarsetes virtuaalmasinates - CLR, JVM, samuti riistvaras.
Magasinipõhise virtuaalmasina kood on samuti näide magasinkeelest,
mida on tarvis analüüsida. Suurel osal juhtudest on magasinkeel ise
tüübivaba - tüüpidega seotud kitsendused on osa koodistandardist ja
programmeerimiskultuurist, mitte keelest.
Tuuakse sisse n.-ö. "väline" analüüsivahend, mis lubab teatud
tingimustel leida koodist kohti, kus magasini kasutamine äratab
kahtlust (aga ei pruugi sellegipoolest vale olla).
Prototüüpanalüsaatori tuum on kirjutatud Javas.

Ettekande kiled. [ppt]

*Abstract:*
We give a uniform type-systematic account of a number of optimizations
and the underlying analyses for a bytecode-like stack-based low-level
language, including analysis algorithms and soundness
proofs. Specifically, we treat dead store instructions, load-pop
pairs, duplicating load instructions, store-load pairs. The load-pop
pairs and store-load pairs elimination optimizations are built on top
of bidirectional analyses, facilitating correct elimination of
instruction pairs spanning across basic block boundaries. As a result,
no assumptions are needed about input code (it need not be the
compiled form of a high-level source program, the stack need not be
empty at basic block boundaries and not even need it be checked for
safety before the analysis). The strongest analysis algorithms and
soundness proofs are simple and uniform.
(Joint work with Tarmo Uustalu.)

Ettekande kiled. [pdf]

*Abstract:*
Approximate matching is an important problem of information retrieval
and bioinformatics applications. We have implemented an approximate
search algorithm for matching a subset of regular expressions. The
basic principles of the algorithm have been previously described in
Navarro's article "NR-grep: a Fast and Flexible Pattern Matching
Tool". The algorithm uses Glushkov method for generating the
non-deterministic automaton, and a bit-parallel method for matching
this automaton with a small number of allowed mismatches, insertions,
and deletions. We have also introduced the method for including
error-free regions into the expressions. The implementation of the
algorithm in C++ has been compared to other libraries for exact
regular expression matching, where the method is approximately
comparable with existing programs. For approximate matching we found
only one comparable tool. Our implementation beats that by boosting
the speed about 100-fold. The method is included in our Sally text
algorithm library that is currently under development.
(Joint work with Jaak Vilo.)

Ettekande kiled. [pdf]

*Abstract:*
We consider three types of bottom-up tree transducers of increasing
levels of generality: relabelling (branching-preserving), rebranching
(layering-preserving) and relayering (general) tree transducers. For
each type, we show the equivalence of three categories, in fact,
arrows: the transducers of this type (modulo bisimilarity), the
(co/bi)-Kleisli category of a comonad/distributive law, and a subclass
of tree functions. (Joint work with Ichiro Hasuo and Bart Jacobs.)

Ettekande kiled. [pdf]

*Abstract:*
In this talk we are dealing with PageRank, the well known Web-page
ranking algorithm introduced by Google. We start with giving a short
survey on different PageRank problem interpretations and ways of
efficient parallel solution of the problem. We investigate more
closely the representation of the problem as a system of sparse linear
equations, possible methods for efficient solution of the system and
prospective implementation in our own parallel black-box linear system
solver DOUG (Domain Decomposition on Unstructured Grids,
http://dougdevel.org).

Ettekande kiled. [pdf]

*Abstract:*
We have been working on a static analyzer for many years, and while it
is almost ready for a decent tool-demo, we are also thinking about
presenting some of the underlying ideas. In this talk, I will explore
ways to generalize the methods used in our analyzer, and maybe solicit
some feedback on how to make these ideas sufficiently interesting to
be written down more formally. One idea is to exploit the detailed
information that the analyzer already computes for the data-race
analysis to check for other similar properties. Ideally, we would like
to develop a specification framework where such properties can be
expressed by the user. The key mechanism in achieving these goals is a
generic method of transforming a simple analysis specification into a
path-sensitive analysis. This will be the main focus of the talk.

Ettekande kiled. [pdf]

*Abstract:*
This paper describes a framework for mobile robot path planning in
dynamic environments where the environments are represented by grid
maps. The planning heuristics considered in the paper is to generate
the minimal set of paths so that all the possible path fragments of
two edges are covered. We show that the number of required paths is
linear in the dimensions of the grid (thus making application of the
approach realistic and scalable). The main contribution of the paper
is the description of all the minimal covers by means of an efficient
algorithm. We prove its correctness and conclude that there are
$2^{(m-1)(n-2)+(m-2)(n-1)}$ minimal path fragment covers in an
$m\times n$ grid.

Peeter Laud

Helger Lipmaa

Tarmo Uustalu

Varmo Vene

Viimane uuendus 22.01.2007