# Invited speakers

**Charles Chidume**

International Centre for Theoretical Physics, Trieste, Italy

chidume@ictp.it

**A unified treatment of some iterative algorithms in signal processing andimage reconstruction**

_______________________________________________________________________________

Department of Computer Science

University of Tsukuba

ida@cs.tsukuba.ac.jp

**Algebraic Graph Rewriting in Computational Origami**

The art of paper folding, known as origami, provides the methodology of constructing a geometrical object out of a piece of paper solely bymeans of folding by hands. Computational origami studies the mathematicaland computational aspects of origami.

In this talk we give graph-theoretic formalization of origami. An abstract origami is represented as a triplet (\Pi, \succ, ~), where \Pi is a set of faces that constitutes an origami, and \succ and ~ are superposition and adjacency (binary) relations on \Pi, respectively. Origami construction is modeled as a rewrite sequence of abstract origami's. Now a question arises how to represent and reason about the entire origamiconstruction for the computational purposes. Good representation of the abstract origami is essential for in-depth study of origami. I present a hypergraph of origami and the abstraction of origami fold as a set of algebraic graph rewrite rules. The graph theoretic formalism enables us to reason in two separate domains of discourse, i.e. pure combinatoric domain, and geometric domain R2. This help us to tackle challenging problems such as of discovering fold sequences given an origami shape, or discovering a new origami shape that has certain geometric properties.

_______________________________________________________________________________

Research Institute for Symbolic Computation,

Johannes Kepler University, Linz, Austria

Tudor.Jebelean@risc.uni-linz.ac.at

University of Eger, Hungary

**Multi-Domain Logic and its Applications to SAT**

We describe a new formalism and special proof methods for a novel generalization of propositional logic, which is especially suitable for solving the satisfiability problem (SAT).

A Multi Domain Logic (MDL) formula is a formula in first order logic, containing only atoms of the form "x belongs to A", where each "x" is a variable existentially quantified over the whole formula, and each "A" is a constant set. All logical connectives are allowed, but no other quantifiers. Note that classical propositional logic corresponds to the special case when each set is either {T} or {F}.

Similarly to propositional logic, the conjunctive normal form of a MDL formula is a conjunctive set of MDL clauses. Each MDL clause is a disjunction of literals abbreviated as "Ax", with at most one occurrence of each variable. The union of the sets corresponding to a certain variable can be seen as "the domain" of that variable, thus MDL is also a generalization of multi-valued logic, were each variable may have a different domain. The MDL SAT problem consists in finding solutions (that is, domain values for the variables) which satisfy all clauses.

A classical propositional SAT problem can be transformed in a MDL SAT problem by merging several variables in a MDL variable. For instance, the clause "A or B or (not C) or D" becomes "{TF, FT, TT}x or {FF, FT, TT}y", where "x" represents the combined values of "AB" and "y" represents "CD". (Any number of variables can be merged.) In contrast to the well known unit propagation (which is the basis of modern SAT solvers), this representation allows the simultaneous propagation of the combined values of several classical variables. The basic idea of MDL originates from the earlier work of the second author on “hyper-unit” propagation (that is simultaneous propagation of several unit clauses) [1] and on the representation and propagation of “k-literals” (generalized literals containing information on several propositional variables) [2].

The notions of resolution, subsumption, as well as the basic steps of the DPLL method generalize in an elegant and straightforward way, and open very promising research directions towards very efficient SAT solvers.

[1] G. Kusper. Solving the resolution-free SAT Problem by hyper-unit propagation in linear time. Annals of Mathematics and Artificial Intelligence 43(1-4), 2005, pp. 129-136.

[2] G. Kusper, L. Csoke. Better test results for the Graph Coloring and the Pigeonhole Problems using DPLL with k-literal representation. ICAI-2007, Volume II, pp. 127-135, University of Eger, Hungary, 2007.

______________________________________________________________________________

Matthias Hoelzl

Institute of Computer Science

Ludwig-Maximilians-University, Munich, Germany

hoezl@informatik.uni-muenchen.de

**Constraints for Decisions with Multiple Objectives**

The IST-FET Integrated Project SENSORIA is developing a comprehensive approach to the engineering of service-oriented software systems where foundational theories, techniques and methods are fully integrated into pragmatic software engineering processes. To address problems like dynamic composition of services, we have developed a new soft-constraint formalism, called monoidal soft constraints, that allows us to easily specify optimization problems in domains with multiple competing objectives and user preferences.

We give an overview of the general SENSORIA approach, present the theory of monoidal soft constraints and show how these constraints can be applied to various problems, such as service composition or the optimization or wireless radio networks.

______________________________________________________________________________

Laboratoire d'Informatique de Paris 6, UPMC-CNRS, F-75016 Paris, France

LMIB - School of Science, Beihang University, Beijing 100191, China

**Triangular Decomposition for Algebraic and Geometric Computing**

In this talk, we present several algorithms for decomposing systems of multivariate polynomials into triangular systems of various kinds. The algorithms have been efficiently implemented and successfully applied to numerous problems of scientific computing, ranging over computational polynomial algebra, automated geometric reasoning, solving systems of nonlinear equations, qualitative analysis of biological systems, and computer aided geometric design. We discuss some of the applications with a number of illustrative examples.

_______________________________________________________________________________

University of Western Ontario, London Canada

watt@uwo.ca

**Functional Decomposition of Symbolic and Multivariate Laurent Polynomials**

Functional decomposition of polynomials is a well-studied problem with algorithms dating back at least to Ritt in the 1920s. Such functional decomposition takes a polynomial $f$ and finds lower degree polynomials $g_i$ such that $f(X) = g_1 \circ g_2 \circ \cdots \circ \g_k(X)$. Such decompositions are useful to reduce the dimension of polynomial problems and are implemented in most major computer algebra systems. Several authors have extended the problem to consider functional decomposition of rational functions, algebraic functions, approximate polynomials and Laurent polynomials. We have pre- viously studied the functional decomposition of "symbolic polynomials'', that is polynomials whose exponents are them- selves integer-valued polynomials, rather than integers.

For example, the symbolic polynomial $f(X) = 2X^{n^2+n}-4X^{n^2}+2X^{n^2-n}+1$ can be decomposed as $f = g_1 \circ g_2$, where $g_1(X) = 2X^2+1$ and $g_2(X) =X^{n^2/2+ n/2} - X^{n^2/2 - n/2}.$ The present work shows in some detail how the functional decomposition of symbolic polynomials can be related to the functional decomposition of multivariate Laurent polynomials, and shows how to solve the multivariate Laurent polynomial problem.

_______________________________________________________________________________

Hugo Zbinden

Group of Applied Physics, University of Geneva, Geneva Switzerland

hugo.zbinden@physics.unige.ch

**Random Numbers for Quantum Key Distribution**

Quantum Key Distribution (QKD) has seen an important development for the last ten years. Nowadays, different companies offer commercial solutions and key exchanges at pulse rates of up to 1 GHz and over distances of up to 200km have been demonstrated in research labs. However, the generation of random bit strings has often been neglected and it remains a technical problem, as physical random number generators have still insufficient bit rates for high speed QKD.

In this talk, after an introduction in QKD, a state of the art prototype developed at the University of Geneva will be presented. This prototype allows generating keys at high rates over up to 200km of optical fiber. However, due to the lack of high rate physical random generators, random bits at a rate of 350 MHz are produced by a pseudo random number generator seeded by random bits originating from a quantum random number generator (4MHz, id Quantique). It will be shown how an eavesdropper could attack a QKD system based on pseudo random numbers. Finally, different possibilities to increase the rates of quantum random number generators will be discussed.