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
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
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