24 papers · ranked by Valyu relevance
Nils Lommen, Éléanore Meyer, Jürgen Giesl
Programs Authors: ['Nils Lommen' 'Éléanore Meyer' 'Jürgen Giesl'] Abstract There exist several approaches to infer runtime or resource bounds for integer programs automatically. In this paper, we study the subclass of periodic rational solvable loops (prs-loops), where questions regarding the runtime and the size of…
Jagriti Sikka, Kushal Satya, Yaman Kumar, Shagun Uppal + 2 more
'Rajiv Ratn Shah' 'Roger Zimmermann'] Abstract. Predicting the runtime complexity of a programming code is an arduous task. In fact, even for humans, it requires a subtle analysis and comprehensive knowledge of algorithms to predict time complexity with high fidelity, given any code. As per Turing's Halting problem…
Liye Guo, Deivid Vale
Time complexity in rewriting is naturally understood as the number of steps needed to reduce terms to normal forms. Establishing complexity bounds to this measure is a well-known problem in the rewriting community. A vast majority of techniques to find such bounds consist of modifying termination proofs in order to…
Martin Avanzini, Naohi Eguchi, Georg Moser
We propose a new order-theoretic characterisation of the class of polytime computable functions. To this avail we define the small polynomial path order ( $\text{sPOP}⁎$ for short). This termination order entails a new syntactic method to analyse the innermost runtime complexity of term rewrite systems fully…
Jürgen Giesl, Nils Lommen, Marcel Hark, Fabian Meyer
In [16], we developed an approach for automatic complexity analysis of integer programs, based on an alternating modular inference of upper runtime and size bounds for program parts. In this paper, we show how recent techniques to improve automated termination analysis of integer programs (like the generation of…
Sarah Winkler, Georg Moser
Logically constrained rewrite systems (LCTRSs) are a versatile and efficient rewriting formalism that can be used to model programs from various programming paradigms, as well as simplification systems in compilers and SMT solvers. In this paper, we investigate techniques to analyse the worst-case runtime complexity of…
Seungbeom Chin, Joonsuk Huh
A fundamental question in linear optical quantum computing is to understand the origin of the quantum supremacy in the physical system. It is found that the multimode linear optical transition amplitudes are calculated through the permanents of transition operator matrices, which is a hard problem for classical…
Krishnendu Chatterjee, Hongfei Fu, Aniket Murhekar
We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. Several classical textbook algorithms have quite efficient expected-runtime complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., QUICK-SORT), or…
Martin Avanzini, Georg Moser
> Abstract. This paper is concerned with the complexity analysis of constructor term rewrite systems and its ramification in implicit computational complexity. We introduce a path order with multiset status, the polynomial path order POP∗ , that is applicable in two related, but distinct contexts. On the one hand POP∗…
Thomas Reinbacher, Matthias Függer, Jörg Brauer
We present a runtime verification framework that allows on-line monitoring of past-time Metric Temporal Logic (ptMTL) specifications in a discrete time setting. We design observer algorithms for the time-bounded modalities of ptMTL, which take advantage of the highly parallel nature of hardware designs. The algorithms…
Jesper Nederlof, Céline M. F. Swennenhuis
We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized…
Yohei M. Rosen, Benedict J. Paten
Hidden Markov models of haplotype inheritance such as the Li and Stephens model allow for computationally tractable probability calculations using the forward algorithms as long as the representative reference panel used in the model is sufficiently small. Specifically, the monoploid Li and Stephens model and its…
Authors not listed
High-performance computing (HPC) environments are crucial for computational research, including quantum chemistry (QC), but pose challenges for non-expert users. Researchers with limited computational knowledge struggle to utilise domain-specific software efficiently, making mass spectra prediction for in silico…
Michele Mosca, Sebastian R. Verschoor
The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this…
Costanza Pascal, Herzeel Charlotte, Verachtert Wilfried
elPrep is an established multi-threaded framework for preparing SAM and BAM files in sequencing pipelines. To achieve good performance, its software architecture makes only a single pass through a SAM/BAM file for multiple preparation steps, and keeps sequencing data as much as possible in main memory. Similar to other…
Bertrand Marchand, Yann Ponty, Laurent Bulteau
Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time/space complexities of such approaches hinge critically on low values for the treewidth tw of the…
Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye, Nicolas Gauvrit + 1 more
'Nicolas Gauvrit' 'Matthias Dehmer'] Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings. The method is an alternative to the…
Abdullah M. Algashami, Ali Safaa Sadiq
This research dealt with the problem of scheduling applied to the supercomputer’s execution. The goal is to develop an appreciated algorithm that schedules a group of several programs characterized by their time consuming very high on different supercomputers searching for an efficient assignment of the total running…
Juan Pablo Franco, Nitin Yadav, Peter Bossaerts, Carsten Murawski
Life presents us with decisions of varying degrees of difficulty. Many of them are NP-hard, that is, they are computationally intractable. Two important questions arise: which properties of decisions drive extreme computational hardness and what are the effects of these properties on human-decision making? Here, we…
Nickolas Gantzler, Aryan Deshwal, Janardhan Rao Doppa, Cory Simon
Our objective is to search a large candidate set of covalent organic frameworks (COFs) for the one with the largest equilibrium adsorptive selectivity for xenon (Xe) over krypton (Kr) at room temperature. To predict the Xe/Kr selectivity of a COF structure, we have access to two molecular simulation techniques: (1) a…
Juan P. Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts + 1 more
The survival of human organisms depends on our ability to solve complex tasks in the face of limited cognitive resources. However, little is known about the factors that drive the complexity of those tasks. Here, building on insights from computational complexity theory, we quantify the computational hardness of…
Authors not listed
Modeling multimetallic systems efficiently enables faster prediction of desirable chemical properties and design of new materials. This work describes an initial implementation for performing multireference wave function method localized active space self-consistent field (LASSCF) calculations through the use of…
Authors not listed
Deriving versatile and robust mechanistic models from experimental data is a key challenge in engineering and natural sciences. This is especially true in chemical reaction engineering, where reactor manufacturers and operators increasingly pursue the development and maintenance of digital twins that rely on frequent…
Authors not listed
The era of exascale computing presents both exciting opportunities and unique challenges for quantum mechanical simulations. While the transition from petaflops to exascale computing has been marked by a steady increase in computational power, the shift towards heterogeneous architectures, particularly the dominant…