19 papers · ranked by Valyu relevance
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…
Ananth Goyal
We propose an approach to determine the continual progression of algorithmic efficiency, as an alternative to standard calculations of time complexity, likely, but not exclusively, when dealing with data structures with unknown maximum indexes and with algorithms that are dependent on multiple variables apart from just…
Jose Divasón, Sebastiaan J. C. Joosten, René Thiemann, Akihisa Yamada
'Akihisa Yamada'] We formally verify the Berlekamp-Zassenhaus algorithm for factoring square-free integer polynomials in Isabelle/HOL. We further adapt an existing formalization of Yun’s square-free factorization algorithm to integer polynomials, and thus provide an efficient and certified factorization algorithm for…
Holger Dell, Anselm Haak, Melvin Kallmayer, Leo Wennmann
We present a randomized algorithm for solving low-degree polynomial equation systems over finite fields faster than exhaustive search. In order to do so, we follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA 2017), Björklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In…
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∗…
Bjorn K. Berntson, Christoph Sünderhauf
Quantum signal processing is a framework for implementing polynomial functions on quantum computers. To implement a given polynomial P, one must first construct a corresponding complementary polynomial*Q. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We…
Zijun Wu, Rolf H. Möhring, Jianhui Lai
For simple TSP instances that have a {1, n}-valued distance function and a unique optimal solution, we show that sample size N ∈ ω(ln n) results in a stochastically polynomial runtime, and N ∈ O(ln n) results in a stochastically exponential runtime, where "stochastically" means with a probability of 1 − n −ω(1) , and n…
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…
Daniel Rubio Bonilla, Colin W. Glass, Jan Kuper
In this paper we discuss how semantic annotations can be used to introduce mathematical algorithmic information of the underlying imperative code to enable compilers to produce code transformations that will enable better performance. By using this approaches not only good performance is achieved, but also better…
Pavel Emelyanov, Denis Ponomaryov
In 2010, A. Shpilka and I. Volkovich established a prominent result on the equivalence of polynomial factorization and identity testing. It follows from their result that a multilinear polynomial over the finite field of order 2 can be factored in time cubic in the size of the polynomial given as a string. Later, we…
Alin Bostan, Vincent Neiger, Sergey Yurkevich
The th power of a polynomial matrix of fixed size and degree can be computed by binary powering as fast as multiplying two polynomials of linear degree in . When Fast Fourier Transform (FFT) is available, the resulting complexity is softly linear in , i.e. linear in with extra logarithmic factors. We show that it is…
Seth D. Temple, Sharon R. Browning, Elizabeth A. Thompson
The worst-case runtime complexity to simulate identity-by-descent segments is quadratic in sample size. We propose two main techniques to reduce the compute time, which are motivated by coalescent and recombination processes. We observe average runtimes to simulate detectable IBD segments around a locus that scale…
Pencho Yordanov, Jörg Stelling
Kirchhoff polynomials are central for deriving symbolic steady-state expressions of models whose dynamics are governed by linear diffusion on graphs. In biology, such models have been unified under a common linear framework subsuming studies across areas such as enzyme kinetics, G-protein coupled receptors, ion…
Authors not listed
Computing electrostatic interactions remains the bottleneck of molecular dynamics (MD) simulations despite more than a century of effort in developing methods to accelerate the calculation. Previously we have developed the Spherical Grid and Treecode (SGT) and Gauss-Legendre-Spherical-t (GLST) algorithms for…
Babak Emami, Wesley Dyk, David Haycraft, Jenn Robinson + 3 more
Computational protein design is a foundational challenge in biotechnology, advantageous for engineering novel enzymes and therapeutics, yet its combinatorial complexity remains a bottleneck for classical optimization. We formulate fixed–backbone computational protein design as a quadratic Hamiltonian over rotamer…
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…
Pengyu Liu, Matthew Gould, Caroline Colijn
Phylogenetic trees are a central tool in evolutionary biology. They demonstrate evolutionary patterns among species, genes, and with modern sequencing technologies, patterns of ancestry among sets of individuals. Phylogenetic trees usually consist of tree shapes, branch lengths and partial labels. Comparing tree shapes…
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…
Nikolai Baudis, Pierre Barbera, Sebastian Graf, Sarah Lutteropp + 3 more
In the context of a master level programming practical at the computer science department of the Karlsruhe Institute of Technology, we developed and make available two independent and highly optimized open-source implementations for the pair-wise statistical alignment model, also known as TKF91, that was developed by…