Efficient method for computing twisted Alexander polynomials of Montesinos links.
problem Computing twisted Alexander polynomials for Montesinos links efficiently.
method Developed an efficient method to compute the twisted Alexander polynomial for Montesinos links using any linear representation.
result Formulas for multi-variable Alexander polynomials can be easily derived.
Efficient algorithm computes colored Jones polynomial of knots.
problem Computing the colored Jones polynomial efficiently for knots.
method Walk model of the colored Jones polynomial, utilizing q-Weyl algebra.
result Our algorithm runs faster than existing methods by an order of magnitude.
Study on periodic knots, proving limitations on their Alexander polynomials.
problem Understanding Alexander polynomials of periodic knots.
method Polynomial factorization, number theory interpretation, computational methods.
result Alexander polynomials of freely periodic knots are restricted to products of cyclotomic polynomials.
Unified view and efficient algorithms for polynomial networks and factorization machines.
problem Efficiently using feature interactions in classification and regression tasks.
method Unified perspective, low-rank symmetric tensor estimation, multi-convex optimization.
result New efficient training algorithms for polynomial networks and factorization machines.
New algorithm reliably learns ReLU functions efficiently.
problem Learning ReLU functions in the Reliable Agnostic model.
method Combines kernel methods, polynomial approximations, and dual-loss approach.
result First efficient algorithms for reliable learning of ReLU functions.
Efficiently samples arbitrary compact bodies with polynomial complexity.
problem Uniform sampling from arbitrary compact bodies efficiently.
method Warm start algorithm under isoperimetry and volume growth condition.
result Substantial generalization of known results for convex and star-shaped bodies.
Paper computes Alexander polynomials for arborescent links.
problem Explicit formulas for Alexander polynomials are hard to compute for most link families.
method Efficient method for arborescent links, using recursive polynomials.
result Explicit closed formulas for pretzel links derived.
Kernel methods can learn hierarchical polynomials efficiently.
problem Learning hierarchical structure from data.
method Iteratively reweighting kernel machines using derivatives.
result Efficient learning of hierarchical polynomials.
Shallow neural networks can represent polynomials efficiently.
problem Representing polynomials using shallow neural networks.
method Using shallow neural networks of width 2(R+d)d to represent d-variate polynomials of degree R. result Derives minimax optimal convergence rate for shallow networks to unknown univariate regression functions.
The study reveals the efficiency of sampling from tilted distributions.
problem Sampling from a tilted distribution of an unknown underlying distribution.
method Self-normalized importance sampling to characterize accuracy.
result Polynomial vs super-polynomial sample complexity for bounded vs unbounded distributions.
New algorithm learns ReLU networks efficiently using Schur polynomials.
problem PAC learning a linear combination of ReLU activations under Gaussian distribution.
method Uses tensor decomposition and Schur polynomials to identify and analyze higher-order moments.
result Near-optimal sample and computational complexity for learning ReLU networks.
FPC tackles big data challenges with polynomial kernels and ADMM.
problem Efficiently classify massive data with scalability and storage challenges.
method Polynomial feature mapping and ADMM for non-smooth convex optimization.
result FPC significantly reduces computational burden and storage memory without sacrificing generalization ability.
SURF simplifies distribution estimation with simple, robust, and fast algorithms.
problem Efficient and accurate distribution estimation in statistics and machine learning.
method Piecewise polynomial approximation using empirical probability interpolation and divide-and-conquer merging.
result Surpassing state-of-the-art algorithms in efficiency and accuracy, SURF estimates distributions robustly and quickly.
Score matching offers efficient estimation for certain distributions.
problem Estimating probability distributions with intractable constants.
method Score matching as an alternative to maximum likelihood.
result Score matching is computationally and statistically efficient for certain distributions.
Algorithm samples from Bingham distribution efficiently.
problem Sampling from the Bingham distribution on a sphere.
method Rejection sampling with polynomial approximation.
result Exact samples from Bingham distribution in polynomial time.
Efficiently estimates binary product distributions with privacy.
problem Estimating means of binary product distributions privately and accurately.
method Polynomial time, pure differential privacy approach.
result Optimal sample complexity with polylogarithmic factors.
Study robust algorithms for deep networks under adversarial perturbations.
problem Designing robust deep networks to adversarial attacks.
method Connecting robustness to polynomial optimization, designing efficient algorithms.
result Provable robustness for linear classifiers and PTFs, characterizing robustness price, efficient certification.
New q-deformed integers help compute Jones polynomials efficiently.
problem Computing Jones polynomials of rational links efficiently.
method Defining q-deformed integers from pairs of coprime integers and using them to compute Jones polynomials.
result Efficient algorithm for computing Jones polynomials of rational links.
New algorithm learns PTFs with noisy data efficiently.
problem Learning low-degree PTFs with noisy data efficiently.
method Structural result and novel robust Chow vector estimation.
result PAC learns PTFs with nasty noise using efficient samples.
Polynomial-time algorithm for optimal stopping with fixed accuracy.
problem High-dimensional path-dependent optimal stopping problems.
method Efficient simulator of underlying information process, polynomial-time algorithm based on novel expansion.
result Polynomial-time solution for epsilon-optimal stopping policies and values.
Extends factorization machines and polynomial networks to multi-output problems.
problem Learning vector-valued functions for multi-class or multi-task problems.
method Convex formulation of a 3-way tensor with a conditional gradient algorithm.
result Achieves excellent accuracy with sparser models than existing methods.
Efficiently learns Gaussian parameters robust to adversarial noise.
problem Learning Gaussian parameters in the presence of adversarial noise.
method Robust estimators achieving optimal error in total variation distance.
result Optimal error guarantees O(ε) in total variation distance. This study extends verifiable learning to boosted tree ensembles, enabling efficient security verification.
problem Efficiently verifying the robustness of boosted tree ensembles against norm-based attackers.
method Formal verification of robustness for large-spread boosted tree ensembles, considering L∞-norm and pseudo-polynomial time for Lp-norm verification. result Polynomial time verification for L∞-norm attackers, NP-hard for other norms, and pseudo-polynomial time for Lp-norm verification. Polynomial expansions improve option pricing accuracy.
problem Efficiently pricing and Greeks in stochastic volatility models.
method Analytic series representations for European and exotic options.
result Polynomial expansions match Fourier transform accuracy.
Efficient algorithm for sampling from arbitrary compact bodies.
problem Sampling from arbitrary compact bodies efficiently.
method Warm start algorithm with polynomial complexity.
result Substantial generalization of known results for convex and star-shaped bodies.
Jones polynomials for knots and links with many crossings calculated efficiently.
problem Computing Jones polynomials for knots and links with a large number of crossings.
method Calculating Tutte polynomials for associated graphs and evaluating with specific substitutions.
result Jones polynomials for knots and links with many crossings calculated efficiently.
New formulas derived for lattice crossing coefficients, improving computation efficiency.
problem Computing coefficients of Catalan states in lattice crossings.
method Using plucking polynomial and Θ_A-state expansion, deriving new properties and formulas.
result Coefficients of Catalan states factor under specific conditions, leading to more efficient computation.
A new method builds sparse polynomial chaos expansions for models with dependent inputs.
problem Quantifying uncertainty in models with dependent inputs.
method Data-driven approach to construct orthonormal polynomials recursively based on input correlations.
result Reduces the number of observations and improves numerical stability and computational efficiency.
Sparse Polynomial Chaos expansions improve accuracy and efficiency in simulations.
problem Challenges in computational efficiency and accuracy for Polynomial Chaos modeling.
method Sparse Bayesian learning using Variational Relevance Vector Machines.
result Sparse Polynomial Chaos expansions achieve comparable performance to compressive sensing with fewer data points.
Abstract reviews algorithms for multi-index models, focusing on polynomial-time methods and their limitations.
problem Estimating the index space in multi-index models efficiently and accurately.
method Polynomial-time algorithms in Gaussian space, nonparametric gradient estimation, and neural network fitting.
result A gap exists between computationally efficient methods and information-theoretical minimum.
Study active learning of PTFs with derivative access.
problem Active learning of polynomial threshold functions (PTFs).
method Algorithm for active learning degree-d univariate PTFs with derivative access. result Computational efficient algorithm for active learning degree-d univariate PTFs. We introduce a new activation function using Chebyshev-Lagrange polynomials for improved neural network performance.
problem Improving data efficiency and accuracy of neural networks.
method Parameterized piece-wise polynomial activation functions based on Chebyshev nodes and Lagrangian interpolation.
result Significant improvements in model capacity and accuracy, especially in linear extrapolation.
Accelerates nonparametric estimation to near-linear time.
problem Quadratic time complexity in local polynomial regression.
method Novel use of binary indexed trees for multi-dimensional data.
result Near-linear time complexity in computation.
Polynomial sketch approximates functions of low-rank matrices efficiently.
problem Approximating element-wise functions of low-rank matrices without full access.
method Combining polynomial approximation and tensor sketch for monomials.
result Efficient algorithm with lower complexity than full matrix access.
New method efficiently interpolates nonparametric density estimators.
problem Efficient evaluation of nonparametric density estimators.
method Piecewise multivariate polynomial interpolation scheme.
result New estimator with low space requirements and efficient querying.
Algorithm simplifies triangulations near curves efficiently.
problem Efficiently simplifying triangulations near given curves.
method Uses flips and powers of Dehn twists in polynomial time.
result Algorithm completes in polynomial time based on curve size.
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…
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.
Polynomial-time Gibbs sampling generates DPP samples efficiently.
problem Sampling from continuous Determinantal Point Processes (DPPs).
method Polynomial-time Gibbs sampling algorithm.
result Gibbs sampler generates DPP samples in polynomial time.
Enhanced PC2 improves surrogate modeling for high-dimensional problems.
problem Degrading performance and efficiency of PC2 in high-dimensional parameter spaces. method Integrates SULM solver and D-optimal sampling strategy into PC2 framework. result Enhanced PC2 demonstrates better comprehensive capability and efficiency. Polynomial-time algorithm learns MAP perturbation models for structured prediction.
problem Efficiently learning parameters for robust structured prediction models.
method Minimizes Rademacher-based generalization bound to learn parameters in polynomial time.
result Guaranteed generalization to unseen examples under certain conditions.
We show that the class of strongly connected graphical models with treewidth at most k can be properly efficiently PAC-learnt with respect to the Kullback-Leibler Divergence. Previous approaches to this problem, such as those of Chow ([1]), and Ho gen ([7]) have shown that this class is PAC-learnable by reducing it to …
FNOs learn solution operators of dissipative equations efficiently via spectral methods.
problem Learning and approximation of solution operators for dissipative equations.
method Introducing spectral methods and deriving FNO approximation bounds and sample complexity guarantees.
result Polynomial sample complexity guarantees for FNOs learning solution operators of dissipative equations.
A new method minimizes experimental design regret for various optimality criteria.
problem Optimizing experimental design points for statistical efficiency.
method Regret minimization framework for polynomial-time approximation.
result Achieves (1+ε) approximation with O(p/ε2) design points. New algorithms for efficient inference and sampling in complex Ising models.
problem Efficiently computing partition functions and sampling configurations for complex Ising models.
method Equivalent linear transition to perfect matching counting and sampling on an expanded dual graph.
result Polynomial-time inference and sampling algorithms for K33-free topologies. Polynomial-time algorithm for homotoping arcs or curves into efficient position.
problem Finding efficient position for arcs or curves on surfaces.
method Polynomial-time algorithm using local homotopies.
result Polynomial-time efficient position achieved for surfaces of positive complexity.
Efficiently estimate Gaussian copulas' tail expectations using novel estimators.
problem Estimating expectations over constrained sets in Gaussian copulas' tails.
method Proposes three estimators based on identifying dominating points and scaling exponential distributions.
result Developed estimators achieve bounded relative error in Gaussian settings and polynomial efficiency in NORTA settings.
New algorithm learns halfspaces with noise using Forster decomposition.
problem Learning halfspaces in noisy data.
method Forster decomposition and efficient mixture of distributions.
result First polynomial-time algorithm with strongly polynomial sample complexity.