This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002),…
On-device research index
arXiv research
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “polynomial-time computation”
Investigates polynomial time algorithms for computing Khovanov homology of braids.
problem Computing Khovanov homology for general braids is intractable.
method Examines polynomial time algorithms for 3-braids and a variation of the scanning algorithm for more general braids.
result Shows that for 3-braids, Khovanov homology can be computed in polynomial time, while for more general braids, it can be computed in polynomial time for bounded homological degrees.
We describe a polynomial-time algorithm to compute a (tight) geodesic between two curves in the curve graph. As well as enabling us to compute the distance between a pair of curves, this has several applications to mapping classes. For example, we can use these geodesics to compute the asymptotic translation length, Ni…
We present the strongest known knot invariant that can be computed effectively (in polynomial time).
Polynomial-time method solves complex combinatorial semi-bandits.
problem Optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards.
method Proposes a polynomial-time method to solve the Graves-Lai optimization problem for various combinatorial structures.
result First known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
Paper finds efficient algorithms for computing fixed points in financial networks.
problem Computing fixed points in complex financial networks with potential defaults.
method Tarski's theorem and polynomial-time algorithms for minimal and maximal fixed points.
result Efficient algorithms for computing minimal and maximal fixed points in financial networks.
Strongly polynomial algorithm for approximate Forster transforms and halfspace learning.
problem Computing approximate Forster transforms and halfspace learning.
method Strongly polynomial time algorithm for approximate Forster transforms and halfspace learning.
result First strongly polynomial time algorithm for distribution-free PAC learning of halfspaces.
Polynomial-time reachability for LTI systems with TLL NN controllers is achieved.
problem Bounding the reachable set of LTI systems controlled by TLL NN controllers.
method Polynomial-time computation of exact one-step reachable set and tight bounding box via two methods.
result Exact reachability computation in polynomial time for TLL NN controllers.
Algorithm classifies surface homeomorphisms with polynomial time complexity.
problem Classifying surface homeomorphisms with polynomial time complexity.
method Algorithm to compute curve distances and decide Nielsen-Thurston types.
result Polynomial time classification of surface homeomorphisms.
Low-degree method fails to predict robust subspace recovery problem.
problem Predicting computational tractability of robust subspace recovery problem.
method Low-degree polynomial framework, anti-concentration properties.
result Low-degree method fails to predict computational tractability of robust subspace recovery problem even up to high degree.
New algorithms explain Naive Bayes classifiers in polynomial time and delay.
problem Computing explanations for Naive Bayes classifiers efficiently.
method Developed log-linear time and polynomial delay algorithms for PI-explanations.
result Efficiently computed PI-explanations for linear classifiers.
MAP perturbation models have emerged as a powerful framework for inference in structured prediction. Such models provide a way to efficiently sample from the Gibbs distribution and facilitate predictions that are robust to random noise. In this paper, we propose a provably polynomial time randomized algorithm for learn…
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…
Polynomial-time algorithm finds short non-orientable loops intersecting graph edges up to 30 times.
problem Finding short non-orientable loops intersecting graph edges efficiently.
method Combining computational biology techniques with recent graph theory results.
result Existence of short canonical non-orientable systems of loops.
Paper extends Cohen's method to compute Jones polynomial for certain braid subfamilies.
problem Computing Jones polynomial for specific knot families.
method Using weighted adjacency matrices and determinants for certain subfamilies of braid groups.
result Jones polynomial can be computed in polynomial time for certain subfamilies of braid groups.
Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
problem Clustering d-dimensional Gaussian mixtures with unknown covariance.
method Lattice-based methods using Lenstra--Lenstra--Lovasz reduction.
result Achieves statistically-optimal sample complexity of d+1 samples.
The problem of high-dimensional path-dependent optimal stopping (OS) is important to multiple academic communities and applications. Modern OS tasks often have a large number of decision epochs, and complicated non-Markovian dynamics, making them especially challenging. Standard approaches, often relying on ADP, dualit…
Efficient algorithm for identifying causal effects in linear models.
problem Determining causal effects from observational data under latent confounding.
method Symbolic computation and efficient algorithm for finding identifying formulas.
result Proves the existence of identifying formulas of a specified degree in quasi-polynomial time.
Paper proposes efficient SHAP computation methods.
problem Efficient computation of SHAP values for machine learning models.
method Develops polynomial time methods for SHAP computation based on model structure.
result Exact SHAP computation in polynomial time for various model structures.
We show that if a closed, oriented 3-manifold M is promised to be homeomorphic to a lens space L(n,k) with n and k unknown, then we can compute both n and k in polynomial time in the size of the triangulation of M. The tricky part is the parameter k. The idea of the algorithm is to calculate Reidemeister torsion using …
Statistical-computational gap found in aligning multiple Gaussian graphs.
problem Aligning multiple Gaussian graphs with unknown signals.
method Generalized informational threshold and computational barrier analysis.
result Existence of a statistical-computational gap in multiple Gaussian graph alignment.
The Gromov-Hausdorff distance provides a metric on the set of isometry classes of compact metric spaces. Unfortunately, computing this metric directly is believed to be computationally intractable. Motivated by applications in shape matching and point-cloud comparison, we study a semidefinite programming relaxation of …
The aim of this short note is to draw attention to a method by which the partition function and marginal probabilities for a certain class of random fields on complete graphs can be computed in polynomial time. This class includes Ising models with homogeneous pairwise potentials but arbitrary (inhomogeneous) unary pot…
We find polynomial-time solutions to the word problem for free-by-cyclic groups, the word problem for automorphism groups of free groups, and the membership problem for the handlebody subgroup of the mapping class group. All of these results follow from observing that automorphisms of the free group strongly resemble s…
Quantum machine learning offers advantages for broader learning tasks.
problem Demonstrate QML advantage over classical methods for general learning tasks.
method Construct a new family of supervised learning tasks and prove their hardness.
result Prove provable advantage of QML based on general quantum computational advantages.
New quantum invariants for planar knotoids improve knot classification.
problem Classifying and distinguishing planar knotoids with up to five crossings.
method Define biframed planar knotoids and construct new invariants.
result Improved classification of planar knotoids with up to five crossings.
Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithmsmath.ST
New algorithm optimizes matrix reordering for noisy disordered matrices.
problem Optimizing matrix reordering for noisy disordered matrices in single-cell biology and metagenomics.
method Proposed a polynomial-time adaptive sorting algorithm to improve upon spectral seriation.
result Our algorithm achieves superior performance compared to existing methods in real datasets.
TQFT invariants are either easy or hard to compute, depending on the TQFT type.
problem Computing TQFT invariants on closed 3-manifolds.
method Application of a dichotomy result for weighted constraint satisfaction problems over C.
result TQFT invariants are either solvable in polynomial time or -hard.
Efficient algorithms for WRT invariants of torus bundles using algebraic structures.
problem Computing topological invariants of 3-manifolds is generally intractable.
method Embedding skein algebra into symmetric subalgebra at roots of unity for polynomial-time classical computation and using quantum algorithms for exponential space advantage.
result Polynomial-time classical computation and quantum algorithms for WRT invariants of torus bundles.
We study computational and sample complexity of parameter and structure learning in graphical models. Our main result shows that the class of factor graphs with bounded factor size and bounded connectivity can be learned in polynomial time and polynomial number of samples, assuming that the data is generated by a netwo…
Unified framework for geometric computation of minimum-area homotopy.
problem Computing the minimum homotopy area of a closed curve.
method Unified combinatorial word approach combining geometric and algebraic methods.
result Unified geometric proof and constructive algorithm for minimum area homotopy.
Optimal transport is #P-hard when components are independent, even with approximate solutions.
problem Computational complexity of optimal transport with independent marginals.
method Proved #P-hardness and developed a pseudo-polynomial time approximation algorithm.
result Optimal transport is #P-hard even with independent components and approximate solutions.
Q-SHAP efficiently calculates feature contributions in boosting trees.
problem Global evaluation of feature contributions in tree models.
method Q-SHAP, an efficient algorithm that reduces Shapley values calculation to polynomial time.
result Q-SHAP improves computational efficiency and enhances accuracy of feature-specific estimates.
In recent years, sparse principal component analysis has emerged as an extremely popular dimension reduction technique for high-dimensional data. The theoretical challenge, in the simplest case, is to estimate the leading eigenvector of a population covariance matrix under the assumption that this eigenvector is sparse…
Algorithms compute length spectra of torus graphs efficiently.
problem Computing length spectra of graphs embedded on a torus.
method Preprocessing and algorithms based on polyhedral norms.
result Efficient computation of length spectra and spectrum comparison.
New insights into Khovanov homology complexity and topological structure.
problem Complexity of computing Khovanov homology for closed braids.
method Analysis of independence simplicial complexes and polynomial time algorithms.
result Independence simplicial complexes associated to 4-braid diagrams are homotopy equivalent to wedges of spheres.
Algorithm finds Dirichlet domains for hyperbolic surfaces.
problem Computing explicit Dirichlet domains for hyperbolic surfaces.
method Algorithm based on side pairings of fundamental polygons, using geometric-topological data structures.
result Algorithm runs in polynomial time, dependent on surface perimeter and genus.
A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcs.DS
Polynomial time algorithm matches correlated Gaussian matrices without vanishing correlation.
problem Matching vertices in two correlated Erdős-Rényi graphs.
method Iterative matching algorithm for correlated Gaussian Wigner matrices.
result First polynomial time algorithm for graph matching with arbitrarily small constant correlation.
We describe the polynomial time complexity algorithm for computing first coefficients of the skein (Homflypt) and Kauffman polynomial invariants of links, discovered by D.Vertigan in 1992 but never published.
Hard to approximate critical points for simple nonconvex functions.
problem Approximating critical points of nonconvex functions.
method Proving hardness results for polynomial-time approximation of critical points.
result Proving that approximating critical points is intractable for simple nonconvex functions.
I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "progr…
Algorithm calculates quantum invariants of 3-manifolds with polynomial time complexity.
problem Computing quantum invariants from Tambara-Yamagami categories is #P-hard.
method Fixed-parameter tractable algorithm with first Betti number as parameter.
result Existence of FPT algorithm for Tambara-Yamagami invariants.
We describe a new algorithm to compute the geometric intersection number between two curves, given as edge vectors on an ideal triangulation. Most importantly, this algorithm runs in polynomial time in the bit-size of the two edge vectors. In its simplest instances, this algorithm works by finding the minimal position …
Estimating symmetric properties of a distribution, e.g. support size, coverage, entropy, distance to uniformity, are among the most fundamental problems in algorithmic statistics. While each of these properties have been studied extensively and separate optimal estimators are known for each, in striking recent work, Ac…
We show that the existence of a computationally efficient calibration algorithm, with a low weak calibration rate, would imply the existence of an efficient algorithm for computing approximate Nash equilibria - thus implying the unlikely conclusion that every problem in PPAD is solvable in polynomial time.
Complexity of counting group homomorphisms depends on group structure and presentation.
problem Computing the number of homomorphisms from a group to another.
method Obstruction theory and polynomial time algorithms for specific cases.
result Efficient algorithms for counting homomorphisms under certain conditions.
Study disproves conjecture about low-degree polynomials in hypothesis testing.
problem Conjecture about limitations of polynomial-time algorithms in hypothesis testing.
method Used counterexamples to refute the conjecture and modified the conjecture to rule out the counterexample.
result Disproved conjecture about limitations of low-degree polynomials in hypothesis testing.
Paper improves likelihood estimation for discrete distributions.
problem Computing profile maximum likelihood for discrete distributions.
method New bounds on Bethe and Sinkhorn permanents for low rank matrices.
result Achieves an approximation factor of exp(-O(sqrt(n) log n)) in polynomial time.