Abstract: We focused on the question - what kind of collision-finding attacks have influence on the security of time-stamping schemes? In our analysis, we distinguish between client-side hash functions used to shorten the documents before sending them to time-stamping servers and server-side hash functions used for establishing one way causal relations between time stamp requests. We derive necessary and sufficient conditions for client side hash functions and show by using explicit separation techniques that neither collision-resistance nor 2nd preimage resistance is necessary for secure time-stamping. Moreover, we show that server side hash functions can even be not one-way. This shows that no generic collision-finders to black-box hash functions can be turned into wrappers that break the corresponding time-stamping schemes. Each such wrapper should analyze the structure of the hash function. However, these separations do not necessarily hold for more specific classes of hash functions. Considering this, we take a more detailed look at the structure of practical hash functions by studying the Merkle-Damgaard (MD) hash functions. We show that attacks, which are able to find collisions for MD hash functions with respect to randomly chosen initial states, also violate the necessary security conditions for client-side hash functions. This does not contradict the black-box separations results because the MD structure is already a deviation from the black-box setting. As a practical consequence, MD5, Sha-0, and RIPEMD are no more recommended to use as a client-side hash function in time-stamping schemes. However, as we show, there is still no evidence against using MD5 (or even MD4) as a server-side hash function. (Joint work with Sven Laur).
Ettekande kiled. [pdf]
Abstract: Hash functions are widely used for distributing data pseudorandomly accross hash tables for fast access. Bit-state hashing is a well known method in model checking for reducing memory consumption of the whole state space search by storing only a single bit for each seen state at the address calculated by the hash function. The drawback of the method is the possibility of hash collisions that will result in unexplored parts of the search space. We look at how changing the behaviour of a hash function by changing the size of the hash table influences the performance of bit-state hashing and compare it to the approach of replacing the hash function with an abstraction function for the sake of utilizing the previously referred collisions for abstraction.
Ettekande kiled. [pdf]
Abstract: Planted motif problem is a benchmark problem for evaluating string motif discovery programs, which are extensively used in bioinformatics. A set of long strings is generated randomly and a short string motif is planted into a random position in each of the long strings. The planting process is not exact and some "mutations" may occur. The task is to find the short string motif, given the set of long strings. We will interactively solve the task and discuss the probability of having a solution in random strings without the planted motif.
Abstract: The issue of security of the information flow in a system arises if the inputs and outputs of the system have been partitioned into different security classes. In this case we want the high-security (private) inputs to not influence the low-security (public) outputs in a way that is useful for an adversary trying to gain some new information about these inputs. In this tutorial we give an overview of possible definitions of secure information flow for different classes of systems, as well as means to check the security of information flow.
Ettekande kiled. [pdf]
Abstract: One of the most common aspects of (programming) languages, logics and semantics is the concept of name and the action of naming. These aspects are so buried in our habits that we hardly ever talk about them. In fact, the action of naming can be seen as the archetypal mechanism of abstraction, in the sense that it allows to isolate and crystallize into names specific aspects of more complex concepts, which are thus easier to deal with. A closer look will reveal that there are several, and quite different, abstractions paradigms which names can be used for. Different paradigms yield different behaviors of names, and sometimes these differences have been source of confusion in the past. In this talk, we will analyze some prominent abstraction paradigms in the theory of programming languages, of process calculi, of logics and semantics; we will see the different roles played by names in these situations. Then we discuss some recent developments in the theory of these situations, with particular care to semantic models and general logical systems for reasoning about them.
Ettekande kiled. [pdf]
Abstract: Recently, it has turned out that transfinite semantics is useful for constructing a sound mathematical framework of some program transformation techniques like program slicing. On the other hand, transfinite semantics may seem a bit artificial solution; moreover, using them for recursive imperative programs involves serious problems.
We introduce trace semantics where trace components are indexed with rational numbers. Call these semantics rational. Rational semantics turns out to be a uniform framework to both recursive and non-recursive imperative programs. Thereby, rational semantics can be naturally given so that, for non-recursive programs, it in principle coincides with transfinite semantics (the difference is only in indexing of components).
Ettekande kiled. [pdf]
Abstract: A finite array is a set with "lookup" and "update" maps on it subject to the axiomatics of global state of Plotkin and Power. Finite arrays model a memory on which one admits the two operations above. In this paper we study potentially infinite arrays, with a collection of maps representing "allocation" of fresh portions of memory. These arrays are defined on omega-chains, where each set in a chain determines the finite array of the corresponding dimension. Power and Shkaravska have shown that finite arrays are comonadic over Set. Here we show that the category of potentially infinite arrays is comonadic over omega-chains. Plotkin and Power have studied a "local state" monad for fresh memory allocation. The result presented here is not a dual for their result, but rather it is its simplified version. The monad of Plotkin and Power is given over the presheaves, which map the category of finite sets and injections onto Set.
Abstract: Position Weight Matrices (PWMs) can not describe polymorphisms in the TFBS that are derived from evolutionary events as insertions or deletions. In this work we extend the use of PWMs for the description of varied length TFBS (for the same TF). We combine the PWMs with the Levenshtein Distance (edit distance) and allow the introduction of insertions and deletions. We apply our method in the promoter region of genes with a similar expression profile, in order to discover 'undetected' TFBS that are possible to explain the similarities in the expression profiles. (Joint work with Pavlos Pavlidis).
Ettekande kiled. [pdf]
Abstract: We present a method for size reduction of two-way multitape automata. Our algorithm applies local transformations that change the order in which transitions concerning different tapes occur in the automaton graph, and merge suitable states into a single state. Our work is motivated by implementation of a language for string manipulation in database systems where string predicates are compiled into two-way multitape automata. Additionally, we present a (one-tape) NFA reduction algorithm that is based on a method proposed for DFA minimization by Kameda and Weiner, and apply this algorithm, combined with the multitape automata reduction algorithm, on our multitape automata. (Joint work with Matti Nykänen and Esko Ukkonen, presented at CIAA 2005, LNCS 3845, pp 307-318).
Kokkuvõte: Lineaarne regressioon on levinud statistiline mudel, mis kirjeldab valjundi Y sõltuvust sisenditest X1, X2, ..., Xn lineaarteisendusega Y = a1 X1 + a2 X2 + ... + an Xn. Reeglina valitakse mudeli koefitsendid nii, et need minimiseeriks mudeli viga valimil. Sellise meetodiga saadavad tulemused pole paljude masinõppimisega seotud rakendustes rahuldavad. Väikeste valimite korral võib koefitsentide väärtuste variatsioon olla suur, põhjustades mudeli ennustustäpsuse olulise languse. Teiseks on raske interpreteerida lineaarset mudeli poolt kirjeldatud sõltuvusi, kui nullist erinevaid koefitsente on piisavalt palju.
Mitmete alternatiivsete lineaarse regressiooni algoritmide eesmärgiks on leida parim väheste nullist erinevate koefitsentidega mudel. Ettekandes käsitleme lineaarse regresiooni algoritmide peret LARS. Peaeesmärgiks on näidata, et LARS-i saab dualiseerida - esitada dimensioonist sõltumatute lineaarsete operatsioonide abil. See annab võimaluse kombineerida LARS-i tuumateisendustega, mis omakorda võimaldab kasutada LARS-i oluliste tunnuste automaatsel valikul. (Ühistöö Sven Lauriga).
Ettekande kiled. [pdf]
Abstract: Huet's zipper datatype provides a way for representing trees with a focus and for refocussing. Attribute evaluation is a form of computation on trees where a tree is taken into a tree of the same shape where the values at the nodes are computed uniformly for every node. We show that while the zipper operations are a tool for describing the computations for each individual node, the computation on the whole is organized by a comonad structure that is present in the zipper. (Joint work with Varmo Vene.)
Abstract: We are giving a brief overview of Domain Decomposition methods, their parallel implementation and performance. We discuss a class of such methods based on aggregation algorithms for parallel solution of highly heterogeneous PDEs with strong coefficient variations. We will outline implementation of the methods in the DOUG (Domain Decomposition on Unstructured Grids) package. At the same time we discuss some ideas about implementation of the methods on computational GRIDs.
Ettekande kiled. [pdf]
Abstract: We show that cyclic structures, i.e., finite or possibly infinite structures with back-pointers, unrollable into possibly infinite structures, can be elegantly represented as nested datatypes. This representation is free of the various deficiencies characterizing the more naive representation as mixed-variant datatypes. It is inspired by the representation of lambda-terms as a nested datatype via the de Bruijn notation.
Abstract: We will show how to study inner structure of the graphs (cliques, minimal feedback edges aso) and tournaments best ranking problems using some simple ideas about monotone systems.
Peeter Laud