21 papers · ranked by Valyu relevance
Nils Lommen, Jürgen Giesl
In earlier work, we developed a modular approach for automatic complexity analysis of integer programs. However, these integer programs do not allow non-tail recursive calls or subprocedures. In this paper, we consider integer programs with function calls and present a natural extension of our modular complexity…
Rome, Hayden, Lynch, Jayson + 6 more
Algorithm research focuses primarily on how many operations processors need to do (time complexity). But for many problems, both the runtime and energy used are dominated by memory accesses. In this paper, we present the first broad survey of how algorithmic progress has improved memory usage (space complexity). We…
Maximilian Vierlboeck, Antonio Pugliese, Roshanak Nilchian, Paul T. Grogan + 1 more
—Complexity in engineered systems presents one of the most persistent challenges in modern development since it is driving cost overruns, schedule delays, and outright project failures. Yet while architectural complexity has been studied, the structural complexity embedded within requirements specifications remains…
David A. Juckett, Pasquale Stano, James R. Lyons
The origin of life embodies two fundamental questions: how and when did life begin? It is commonly conjectured that life began on Earth around 4 billion years ago. This requires that the complex organization of RNA, DNA, triplet codon, protein, and lipid membrane (RDTPM) architecture was easy to establish between the…
Louis Rustenholz, Manuel V. Hermenegildo, Pedro Lopez-Garcia, Alessio Mansutti + 2 more
We present the theory underpinning a complexity analysis tool (under development) that aims at automating tedious parts of the analysis of complex algorithms originating from the field of automated reasoning. Examples are given by super-exponential quantifier elimination procedures in real and integer arithmetics. Our…
Mengqi Zhang, Guangqiang Teng, Xiaoyu Lei, Boris Ryabko
Lei proposed an algorithm Algorithm $A_{3}$ in 2023 to generate an exact discrete uniform distribution from an unknown biased Bernoulli source. The present paper does not claim a new extraction algorithm. Its contributions are analytical: first, we provide a Fourier-analytic proof of the uniformity mechanism based on…
Markel Zubia, Rob Nederpelt
Infinite words, also known as streams, hold significant interest in computer science and mathematics, raising the natural question of how their complexity should be measured. We introduce cellular automaton reducibility as a measure of stream complexity: σ is at least as complex as τ when there exists a cellular…
Abrahim Ladha, Yiran Luo, Alan Tian
While the Church-Turing thesis asserts that effective calculability explicates to sets decidable by a Turing machine, the Cobham-Edmonds thesis asserts that feasible computation explicates to the complexity class $\mathsf{P}$, those decidable by a polynomial-time bounded Turing machine. The Church-Turing thesis has…
Zoe Leyva-Acosta, Eduardo Acuña Yeomans, Francisco Hernández-Quiroz, Ming Li
Algorithmic complexity is a foundational notion in theoretical computer science, but its incomputability has led to two families of practical estimators: compression-based and program-execution-based (e.g., the Coding Theorem Method, CTM). Despite widespread use, the correspondence between these paradigms remains…
Boumediene Hamzi, Marianne Clausel, Kamal Dingle, Marcus Hutter + 2 more
Spurious correlations between time series are a persistent problem: simple, low-complexity patterns are abundant, so unrelated series can easily exhibit high Pearson correlation. We argue that Kolmogorov complexity-a series’ resistance to compression-provides a principled diagnostic for flagging such cases. We prove an…
Milan Lopuhaä-Zwakenberg
Quantitative analysis of risk models is essential to ensure the resilience of complex systems. Fault trees (FTs) form a ubiquitous prominent risk model, and unreliability is its key safety metric. As complex systems have larger and larger models, the complexity of algorithms computing unreliability is a pressing…
Samuel Everett
We begin development of a method for studying dynamical systems using concepts from computational complexity theory. We associate families of decision problems, called telic problems, to dynamical systems of a certain class. These decision problems formalize finite-time reachability questions for the dynamics with…
Authors not listed
A framework for catalysis based on categorical aperture selection rather than temporal acceleration is presented. Traditional catalysis theory describes catalysts as agents that accelerate reactions by lowering activation energies, implicitly treating time as the fundamental variable and reaction rate enhancement as…
Eduardo Y. Sakabe, Felipe S. Abrahão, Alexandre Simões, Esther Colombini + 3 more
Understanding and controlling the complexity of neural networks is a central challenge in machine learning, with implications for generalization, optimization, and model capacity. While most approaches rely on entropy-based loss functions and statistical metrics, these measures often fail to capture deeper, causally…
Attila Egri-Nagy, Chrystopher L. Nehaniv
Computational power can be measured by assigning an algebraic structure to a computational device. Here, we convert a small patch of Conway's Game of Life into a transformation semigroup. The conversion captures not only time evolution but also interactive operations. In this way, the cellular automaton becomes…
Authors not listed
The Polytope Formalism provides a rigorous and unifying mathematical framework for representing all possible molecular configurations and their interrelationships. Extending its application from stereoisomerism to molecular constitution reveals that both arise from a common structural foundation linking discrete and…
Authors not listed
This work establishes theoretical foundations for hierarchical quantum-classical algorithm design, where complex problems are decomposed across multiple spatial, temporal, or organizational scales with quantum and classical computation assigned to appropriate levels. We develop a mathematical framework that…
Authors not listed
RNA molecules fold into complex three-dimensional structures that determine their function. A wide range of mathematical frameworks, such as chord diagrams, fatgraphs, and context-free grammars, have been used to represent these structures; however, these models have largely been developed from mathematical motivations…
Authors not listed
AI-driven molecular generation encounters a "generation-synthesis gap": most computationally designed molecules cannot be synthesized in laboratories, limiting AI-assisted drug design (AIDD) applications. Current approaches to assess synthetic accessibility (SA) include computer-aided synthesis planning (CASP) tools…
Ido Aizenbud, David Beniaguev, Noam Pnueli, Idan Segev + 1 more
Cortical pyramidal neurons possess elaborate dendritic trees with diverse nonlinear membrane conductances and thousands of plastic synapses, suggesting substantial computational capabilities at the single-cell level. Yet, what can a neuron compute remains an open question, largely due to the lack of a systematic…
Alex N Popinga, Jack Forman, Dmitri Svetlov, Huy Vo + 1 more
Biological data is prone to both intrinsic and extrinsic noise and variability between experimental replicas. That same stochasticity and heterogeneity can carry information about underlying biochemical mechanisms but, if not incorporated in modeling and probabilistic inference, can also bias parameter estimates and…