December 2004 - tr-announce - lists.rwth-aachen.de

2004-08: Algebraic Correctness Proofs for Compiling Recursive Function Definitions with Strictness Information
by Volker Stolz 23 Dec '04

23 Dec '04

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Klaus Indermark, Thomas Noll: Algebraic Correctness Proofs for Compiling Recursive Function Definitions with Strictness Information 2004-8 Abstract: Adding appropriate strictness information to recursive function definitions we achieve a uniform treatment of lazy and eager evaluation strategies. By restriction to first-order functions over basic types we develop a pure stack implementation that avoids a heap even for lazy arguments. We present algebraic definitions of denotational, operational, and stack-machine semantics and prove their equivalence by means of structural induction. Regards, Volker

1 0

2004-10: Secure Multi-Party Computation with Security Modules
by Volker Stolz 23 Dec '04

23 Dec '04

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Zinaida Benenson, Felix C. Gärtner, Dogan Kesdogan Secure Multi-Party Computation with Security Modules 2004-10 We consider the problem of secure multi-party computation (SMC) in a new model where individual processes contain a tamper-proof security module. Security modules can be trusted by other processes and can establish secure channels between each other. However, their availability is restricted by their host, i.e., a corrupted party can stop the computation of its own security module as well as drop any message sent by or to its security module. In this model we show that SMC is solvable if and only if a majority of processes is correct. We prove this by relating SMC to the problem of Uniform Interactive Consistency among security modules (a variant of the Byzantine Generals Problem from the area of fault-tolerance). The obtained solutions to SMC for the first time allow to compute any function securely with a complexity which is polynomial only in the number of processes (i.e., the complexity does not depend on the function which is computed). We conclude that adding secure hardware does not improve the resilience of SMC but can effectively improve the efficiency. Regards, Volker

1 0

2004-09: Parameterized Power Domination Complexity
by Volker Stolz 23 Dec '04

23 Dec '04

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith Parameterized Power Domination Complexity 2004-09 Abstract: The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as Power Dominating Set. Nodes can be measured indirectly according to Kirchhoff's law. We show that this problem can be solved in linear time for graphs of bounded treewidth and establish bounds on its parameterized complexity if the number of PMUs is the parameter. Regards, Volker

1 0