Ettekande slaidid. [pdf]

*Abstract:* We present a purely functional implementation of
two standard -- direct and inverse -- modes of the Automatic
Differentiation techniques, permitting to compute the derivatives of
expressions within a _numerical_ program exactly and inexpensively.
The direct method is based on the overloading of the aritmetic
operations to lazy infinite streams, which implement numerical
expressions together with _all_ their derivatives, and which realize a
closed differential algebra. The reverse method relies on a paradoxal
State Monad version in which the "time goes backwards", and the
"state" which model the adjoints (derivatives) of intermediate
expressions propagates from the future towards the past, exploiting
again the laziness of the used language, Haskell. [No previous
knowledge of Monads is assumed].

Ettekande slaidid. [pdf]

*Abstract:* While 'states' in Quantum Theory are abstract
vectors in Hilbert spaces, and observables are abstract operators, all
_concrete_ computations need implementable representations
thereof. Computer scientists introduce thus "quantum registers", play
with concrete matrices, etc., in order to be able to do standard
calculi thereupon. One undesirable consequence of such an approach is
that _too much_ information is attributed to 'quantum' entities, and
the computational model represents not only the system, but also its
concrete view. We attempt at implement almost directly the quantum
abstractions, keeping the bridge between computations and theoretical
physics as short as possible. State vectors are _functions_, operators
are higher-order functions, etc. Despite this, very high, level of
abstraction, we show how to perform some classic "quantum
computations", such as the Deutsch algorithm, or a qubit
teleporting. But our formalism is pretty general, applicable to other
systems than qubits; we sketch thus also some other application of the
presented framework, such as the construction of some concrete wave
functions, or the development of lazy perturbational schemes. The
talk assumes a _rudimentary_ knowledge of quantum mechanics.

*Abstract:* As a notion of uniformity, the definition of
natural transformation in category theory serves ordinary mathematics
well. The mathematics of program semantics, which uses higher order
constructions of mixed variance, seems to require something else.
Exactly what is still unknown. A few examples illustrate the troubles
and triumphs of various definitions.

- Plotkin's lambda definability paper,
- O'Hearn's full abstraction paper,
- current problems.

Ettekande slaidid. [pdf]

*Abstract:* Gene expression data clustering methods group
together similar genes. We have developed a method that avoids
calculations of all-against-all distances, yet identifies rapidly most
of the similar gene pairs. Using this method we have developed fast
approximate versions of single-, average-, and complete-linkage
hierarchical clustering. (Joint work with Jaak Vilo.)

Ettekande slaidid. [pdf]

*Abstract:* It is generally believed that a drawing of a graph
is clearly understandable and aesthetically pleasing, if the drawing
contains as few edge crossings as possible. A special case of general
drawing of a directed graph is the layered drawing where the vertices
of the graph are distributed between discrete layers so that all the
edges of the graph point to the same direction. The edge crossing
minimisation in such a drawing is an NP-hard combinatorial
optimisation problem. A close alternative to that - the extraction of
the maximum level planar subgraph is equally difficult. We attempt to
solve these problems using the Integer Linear Programming approach
(ILP). The ILP technique can be regarded as "a way between" imprecise
fast heuristic algorithms and exponential-time exact algorithms,
allowing to achieve close to optimal results in "acceptable time". We
explain the ILP approach in general and talk about the specifics of
solving the two aforementioned graph drawing problems by the ILP.

Ettekande slaidid. [pdf]

*Abstract:* Every cell possesses two independent copies of DNA,
one from the female parent and the other from the male. Modern
biotechnology is not yet capable of reading the sequence from a
particular one of those two helices, but produces a succession of
unordered pairs of values (eg {A,G},{G,G},{T,C},...) as genotyping
output. At a considerable computational expense, mathematical methods
can be exploited to reconstruct genes and actual sequences
(haplotypes) from such raw genotyping data, but for slightly longer
genome regions the degrees of freedom quickly become unmanagable for
statistical simulations. Knowing the individual haplotypes is often
essential for interpreting genetic variance and discovering genome
structure.

