A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Fixed-parameter tractability of private synthetic data generation
Many polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of th…
New algorithm speeds up knot polynomial calculations.
To enumerate 3-manifold triangulations with a given property, one typically begins with a set of potential face pairing graphs (also known as dual 1-skeletons), and then attempts to flesh each graph out into full triangulations using an exponential-time enumeration. However, asymptotically most graphs do not result in …
In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth. We prove such a metatheorem for a general class of triangulations of arbitrary fixed dimension d, including all t…
Study on teaching complexity in graphs, proving hardness and tractability.
Optimal Morse matchings reveal essential structures of cell complexes which lead to powerful tools to study discrete geometrical objects, in particular discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds, through a reduction to the erasability problem. Here, we refine the stu…
Study shortest non-separating curves on non-orientable surfaces, proving NP-hardness and tractability.
There are many fundamental algorithmic problems on triangulated 3-manifolds whose complexities are unknown. Here we study the problem of finding a taut angle structure on a 3-manifold triangulation, whose existence has implications for both the geometry and combinatorics of the triangulation. We prove that detecting ta…
Algorithm efficiently learns deep ReLU networks with polynomial runtime in depth and parameters.
We give a general fixed parameter tractable algorithm to compute quantum invariants of links presented by diagrams, whose complexity is singly exponential in the carving-width (or the tree-width) of the diagram. In particular, we get a time algorithm to compute any Resh…
EPMF factorizes matrices by adjusting their entries to match a specified power.
The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterised by an integer . We resolve the question …
Algorithm calculates quantum invariants of 3-manifolds with polynomial time complexity.
Training neural networks is hard in fixed dimensions.
The paper explores algorithms to transform 3-manifold triangulations while controlling sparsity.
In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV(4,q), using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parame…
New algorithm for weighted low rank approximation with provable guarantees.
We define cylinder knots as billiard knots in a cylinder. We present a necessary condition for cylinder knots: after dividing cylinder knots by possible rotational symmetries we obtain ribbon knots. We obtain an upper bound for the number of cylinder knots with two fixed parameters (out of three). In addition we prove …
Complex phenomena in engineering and the sciences are often modeled with computationally intensive feed-forward simulations for which a tractable analytic likelihood does not exist. In these cases, it is sometimes necessary to estimate an approximate likelihood or fit a fast emulator model for efficient statistical inf…
Machine learning software accounts for a significant amount of energy consumed in data centers. These algorithms are usually optimized towards predictive performance, i.e. accuracy, and scalability. This is the case of data stream mining algorithms. Although these algorithms are adaptive to the incoming data, they have…
NPAS trains neural networks with a fixed parameter budget, improving performance and compactness.
Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth of a compact, connected 3-manifold defined by \[ \operatorname{tw}(M) = \min\{\operatorname{tw}(Γ(\mathcal{T})):\mathcal{T}~\text{is a triangulation of }M\}, \] where denotes the dual graph of…
We analyze the (unconditional) distribution of a linear predictor that is constructed after a data-driven model selection step in a linear regression model. First, we derive the exact finite-sample cumulative distribution function (cdf) of the linear predictor, and a simple approximation to this (complicated) cdf. We t…
New method for initializing low-rank neural networks improves performance.
A typical way in which network data is recorded is to measure all the interactions among a specified set of core nodes; this produces a graph containing this core together with a potentially larger set of fringe nodes that have links to the core. Interactions between pairs of nodes in the fringe, however, are not recor…
Every element of PU(2,1) can be decomposed into at most 4 special elliptic isometries.
Algorithm learns means of spherical Gaussian mixtures efficiently in low dimensions.
We show how to find a complete set of necessary and sufficient conditions that solve the fixed-parameter local congruence problem of immersions in -spaces, whether homogeneous or not, provided that a certain order jet bundle over the -space admits a -invariant local coframe field of constant struc…
Unified framework for tractable inference scenarios in machine learning models.
A universal LSTM model outperforms asset-specific models in forecasting stock volatilities.
Recurrent and convolutional neural networks are the most common architectures used for time series forecasting in deep learning literature. These networks use parameter sharing by repeating a set of fixed architectures with fixed parameters over time or space. The result is that the overall architecture is time-invaria…
PNCs balance tractability and expressiveness in probabilistic modeling.
Unified tractability conditions for various compositional inference queries.
Proposes a deep neural network for predicting clustered time-to-event data.
Hybrid model combines continuous and tractable probabilistic models.
New tractable density models from squaring neural networks.
We consider the problem of transforming samples from one continuous source distribution into samples from another target distribution. We demonstrate with optimal transport theory that when the source distribution can be easily sampled from and the target distribution is log-concave, this can be tractably solved with c…
The key idea of Bayesian optimization is replacing an expensive target function with a cheap surrogate model. By selection of an acquisition function for Bayesian optimization, we trade off between exploration and exploitation. The acquisition function typically depends on the mean and the variance of the surrogate mod…
Probabilistic models learned as density estimators can be exploited in representation learning beside being toolboxes used to answer inference queries only. However, how to extract useful representations highly depends on the particular model involved. We argue that tractable inference, i.e. inference that can be compu…
We present a novel tractable generative model that extends Sum-Product Networks (SPNs) and significantly boosts their power. We call it Sum-Product-Quotient Networks (SPQNs), whose core concept is to incorporate conditional distributions into the model by direct computation using quotient nodes, e.g. $P(A|B) = \frac{P(…
TRUST improves structure learning with tractable uncertainty.
Despite widespread interest and practical use, the theoretical properties of random forests are still not well understood. In this paper we contribute to this understanding in two ways. We present a new theoretically tractable variant of random regression forests and prove that our algorithm is consistent. We also prov…
We propose Very Simple Classifier (VSC) a novel method designed to incorporate the concepts of subsampling and locality in the definition of features to be used as the input of a perceptron. The rationale is that locality theoretically guarantees a bound on the generalization error. Each feature in VSC is a max-margin …
We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in polynomial time. The notion of tractability extends the basic case of planar zero-field Ising models…
Investigates optimal parameter allocation in Transformers for efficiency and expressivity.
Paper introduces md-vtrees for efficient probabilistic and causal inference.
Discretizing multi-dimensional data distributions is a fundamental step of modern indexing methods. State-of-the-art techniques learn parameters of quantizers on training data for optimal performance, thus adapting quantizers to the data. In this work, we propose to reverse this paradigm and adapt the data to the quant…