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

2006-08: Optimal Vertex Elimination in Single-Expression-Use Graphs
by Peter Schneider-Kamp 24 May '06

24 May '06

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.

1 0

2006-07: Transforming structures by set interpretations
by Peter Schneider-Kamp 23 May '06

23 May '06

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.

1 0

2006-06: Divide-and-Color
by Peter Schneider-Kamp 18 May '06

18 May '06

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.

1 0

2006-04: Toward Low Static Memory Jacobian Accumulation
by Peter Schneider-Kamp 05 Apr '06

05 Apr '06

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.

1 0

2006-03: Intraprocedural Adjoint Code Generated by the Differentiation-Enabled NAGWare Fortran Compiler
by Peter Schneider-Kamp 03 Apr '06

03 Apr '06

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.

1 0

2005-24: Tampering with Motes: Real-World Physical Attacks on Wireless Sensor Networks
by Peter Schneider-Kamp 03 Feb '06

03 Feb '06

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.

1 0

2005-23: Decision Making Based on Approximate and Smoothed Pareto Curves
by Peter Schneider-Kamp 14 Dec '05

14 Dec '05

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.

1 0

2005-22: Optimal Randomized Fair Exchange with Secret Shared Coins
by Peter Schneider-Kamp 07 Dec '05

07 Dec '05

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

1 0

2005-21: Optimization of Straight-Line Code Revisited
by Peter Schneider-Kamp 28 Nov '05

28 Nov '05

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

1 0

2005-20: 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.
by Peter Schneider-Kamp 14 Nov '05

14 Nov '05

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

1 0