This talk aims at exhibiting this bioinformatics problem, explaining the underlying mathematical models and proposing a few ideas to tackle the computational issue.

Ettekande slaidid. [ps.gz]

*Kokkuvõte:* Universaalne komponeeritavus on krüptograafiliste
süsteemide turvadefinitsioonide omadus, mis lubab komponeeritud
süsteemide omaduste üle arutlemise taandada nende komponentsüsteemide
ideaalsete funktsionaalsuste üle arutlemisele; komponentsüsteemide
realisatsioonide iseärasusi pole tarvis arvesse
võtta. Ajatemplisüsteemid on krüptograafilised süsteemid, mis lubavad
osapooltel fikseerida bitijadade loomise (täpsemalt öeldes:
ajatembeldamise) järjekorra, vajamata selleks usaldatud
osapooli. Käesolevas ettekandes uurime erinevaid võimalusi
ajatemplisüsteemide turvalisuse universaalselt komponeeritavate
definitsioonide andmiseks ning arutleme, milliseid kompromisse
sealjuures teha tuleb.

Ettekande slaidid. [pdf]

*Kokkuvõte:* Ettekanne käsitleb otsinguid üle krüpteeritud
andmete. Üheks uudseimaks lahenduseks on Bloomi indeksi kasutamine,
idee enda pakkus välja E.-J. Goh artiklis [crypto eprint 2003/216].
Kahjuks pole artiklis toodud turvatõestus korrektne, seetõttu pakume
välja alternatiivse paremini struktueeritud lähenemise, mis võimaldab
täpselt määratleda kasutavatelt primitiividelt nõutud
turvaomadusi. Saavutatud tulemused on üldisemad, kattes kogu mäluta
andmestruktuuride klassi. Tuntumateks näideteks sellistest
andmestruktuuridest on nimistud ja prefikspuud. Lisaks vaatleme
võimalikke laiendusi nagu eristamatud päringud, ligikaudne otsing ja
päringute kontroll/piiramine.

H. Lipmaa, An oblivious transfer protocol with log-squared communication, draft paper. [crypto eprint]

Ettekande slaidid. [pdf]

*Abstract:* We propose a family of two-round $1$-out-of-$n$
computationally-private information retrieval protocols for elements
from $\mathbb{Z}_d$ that has the next properties: (a) In the
asymptotically optimal case, it has communication $\Theta(\log^2
n\cdot {k}+\log n\cdot \log d)$ bits, where ${k}$ is the security
parameter; (b) It can be based on an arbitrary IND-CPA secure
length-flexible public-key cryptosystem. In particular, the
sender-privacy of the new protocols can be based on the assumption
that the Decisional Composite Residuosity Problem is hard. The
proposed protocols can be transformed to two-round computationally
chooser-private and information-theoretically sender-private
$1$-out-of-$n$ oblivious-transfer protocols for elements from
$\mathbb{Z}_d$, with the same asymptotical communication, that is
secure assuming that the underlying cryptosystem is IND-CPA secure,
i.e., in the standard model.

Ettekande slaidid. [ps.gz]

*Abstract:* Transfinite semantics are semantics which observe
sequences of computation steps continuing beyond the initial
enumerable part of it. Transfinite semantics have been the subject of
interest mainly for functional languages (due to possible infinite
data structures whose components are computed in such an order which
does not lead to a completely evaluated term within the least
enumerable number of evaluation steps, having however an intuitively
clear value being able to be obtained using another order of reduction
or --- continuing the actual reduction sequence with transfinite
steps).

We are interested in transfinite semantics in the case of imperative languages. This means returning of the control from infinite loops and continuing the computations after that. The reason of studying such semantics is given by program slicing and its well-known "semantic anomaly" which arises in the case of slicing away infinite loops.

Our farther aim is to give a specification of the concept of slicing in terms of transfinite semantics so being independent of the actual syntax of the language. The idea of using transfinite semantics for specifying slicing is not new but it still lacks from a satisfactory realization.

Ettekande slaidid. [pdf]

