The Sarkar-Wang algorithm computes the hat version of the Heegaard Floer homology of a closed oriented three manifold. This paper analyzes the computational complexity of the Sarkar-Wang algorithm; then the algorithm is modified to obtain a better bound. Then the computational complexity of calculating HFK hat from a H…
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,657 papers · 148 categories
Trend · papers per month
48 results for “algorithmic computation”
Quantum computing techniques improve graph analysis and community detection.
problem Analyzing large graphs efficiently and accurately.
method Used quantum annealing and quantum gate computers for community detection and regularity checking.
result Demonstrated the effectiveness of quantum computing in solving complex graph problems.
Adaptive compute allocation improves model performance by prioritizing harder queries.
problem Inefficiency in allocating test-time compute uniformly across all queries.
method Formulated as a bandit learning problem, proposed adaptive algorithms that estimate query difficulty and allocate compute accordingly.
result Achieved up to 15.29% relative performance improvement on various benchmarks.
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.
Quantum computing offers new solutions for finance problems.
problem Challenging classical computational problems in finance.
method Quantum algorithms for finance applications.
result Potential benefits for financial services.
Numerical challenges inherent in algorithms for computing worst Value-at-Risk in homogeneous portfolios are identified and solutions as well as words of warning concerning their implementation are provided. Furthermore, both conceptual and computational improvements to the Rearrangement Algorithm for approximating wors…
Paper proposes diagnostics for error and variance estimation in randomized matrix computations.
problem Safe use of randomized matrix algorithms in applications.
method Leave-one-out error estimator and jackknife resampling method.
result Provides rapid diagnostics to assess quality of randomized matrix computations.
The aim of this paper is to discuss some applications of general topology in computer algorithms including modeling and simulation, and also in computer graphics and image processing. While the progress in these areas heavily depends on advances in computing hardware, the major intellectual achievements are the algorit…
Quantum computing promises faster bioinformatics, but challenges remain.
problem Efficient bioinformatics processing and drug discovery.
method Quantum algorithms for optimization, simulation, and machine learning.
result Quantum computing can significantly speed up bioinformatics tasks.
Finding the Optimal Currency Composition of Foreign Exchange Reserves with a Quantum Computerecon.GN
Quantum computing aids in optimizing currency reserves for central banks.
problem Optimizing currency composition in foreign exchange reserves.
method Comparison of quantum and classical algorithms for portfolio optimization.
result Quantum algorithms outperform classical methods in currency optimization.
An Efficient Algorithm for Computing Interventional Distributions in Latent Variable Causal Modelscs.LG
Probabilistic inference in graphical models is the task of computing marginal and conditional densities of interest from a factorized representation of a joint probability distribution. Inference algorithms such as variable elimination and belief propagation take advantage of constraints embedded in this factorization …
We present new algorithms to compute the mean of a set of empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We propose two original algorithms to compute Wasse…
Scientific Computing relies on executing computer algorithms coded in some programming languages. Given a particular available hardware, algorithms speed is a crucial factor. There are many scientific computing environments used to code such algorithms. Matlab is one of the most tremendously successful and widespread s…
Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU() Symmetryquant-ph
Enhances quantum computing for symmetrical systems, proving a new class of problems.
problem Proving the efficiency of a new quantum computing model for symmetrical systems.
method Introducing equivariant convolutional quantum algorithms tailored for SU(d) symmetries.
result Demonstrates a problem that can be solved efficiently on a new quantum model, suggesting it's not classically simulatable.
Algorithm computes eigenvalues and eigenforms on Calabi-Yau threefolds.
problem Computing spectra of Laplace-de Rham operator on Calabi-Yau manifolds.
method Numerical algorithm using approximate Calabi-Yau metric.
result Computed eigenvalues and eigenforms for the Fermat quintic threefold.
Algorithm computes knot Floer complex for knots of thickness one.
problem Computing knot Floer complexes for knots of thickness one.
method Developed and implemented an algorithm for knots of thickness one.
result Algorithm can compute full knot Floer complex for knots of thickness one.
Paper develops fast method for computing optimal transport.
problem Efficient computation of optimal transport distance between distributions.
method Entropy-regularized extragradient method for first-order optimization.
result Achieves state-of-the-art runtime guarantees and good numerical performance.
Fast feature selection for SHM using canonical correlation.
problem Feature selection for structural health monitoring.
method Greedy search of sum of squared canonical correlation coefficients.
result Extremely fast feature selection with good performance.
Fatgraphs are multigraphs enriched with a cyclic order of the edges incident to a vertex. This paper presents algorithms to: (1) generate the set of all fatgraphs having a given genus and number of boundary cycles; (2) compute automorphisms of any given fatgraph; (3) compute the homology of the fatgraph complex. The al…
Parallel algorithm speeds up Jones polynomial computation.
problem Efficient computation of knot complexity measures.
method First parallel algorithm for exact Jones polynomial computation.
result Reduces computational time by an exponential factor.
AI progress measured by reduced compute needed to reach past performance.
problem Quantifying algorithmic progress in AI.
method Analysis of floating-point operations required to train neural networks.
result Algorithmic efficiency doubled every 16 months over 7 years.
Stable Torsion Lengthmath.GR
Study on stable torsion length in groups, showing it vanishes in crystallographic groups and providing algorithms for computation.
problem Understanding the stable torsion length in groups, especially in crystallographic and free products of groups.
method Developed linear programming and exact algorithms to compute stable torsion length in free products of groups and finite groups.
result Showed that stable torsion length vanishes in crystallographic groups and provided exact computations for nontrivial examples.
In this paper, we give an algorithm to compute the hat version of the Heegaard Floer homology of a closed oriented three-manifold. This method also allows us to compute the filtrations coming from a null-homologous link in a three-manifold.
A new algorithm computes Fourier coefficients for a specified range efficiently.
problem Inefficiency in FFT due to fixed output size for all applications.
method Fast Partial Fourier Transform (PFT) that allows specifying the range of Fourier coefficients to compute.
result PFT achieves significant speedup over state-of-the-art FFT algorithms for small output sizes.
Matrix profile has been recently proposed as a promising technique to the problem of all-pairs-similarity search on time series. Efficient algorithms have been proposed for computing it, e.g., STAMP, STOMP and SCRIMP++. All these algorithms use the z-normalized Euclidean distance to measure the distance between subsequ…
We consider the weakly supervised binary classification problem where the labels are randomly flipped with probability . Although there exist numerous algorithms for this problem, it remains theoretically unexplored how the statistical accuracies and computational efficiency of these algorithms depend on the degr…
In this paper, we propose new efficient algorithms to verify the null space condition in compressed sensing (CS). Given an () CS matrix and a positive , we are interested in computing , where …
Fixed-parameter tractable computation of Reshetikhin--Turaev knot polynomials via tensor networksmath.GT
New algorithm speeds up knot polynomial calculations.
problem Computing Reshetikhin--Turaev knot polynomials efficiently.
method Fixed-parameter tractable computation via tensor networks.
result Knot polynomial computations are fixed-parameter tractable.
The crosscap number of a knot is an invariant describing the non-orientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varyi…
Efficient WKNN-Shapley computation improves data valuation accuracy.
problem Efficient computation of Data Shapley for WKNN algorithm.
method Reframed WKNN-Shapley as a counting problem, introduced quadratic-time algorithm.
result Quadratic-time WKNN-Shapley computation, improving from .
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…
Bayesian Optimal Control of Smoothly Parameterized Systems: The Lazy Posterior Sampling Algorithmcs.LG
We study Bayesian optimal control of a general class of smoothly parameterized Markov decision problems. Since computing the optimal control is computationally expensive, we design an algorithm that trades off performance for computational efficiency. The algorithm is a lazy posterior sampling method that maintains a d…
Algorithms compute invariants of 4-manifolds as branched covers.
problem Computing invariants of 4-manifolds as branched covers.
method Diagrammatic algorithms using tri-plane diagrams and permutations.
result Automated algorithm for computing Kjuchukova's homotopy-ribbon obstruction.
An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute the Word Mover's Distancecs.LG
This paper speeds up WMD computation for multiple queries efficiently.
problem Efficiently computing the semantic dissimilarity between text documents.
method Adapting the Sinkhorn-Knopp algorithm to compute WMD of one document against many targets in parallel.
result 67x speedup on 96 cores compared to sequential and naive parallel methods.
Improved first-order algorithm for entropy regularized OT with faster convergence.
problem Solving entropy regularized optimal transport efficiently.
method Accelerated primal-dual stochastic mirror descent algorithm with variance reduction.
result Improved rate from to .
Nonparametric correlations such as Spearman's rank correlation and Kendall's tau correlation are widely applied in scientific and engineering fields. This paper investigates the problem of computing nonparametric correlations on the fly for streaming data. Standard batch algorithms are generally too slow to handle real…
Quantum computing promises faster finance algorithms.
problem Solving finance problems faster than classical methods.
method Quantum computing applications to finance, including Monte Carlo, portfolio optimization, and machine learning.
result Quantum speedups for finance problems, especially Monte Carlo and portfolio optimization.
Two new algorithms reduce online kernel regression's computational cost while maintaining optimal regret bounds.
problem Trade-off between regret and computational cost in online kernel regression.
method AOGD-ALD and NONS-ALD algorithms dynamically maintain nearly orthogonal basis to approximate kernel mapping and control approximate error.
result Achieves nearly optimal regret bounds at sublinear computational complexity.
We provide a proof of backpropagation algorithm in matrix notation.
problem The lack of a full induction proof of backpropagation algorithm in matrix notation.
method We provide a full induction proof of the BP algorithm in matrix notation, situating it in the framework of matrix differential calculus.
result We prove the validity of the backpropagation algorithm in inductive form.
Modified BA algorithm computes RD and DR functions efficiently.
problem Computing rate-distortion and distortion-rate functions.
method A novel modification of the BA algorithm using Newton's method for root-finding.
result The modified algorithm converges to RD and DR function solutions with rate and provides -approximations.
Linear time dynamic programming for the exact path of optimal models selected from a finite setcs.LG
New algorithm speeds up path computation for optimal models.
problem Finding the exact path of optimal models from a finite set.
method Dynamic programming approach for linear time computation.
result Dynamic programming achieves linear time for breakpoints computation.
Nonnegative matrix factorization (NMF) is a powerful tool for data mining. However, the emergence of `big data' has severely challenged our ability to compute this fundamental decomposition using deterministic algorithms. This paper presents a randomized hierarchical alternating least squares (HALS) algorithm to comput…
Improved bounds for proximal gradient algorithms with computational errors.
problem Analyzing convergence of proximal gradient algorithms with inaccuracies.
method Deriving new tighter deterministic and probabilistic bounds for convex composite problems.
result Probabilistic bounds are more robust and accurate for algorithm verification and performance guarantees.
Quadratic-time algorithm computes stretch factors and foliations for pseudo-Anosov mapping classes.
problem Computing stretch factors and foliations for pseudo-Anosov mapping classes efficiently.
method Quadratic-time algorithm using input word and length as complexity measure.
result First algorithm to compute stretch factors and foliations in sub-exponential time.
Fast algorithm for braid group Hecke representation, applied to knot invariants.
problem Computing topological invariants of knots efficiently.
method Representation-theoretic approach to braid group, leveraging quantum topology.
result Fast algorithm for Hecke representation of braid group, finding non-trivial braids.
Computing the Hopf invariantmath.CO
Algorithm calculates Hopf invariant for simplicial mappings.
problem Computing Hopf invariant for simplicial mappings.
method Proposed an algorithm based on Whitehead's integral formula.
result Algorithm successfully computes Hopf invariant.
Quantum Bayesian Computationstat.ML
QBC uses quantum computers to speed up Bayesian computation.
problem Exponential speed-up in Bayesian computation.
method Quantum von Neumann measurement for simulating ML algorithms.
result Quantum versions of regression, Gaussian processes, and SGD.
New MBQC algorithm uses randomness for generative modeling.
problem Designing efficient quantum algorithms for generative modeling.
method Proposes a variational MBQC algorithm that treats randomness as a resource.
result Randomness in MBQC can lead to significant gains in generative modeling performance.