The mathematical foundations of computing, including algorithms, complexity theory, automata theory, formal languages, cryptography, and the theoretical limits of computation
11 papersThis paper presents a mathematically rigorous framework for identifying and completing Coincidence of Wants (CoW) cycles in decentralized exchanges (DEXs) using graph theory and linear algebra. The proposed algorithm aims to detect both complete CoW cycles and generate "bridging orders" to complete partial ones, demonstrating its application on a small real-world Arbitrum swap dataset.
This paper introduces a deterministic algorithm for the single-source shortest path (SSSP) problem on directed graphs with non-negative edge weights. The algorithm achieves a time complexity of O(m log^(2/3) n), improving upon Dijkstra's algorithm for sparse graphs. This is the first deterministic algorithm to break the O(m + n log n) time bound in this setting.
This book introduces a theoretical framework for understanding deep neural networks, using tools from theoretical physics. It focuses on analyzing preactivation distributions, the Neural Tangent Kernel (NTK), and the flow of information through networks during training. The book delves into the mathematical principles behind deep learning, including Gaussian integrals, perturbation theory, and renormalization group flow.
The paper introduces a faster deterministic algorithm for the single-source shortest path (SSSP) problem in directed graphs with non-negative edge weights. Using a recursive partitioning technique, the algorithm achieves a time complexity that outperforms Dijkstra's algorithm on sparse graphs. The algorithm assumes constant in-degrees and out-degrees but proposes a transformation for general graphs.
This paper introduces new quantum algorithms for thermal and ground state preparation that are simpler and require fewer resources than existing methods, making them suitable for early fault-tolerant quantum computers. The algorithms are theoretically proven to be efficient for several model systems, including single qubit, free fermionic, and commuting local Hamiltonians. Further research is needed to generalize these results to all quantum systems.
Physics-Informed Neural Networks (PINNs) offer a novel approach to solving partial differential equations by incorporating physical laws into the learning process. While promising for various applications, including fluid dynamics, optics, and material science, PINNs face challenges related to theoretical understanding, computational cost, and accuracy in complex physical phenomena.
This paper proves the existence and weak compactness of solutions for a double-phase implicit obstacle problem with convection and multivalued mixed boundary conditions. The results are established under general assumptions using fixed-point theory, nonsmooth analysis, and variational methods.
This study mapped 332 SARS-CoV-2-human protein interactions, revealing key pathways hijacked by the virus, including translation, vesicle trafficking, and innate immunity. This led to the identification of 69 existing compounds targeting these interactions, with some showing promising antiviral activity in vitro, particularly translation inhibitors and sigma receptor ligands.
The paper describes a new heuristic algorithm for the Traveling Salesman Problem (TSP) with a time complexity of O(n³) that guarantees a solution no worse than 3/2 times the optimal solution when the triangle inequality holds. This represents a 50% improvement over the previous best-known worst-case ratio of 2 for polynomial-time TSP heuristics.
The author argues against the possibility of achieving Artificial General Intelligence (AGI) because computers lack embodiment, lived experience, and the ability to interact with the world like humans. The paper claims that recent advancements in AI, while impressive, are limited to narrow applications (ANI) and do not represent progress towards true general intelligence.
The paper introduces GL-LowPopArt, a two-stage estimator for generalized low-rank trace regression that achieves near instance-wise optimality. It outperforms existing methods by adapting to instance-specific curvature, and a corresponding minimax lower bound confirms its near-optimality.