*Abstract:* In computational biology approximate string
matching is a central problem. Suffix trie data structures are used as
they provide concise representation of internal structure of strings
enumerating conviently all substrings. We present how to construct
suffix tries and how to use them in applications. We mainly focus on
finding approximate matches of different patterns in a sequence as
well as approximate all-against-all matching.

Ettekande slaidid. [pdf]

*Abstract:* The ForSyDe methodology has been developed for
system design, where the design flow starts at a high abstraction
level. The initial system model in ForSyDe is described as a
functional specification model that is synchronous, deterministic and
can be executed in the functional language Haskell. The design flow
continues with the refinement of the specification model to an
implementation model. The refinement is done through a series of
applications of well-defined design transformations, which are
described in the transformation library. Both the specification and
the implementation model are described in the functional domain, which
makes it easier to verify the implementation against the specification
considering design constraints, since the same verification techniques
can be used for both models. The implementation model as a result of
the refinement process has all the low-level details required for
mapping to hardware (VHDL) and software (C++).

Ettekande slaidid. [pdf]

*Abstract:* Bideterministic automata are deterministic
automata with the property of their reversal automata also being
deterministic. It has been known that a bideterministic automaton is
the minimal deterministic automaton accepting its language. We show
that any bideterministic automaton is the unique minimal automaton
among all (including nondeterministic) automata accepting the same
language. We also present a more general result that shows that under
certain conditions a minimal deterministic automaton accepting some
language or the reversal of the minimal deterministic automaton of the
reversal language is a minimal automaton representation of the
language. These conditions can be checked in polynomial time. (Joint
work with Esko Ukkonen.)

Ettekande slaidid. [pdf]

*Abstract:* Partial functions are usually considered as
something basic or "purely functional" in functional languages, hence
semantics starts from CPO-like categories with a fixpoint operator. We
maintain that partiality due to non-termination can also be treated as
a monadic effect. The appropriate monad is the free completely
iterative monad on the identity functor, which captures timed,
possibly non-terminating computation; one can also consider the
quotient that identifies all terminating computations yielding the
same value (constructively, this is not the same as the error monad,
which can only capture partiality due to finite failure). Looping
constructions are supported immediately; we discuss general recursion
and combination of the monad with monads for other effects. (Work in
progress jointly with T. Altenkirch and V. Capretta.)

Ettekande slaidid. [pdf]

*Abstract:* Discrete controllers used in embedded systems can
be considered as reactive programs with (possibly hard) real time
constraints. The parallel composition of the controller(s) and
continuous plant has to satisfy certain safety and liveness properties
that are formulated in the form of interface specifications. A timed
automata based synthesis approach is discussed and the decidability
proof of the problem is outlined.

N. Ghani, T. Uustalu, V. Vene. Build, augment and destroy, universally, to appear in Proc. of 2nd Asian Symp. on Programming Languages and Systems, APLAS'04 (Taipei, Nov. 2004).

Ettekande slaidid. [pdf]

*Abstract:* We give a semantic footing to the 'fold/build'
syntax of programming with inductive types, covering shortcut
deforestation, based on a universal property. Specifically, we define
a semantics for inductive types based on limits of algebra structure
forgetting functors and show that it is equivalent to the usual
initial algebra semantics. We also give a similar semantic account of
the 'augment' generalization of 'build' and of the 'unfold/destroy'
syntax of coinductive types. For 'augment', we show that it is
definable for a much wider class of inductive types than has
previously been recognized. (Joint work with Neil Ghani and Tarmo
Uustalu.)

Seminari alusmaterjal. [ps.gz]

*Kokkuvõte:* Enamik krüptograafilisi primitiive ja protokolle
on turvalised vaid teatud tingimustel. Seminaris vaatame, mis saab
siis, kui need tingimused pole täidetud või kui protokoll
"lekib". Seminar ei nõua erilisi eelteadmisi, igaüks võib ennast
proovile panna.

Peeter Laud

Helger Lipmaa

Tarmo Uustalu

Varmo Vene

Viimane uuendus 11.10.2004