The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Optimal Vertex Elimination in Single-Expression-Use Graphs
Uwe Naumann, Yuxiao Hu
AIB 2006-08
Gradients of scalar multivariate functions can be computed by
elimination methods on the linearized computational graph. The combinatorial
optimization problem that aims to minimize the number of arithmetic operations
performed by the elimination algorithm is known to be NP-complete. In this
paper we present a polynomial algorithm for solving a relevant
subclass of this problem's instances. The proposed method relies on the ability
to compute vertex covers in bipartite graphs in polynomial time. A simplified
version of this graph algorithm is used in a research prototype of the
differentiation-enabled NAGWare Fortran compiler for the preaccumulation
of local gradients of scalar assignments in the context of automatic generation
of efficient tangent-linear code for numerical programs.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Transforming structures by set interpretations
Thomas Colcombet, Christof Löding
AIB 2006-07
We consider a new kind of interpretation over relational structures:
finite sets interpretations. Those interpretations are defined by
weak monadic second-order (WMSO) formulas with free set variables.
They transform a given structure into a structure with a domain consisting
of finite sets of elements of the orignal structure. The definition of
these interpretations directly implies that they send structures with a
decidable WMSO theory to structures with a decidable first-order theory.
In this paper, we investigate the expressive power of such interpretations
applied to infinite deterministic trees. The results can be used in
the study of automatic and tree-automatic structures.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Divide-and-Color
Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith
AIB 2006-06
We introduce divide-and-color, a new technique for the solution of hard
graph problems. It is a combination of the well-known divide-and-conquer
paradigm and color-coding. Our approach first randomly colors all
edges or nodes of a graph black and white, and then solves the problem
recursively on the two induced parts.
We demonstrate this technique by giving new randomized algorithms for
the solution of two important problems. These yield runtime bounds
of O*(4^k) for finding a simple path of length k and O*(4^((h-1)k))
for finding k edge-disjoint (resp. vertex-disjoint) copies of a graph
H with h edges (resp. h nodes) in a given graph. Derandomization gives
deterministic algorithms for these problems with running times O*(2^(4k))$
and O*(2^(4hk))$, respectively.
All these results significantly improve over the currently known best
bounds. In particular, our generic algorithms beat specialized ones
that have been designed to find k triangles or paths of length two.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Toward Low Static Memory Jacobian Accumulation
Ebadollah Varnik, Uwe Naumann, Andrew Lyons
AIB 2006-04
Derivatives are essential ingredients of a wide range of numerical
algorithms. We focus on the accumulation of Jacobian matrices by Gaussian
elimination on a sparse implementation of the extended Jacobian. A
symbolic algorithm is proposed to determine the fill-in. The first
version of the new algorithm results in a speedup of two compared to
the elimination algorithm that does not exploit sparsity.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Intraprocedural Adjoint Code Generated by the Differentiation-Enabled
NAGWare Fortran Compiler
Michael Maier, Uwe Naumann
AIB 2006-03
In this paper we report on recent advances made in the development of
the first Fortran compiler that provides intrinsic support for computing
derivatives. We focus on the automatic generation of intraprocedural
adjoint code. Technical details of the modifications made to the internal
representation as well as case studies are presented. For example, the new
feature allows for the computation of large gradients at a computational
cost that is independent of their sizes. Numerous numerical algorithms --
derivative-based optimization algorithms in particular -- will benefit
both from the convenience of the approach and from the efficiency of
the intrinsic derivative code.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Tampering with Motes: Real-World Physical Attacks on Wireless Sensor Networks
Alexander Becher, Zinaida Benenson, Maximillian Dornseif
AIB 2005-24
Most security protocols for wireless sensor networks (WSN) assume that
the adversary can gain full control over a sensor node through direct
physical access (node capture attack). But so far the amount of effort
an attacker has to undertake in a node capture attack is unknown. In
our project we evaluate different physical attacks against sensor node
hardware. Detailed knowledge about the effort needed for physical attacks
allows to fine tune security protocols in WSNs so they provide optimal
protection at minimal cost.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Decision Making Based on Approximate and Smoothed Pareto Curves
Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
AIB 2005-23
We consider bicriteria optimization problems and investigate the
relationship between two standard approaches to solving them:
(i) computing the Pareto curve and
(ii) the so-called decision maker's approach in which both criteria
are combined into a single (usually non-linear) objective function.
Previous work by Papadimitriou and Yannakakis showed how to efficiently
approximate the Pareto curve for problems like Shortest Path, Spanning
Tree, and Perfect Matching}. We wish to determine for which classes of
combined objective functions the approximate Pareto curve also yields
an approximate solution to the decision maker's problem. We show that
an FPTAS for the Pareto curve also gives an FPTAS for the decision
maker's problem if the combined objective function is growth bounded like
a quasi-polynomial function. If these functions, however, show exponential
growth then the decision maker's problem is NP-hard to approximate within
any factor. In order to bypass these limitations of approximate decision
making, we turn our attention to Pareto curves in the probabilistic
framework of smoothed analysis. We show that in a smoothed model, we
can efficiently generate the (complete and exact) Pareto curve with a
small failure probability if there exists an algorithm for generating
the Pareto curve whose worst case running time is pseudopolynomial. This
way, we can solve the decision maker's problem w.r.t. any non-decreasing
objective function for randomly perturbed instances of, e.g., Shortest
Path, Spanning Tree, and Perfect Matching.
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Optimal Randomized Fair Exchange with Secret Shared Coins
Felix Freiling, Maurice Herlihy, Lucia Draque Penso
AIB 2005-22
In the fair exchange problem, mutually untrusting parties must securely
exchange digital goods. A fair exchange protocol must ensure that no
combination of cheating or failures will result in some goods being
delivered but not others, and that all goods will be delivered in the
absence of cheating and failures.
This paper proposes two novel randomized protocols for solving fair
exchange using simple trusted units. Both protocols have an optimal
expected running time, completing in a constant (3) expected number of
rounds. They also have optimal resilience. The first one tolerates any
number of dishonest parties, as long as one is honest, while the second
one, which assumes more aggressive cheating and failures assumptions,
tolerates up to a minority of dishonest parties.
The key insight is similar to the idea underlying the code-division
multiple access (CDMA) communication protocol: outwitting an adversary
is much easier if participants share a common, secret pseudo-random
number generator.
--
Peter Schneider-Kamp mailto:psk@informatik.rwth-aachen.de
LuFG Informatik II http://www-i2.informatik.rwth-aachen.de/~nowonder
RWTH Aachen phone: ++49 241 80-21211
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Optimization of Straight-Line Code Revisited
Thomas Noll, Stefan Rieger
AIB 2005-21
In this report we study the effect of an optimizing algorithm for
straight-line code which first constructs a directed acyclic graph
representing the given program and then generates code from it. We
show that this algorithm produces optimal code with respect to the
classical transformations such as Constant Folding, Common Subexpression
Elimination, and Dead Code Elimination. In contrast to the former,
the latter are also applicable to iterative code containing loops. We
can show that the graph-based algorithm essentially corresponds to a
combination of the three classical optimizations in conjunction with Copy
Propagation. Thus, apart from its theoretical importance, this result
is relevant for practical compiler design as it allows to exploit the
optimization potential of the graph-based algorithm for non--linear code
as well.
- --
Peter Schneider-Kamp mailto:psk@informatik.rwth-aachen.de
LuFG Informatik II http://www-i2.informatik.rwth-aachen.de/~nowonder
RWTH Aachen phone: ++49 241 80-21211
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFDiw4i3VbrCXkKHhwRAhf8AJ9H7++W2iQX9svB3+2uZ9bxoLdZkwCgnTUQ
9w+LltUpvzaKW5GSv3rspBo=
=QfpP
-----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Bericht über den Workshop zur Ausbildung im Bereich IT-Sicherheit
Hochschulausbildung, berufliche Weiterbildung, Zertifizierung von
Ausbildungsangeboten am 11. und 12. August 2005 in Köln organisiert
von RWTH Aachen in Kooperation mit BITKOM, BSI, DLR und Gesellschaft
fuer Informatik (GI) e.V.
Felix C. Freiling, Martin Mink
AIB 2005-19
Dieser Bericht enthält eine Zusammenfassung des erstmalig veranstalteten
Workshops zur Ausbildung im Bereich IT-Sicherheit, an dem Vertreter von
deutschen Hochschulen und Firmen bzw. Organisationen teilnahmen.
Der Workshop bot eine Einführung und einen Überblick über drei Bereiche
der Ausbildung im Bereich IT-Sicherheit: Hochschulausbildung im Bereich
IT-Sicherheit, berufliche Weiterbildung im Bereich IT-Sicherheit, und
Zertifizierung von IT Security Professionals.
Im ersten Teil des Workshops wurden unterschiedliche Ansätze und
Ausrichtungen universitärer Ausbildungsprogramme im Bereich IT-Sicherheit
gegenübergestellt und von den Teilnehmern diskutiert. Was sind die
Ziele der Ausbildungsprogramme? Decken sie sich mit den Erwartungen
der Industrie an Absolventen? Macht ein einheitlicher Ausbildungskanon
für IT-Sicherheit an Hochschulen Sinn?
Im zweiten Teil ging es um Fragen beruflicher Weiterbildung und
Zertifizierung von IT Security Professionals, wie: Welche Angebote gibt
es? Wie unterscheiden sich die Angebote?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFDeGHF3VbrCXkKHhwRAmWjAJ9ybP/UF8WDtdXUNsKHSqnWpxlWEACgio9Q
mJEyRrZhXoJtxkWcBJ0qGUI=
=QvhM
-----END PGP SIGNATURE-----