-
Transforming the Bootstrap: Using Transformers to Compute Scattering Amplitudes in Planar N = 4 Super Yang-Mills Theory
Authors:
Tianji Cai,
Garrett W. Merz,
François Charton,
Niklas Nolte,
Matthias Wilhelm,
Kyle Cranmer,
Lance J. Dixon
Abstract:
We pursue the use of deep learning methods to improve state-of-the-art computations in theoretical high-energy physics. Planar N = 4 Super Yang-Mills theory is a close cousin to the theory that describes Higgs boson production at the Large Hadron Collider; its scattering amplitudes are large mathematical expressions containing integer coefficients. In this paper, we apply Transformers to predict t…
▽ More
We pursue the use of deep learning methods to improve state-of-the-art computations in theoretical high-energy physics. Planar N = 4 Super Yang-Mills theory is a close cousin to the theory that describes Higgs boson production at the Large Hadron Collider; its scattering amplitudes are large mathematical expressions containing integer coefficients. In this paper, we apply Transformers to predict these coefficients. The problem can be formulated in a language-like representation amenable to standard cross-entropy training objectives. We design two related experiments and show that the model achieves high accuracy (> 98%) on both tasks. Our work shows that Transformers can be applied successfully to problems in theoretical physics that require exact solutions.
△ Less
Submitted 9 May, 2024;
originally announced May 2024.
-
Partitioning the Bags of a Tree Decomposition Into Cliques
Authors:
Thomas Bläsius,
Maximilian Katzmann,
Marcus Wilhelm
Abstract:
We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algorithms based on similar parameters for various problems. With this paper, we take a first step towards computing clique-partitioned tree decompositions.
Our focus lies on the subproblem of computing clique partitions, i…
▽ More
We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algorithms based on similar parameters for various problems. With this paper, we take a first step towards computing clique-partitioned tree decompositions.
Our focus lies on the subproblem of computing clique partitions, i.e., for each bag of a given tree decomposition, we compute an optimal partition of the induced subgraph into cliques. The goal here is to minimize the product of the clique sizes (plus 1). We show that this problem is NP-hard. We also describe four heuristic approaches as well as an exact branch-and-bound algorithm. Our evaluation shows that the branch-and-bound solver is sufficiently efficient to serve as a good baseline. Moreover, our heuristics yield solutions close to the optimum. As a bonus, our algorithms allow us to compute first upper bounds for the clique-partitioned treewidth of real-world networks. A comparison to traditional treewidth indicates that clique-partitioned treewidth is a promising parameter for graphs with high clustering.
△ Less
Submitted 17 February, 2023;
originally announced February 2023.
-
Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks
Authors:
Thomas Bläsius,
Marcus Wilhelm
Abstract:
A common technique to speed up shortest path queries in graphs is to use a bidirectional search, i.e., performing a forward search from the start and a backward search from the destination until a common vertex on a shortest path is found. In practice, this has a tremendous impact on the performance on some real-world networks, while it only seems to save a constant factor on other types of networ…
▽ More
A common technique to speed up shortest path queries in graphs is to use a bidirectional search, i.e., performing a forward search from the start and a backward search from the destination until a common vertex on a shortest path is found. In practice, this has a tremendous impact on the performance on some real-world networks, while it only seems to save a constant factor on other types of networks. Even though finding shortest paths is a ubiquitous problem, there are only few studies attempting to understand the apparently asymptotic speedups on some networks, using average case analysis on certain models for real-world networks.
In this paper we give a new perspective on this, by analyzing deterministic properties that permit theoretical analysis and that can easily be checked on any particular instance. We prove that these parameters imply sublinear running time for the bidirectional breadth-first search in several regimes, some of which are tight. Moreover, we perform experiments on a large set of real-world networks showing that our parameters capture the concept of practical running time well.
△ Less
Submitted 3 April, 2023; v1 submitted 30 September, 2022;
originally announced September 2022.
-
Modeling Task Mapping for Data-intensive Applications in Heterogeneous Systems
Authors:
Martin Wilhelm,
Hanna Geppert,
Anna Drewes,
Thilo Pionteck
Abstract:
We introduce a new model for the task mapping problem to aid in the systematic design of algorithms for heterogeneous systems including, but not limited to, CPUs, GPUs and FPGAs. A special focus is set on the communication between the devices, its influence on parallel execution, as well as on device-specific differences regarding parallelizability and streamability. We show how this model can be…
▽ More
We introduce a new model for the task mapping problem to aid in the systematic design of algorithms for heterogeneous systems including, but not limited to, CPUs, GPUs and FPGAs. A special focus is set on the communication between the devices, its influence on parallel execution, as well as on device-specific differences regarding parallelizability and streamability. We show how this model can be utilized in different system design phases and present two novel mixed-integer linear programs to demonstrate the usage of the model.
△ Less
Submitted 12 August, 2022;
originally announced August 2022.
-
Conditional Inference and Activation of Knowledge Entities in ACT-R
Authors:
Marco Wilhelm,
Diana Howey,
Gabriele Kern-Isberner,
Kai Sauerwald,
Christoph Beierle
Abstract:
Activation-based conditional inference applies conditional reasoning to ACT-R, a cognitive architecture developed to formalize human reasoning. The idea of activation-based conditional inference is to determine a reasonable subset of a conditional belief base in order to draw inductive inferences in time. Central to activation-based conditional inference is the activation function which assigns to…
▽ More
Activation-based conditional inference applies conditional reasoning to ACT-R, a cognitive architecture developed to formalize human reasoning. The idea of activation-based conditional inference is to determine a reasonable subset of a conditional belief base in order to draw inductive inferences in time. Central to activation-based conditional inference is the activation function which assigns to the conditionals in the belief base a degree of activation mainly based on the conditional's relevance for the current query and its usage history. Therewith, our approach integrates several aspects of human reasoning into expert systems such as focusing, forgetting, and remembering.
△ Less
Submitted 28 October, 2021;
originally announced October 2021.
-
From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization
Authors:
Lukas Behrendt,
Katrin Casel,
Tobias Friedrich,
J. A. Gregor Lagodzinski,
Alexander Löser,
Marcus Wilhelm
Abstract:
We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymmetric distances in the given instance, which yields algorithms to efficiently compute constant factor approximations also for moderately asymmetric TS…
▽ More
We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymmetric distances in the given instance, which yields algorithms to efficiently compute constant factor approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the number of asymmetric edges in a given minimum spanning arborescence. Both algorithms are also stated in the form of additive lossy kernelizations, which allows to combine them with known polynomial time approximations for ATSP. Further, we combine them with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. We complement our results by experimental evaluations, which show that generalized tree-doubling frequently outperforms generalized Christofides with respect to parameter size.
△ Less
Submitted 26 February, 2020; v1 submitted 6 November, 2019;
originally announced November 2019.
-
Insights into the Mind of a Trojan Designer: The Challenge to Integrate a Trojan into the Bitstream
Authors:
Maik Ender,
Pawel Swierczynski,
Sebastian Wallat,
Matthias Wilhelm,
Paul Martin Knopp,
Christof Paar
Abstract:
The threat of inserting hardware Trojans during the design, production, or in-field poses a danger for integrated circuits in real-world applications. A particular critical case of hardware Trojans is the malicious manipulation of third-party FPGA configurations. In addition to attack vectors during the design process, FPGAs can be infiltrated in a non-invasive manner after shipment through altera…
▽ More
The threat of inserting hardware Trojans during the design, production, or in-field poses a danger for integrated circuits in real-world applications. A particular critical case of hardware Trojans is the malicious manipulation of third-party FPGA configurations. In addition to attack vectors during the design process, FPGAs can be infiltrated in a non-invasive manner after shipment through alterations of the bitstream. First, we present an improved methodology for bitstream file format reversing. Second, we introduce a novel idea for Trojan insertion.
△ Less
Submitted 1 October, 2019;
originally announced October 2019.
-
Security for Distributed Deep Neural Networks Towards Data Confidentiality & Intellectual Property Protection
Authors:
Laurent Gomez,
Marcus Wilhelm,
José Márquez,
Patrick Duverger
Abstract:
Current developments in Enterprise Systems observe a paradigm shift, moving the needle from the backend to the edge sectors of those; by distributing data, decentralizing applications and integrating novel components seamlessly to the central systems. Distributively deployed AI capabilities will thrust this transition. Several non-functional requirements arise along with these developments, securi…
▽ More
Current developments in Enterprise Systems observe a paradigm shift, moving the needle from the backend to the edge sectors of those; by distributing data, decentralizing applications and integrating novel components seamlessly to the central systems. Distributively deployed AI capabilities will thrust this transition. Several non-functional requirements arise along with these developments, security being at the center of the discussions. Bearing those requirements in mind, hereby we propose an approach to holistically protect distributed Deep Neural Network (DNN) based/enhanced software assets, i.e. confidentiality of their input & output data streams as well as safeguarding their Intellectual Property. Making use of Fully Homomorphic Encryption (FHE), our approach enables the protection of Distributed Neural Networks, while processing encrypted data. On that respect we evaluate the feasibility of this solution on a Convolutional Neuronal Network (CNN) for image classification deployed on distributed infrastructures.
△ Less
Submitted 9 July, 2019;
originally announced July 2019.
-
Internal versus external balancing in the evaluation of graph-based number types
Authors:
Hanna Geppert,
Martin Wilhelm
Abstract:
Number types for exact computation are usually based on directed acyclic graphs. A poor graph structure can impair the efficency of their evaluation. In such cases the performance of a number type can be drastically improved by restructuring the graph or by internally balancing error bounds with respect to the graph's structure. We compare advantages and disadvantages of these two concepts both th…
▽ More
Number types for exact computation are usually based on directed acyclic graphs. A poor graph structure can impair the efficency of their evaluation. In such cases the performance of a number type can be drastically improved by restructuring the graph or by internally balancing error bounds with respect to the graph's structure. We compare advantages and disadvantages of these two concepts both theoretically and experimentally.
△ Less
Submitted 21 August, 2019; v1 submitted 3 April, 2019;
originally announced April 2019.
-
On error representation in exact-decisions number types
Authors:
Martin Wilhelm
Abstract:
Accuracy-driven computation is a strategy widely used in exact-decisions number types for robust geometric algorithms. This work provides an overview on the usage of error bounds in accuracy-driven computation, compares different approaches on the representation and computation of these error bounds and points out some caveats. The stated claims are supported by experiments.
Accuracy-driven computation is a strategy widely used in exact-decisions number types for robust geometric algorithms. This work provides an overview on the usage of error bounds in accuracy-driven computation, compares different approaches on the representation and computation of these error bounds and points out some caveats. The stated claims are supported by experiments.
△ Less
Submitted 11 July, 2018;
originally announced July 2018.
-
Restructuring expression dags for efficient parallelization
Authors:
Martin Wilhelm
Abstract:
In the field of robust geometric computation it is often necessary to make exact decisions based on inexact floating-point arithmetic. One common approach is to store the computation history in an arithmetic expression dag and to re-evaluate the expression with increasing precision until an exact decision can be made. We show that exact-decisions number types based on expression dags can be evalua…
▽ More
In the field of robust geometric computation it is often necessary to make exact decisions based on inexact floating-point arithmetic. One common approach is to store the computation history in an arithmetic expression dag and to re-evaluate the expression with increasing precision until an exact decision can be made. We show that exact-decisions number types based on expression dags can be evaluated faster in practice through parallelization on multiple cores. We compare the impact of several restructuring methods for the expression dag on its running time in a parallel environment.
△ Less
Submitted 9 April, 2018;
originally announced April 2018.
-
Multithreading for the expression-dag-based number type Real_algebraic
Authors:
Martin Wilhelm
Abstract:
Many algorithms, especially in the field of computational geometry, are based on the premise that arithmetic operations are performed exactly. Real machines are based on inexact floating-point arithmetic. Various number types have been developed to close this gap by providing exact computation or ensuring exact decisions. In this report we describe the implementation of an extension to the exact-d…
▽ More
Many algorithms, especially in the field of computational geometry, are based on the premise that arithmetic operations are performed exactly. Real machines are based on inexact floating-point arithmetic. Various number types have been developed to close this gap by providing exact computation or ensuring exact decisions. In this report we describe the implementation of an extension to the exact-decisions number type Real_algebraic that enables us to take advantage of multiple processing units.
△ Less
Submitted 3 April, 2018; v1 submitted 19 February, 2018;
originally announced February 2018.
-
Balancing expression dags for more efficient lazy adaptive evaluation
Authors:
Martin Wilhelm
Abstract:
Arithmetic expression dags are widely applied in robust geometric computing. In this paper we restructure expression dags by balancing consecutive additions or multiplications. We predict an asymptotic improvement in running time and experimentally confirm the theoretical results. Finally, we discuss some pitfalls of the approach resulting from changes in evaluation order.
Arithmetic expression dags are widely applied in robust geometric computing. In this paper we restructure expression dags by balancing consecutive additions or multiplications. We predict an asymptotic improvement in running time and experimentally confirm the theoretical results. Finally, we discuss some pitfalls of the approach resulting from changes in evaluation order.
△ Less
Submitted 12 October, 2017;
originally announced October 2017.
-
An Analytical Model of Packet Collisions in IEEE 802.15.4 Wireless Networks
Authors:
Matthias Wilhelm,
Vincent Lenders,
Jens B. Schmitt
Abstract:
Numerous studies showed that concurrent transmissions can boost wireless network performance despite collisions. While these works provide empirical evidence that concurrent transmissions may be received reliably, existing signal capture models only partially explain the root causes of this phenomenon. We present a comprehensive mathematical model that reveals the reasons and provides insights on…
▽ More
Numerous studies showed that concurrent transmissions can boost wireless network performance despite collisions. While these works provide empirical evidence that concurrent transmissions may be received reliably, existing signal capture models only partially explain the root causes of this phenomenon. We present a comprehensive mathematical model that reveals the reasons and provides insights on the key parameters affecting the performance of MSK-modulated transmissions. A major contribution is a closed-form derivation of the receiver bit decision variable for arbitrary numbers of colliding signals and constellations of power ratios, timing offsets, and carrier phase offsets. We systematically explore the root causes for successful packet delivery under concurrent transmissions across the whole parameter space of the model. We confirm the capture threshold behavior observed in previous studies but also reveal new insights relevant for the design of optimal protocols: We identify capture zones depending not only on the signal power ratio but also on time and phase offsets.
△ Less
Submitted 18 August, 2014; v1 submitted 19 September, 2013;
originally announced September 2013.
-
Air Dominance in Sensor Networks: Guarding Sensor Motes using Selective Interference
Authors:
Matthias Wilhelm,
Ivan Martinovic,
Jens B. Schmitt,
Vincent Lenders
Abstract:
Securing wireless sensor networks (WSNs) is a hard problem. In particular, network access control is notoriously difficult to achieve due to the inherent broadcast characteristics of wireless communications: an attacker can easily target any node in its transmission range and affect large parts of a sensor network simultaneously. In this paper, we therefore propose a distributed guardian system to…
▽ More
Securing wireless sensor networks (WSNs) is a hard problem. In particular, network access control is notoriously difficult to achieve due to the inherent broadcast characteristics of wireless communications: an attacker can easily target any node in its transmission range and affect large parts of a sensor network simultaneously. In this paper, we therefore propose a distributed guardian system to protect a WSN based on physically regulating channel access by means of selective interference. The guardians are deployed alongside a sensor network, inspecting all local traffic, classifying packets based on their content, and destroying any malicious packet while still on the air. In that sense, the system tries to gain "air dominance" over attackers. A key challenge in implementing the guardian system is the resulting real-time requirement in order to classify and destroy packets during transmission. We present a USRP2 software radio based guardian implementation for IEEE 802.15.4 that meets this challenge; using an FPGA-based design we can even check for the content of the very last payload byte of a packet and still prevent its reception by a potential victim mote. Our evaluation shows that the guardians effectively block 99.9% of unauthorized traffic in 802.15.4 networks in our experiments, without disturbing the legitimate operations of the WSN.
△ Less
Submitted 17 May, 2013;
originally announced May 2013.
-
Key Generation in Wireless Sensor Networks Based on Frequency-selective Channels - Design, Implementation, and Analysis
Authors:
Matthias Wilhelm,
Ivan Martinovic,
Jens B. Schmitt
Abstract:
Key management in wireless sensor networks faces several new challenges. The scale, resource limitations, and new threats such as node capture necessitate the use of an on-line key generation by the nodes themselves. However, the cost of such schemes is high since their secrecy is based on computational complexity. Recently, several research contributions justified that the wireless channel itself…
▽ More
Key management in wireless sensor networks faces several new challenges. The scale, resource limitations, and new threats such as node capture necessitate the use of an on-line key generation by the nodes themselves. However, the cost of such schemes is high since their secrecy is based on computational complexity. Recently, several research contributions justified that the wireless channel itself can be used to generate information-theoretic secure keys. By exchanging sampling messages during movement, a bit string can be derived that is only known to the involved entities. Yet, movement is not the only possibility to generate randomness. The channel response is also strongly dependent on the frequency of the transmitted signal. In our work, we introduce a protocol for key generation based on the frequency-selectivity of channel fading. The practical advantage of this approach is that we do not require node movement. Thus, the frequent case of a sensor network with static motes is supported. Furthermore, the error correction property of the protocol mitigates the effects of measurement errors and other temporal effects, giving rise to an agreement rate of over 97%. We show the applicability of our protocol by implementing it on MICAz motes, and evaluate its robustness and secrecy through experiments and analysis.
△ Less
Submitted 5 May, 2010;
originally announced May 2010.
