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.
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 “polynomial programming”
Exact causal network discovery is polynomial for sparse networks.
problem Finding the optimal causal Bayesian network from data is computationally hard.
method Pruning the search space using network properties, combined with dynamic programming and shortest-path searches.
result Exact discovery is polynomial for sparse causal Bayesian networks.
Paper develops exact convex optimization for neural networks with polynomial activations.
problem Training two-layer neural networks with nonlinear polynomial activations.
method Exact convex optimization using semidefinite programming.
result Global optimization of neural networks is polynomial-time computable.
Real-world problems of operations research are typically high-dimensional and combinatorial. Linear programs are generally used to formulate and efficiently solve these large decision problems. However, in multi-period decision problems, we must often compute expected downstream values corresponding to current decision…
We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) in terms of a single convex program with number of variables polynomial in the number of training samples and the number of hidden neurons. Our theory utilizes semi-infinite duality and minimum norm regularization…
Neural networks solve copositive programs, revealing insights into training problems.
problem Training two-layer vector-output ReLU neural networks.
method Convex analysis and copositive programming.
result Neural networks solve copositive programs, providing insights into training problems.
The Slope Conjecture relates a quantum knot invariant, (the degree of the colored Jones polynomial of a knot) with a classical one (boundary slopes of incompressible surfaces in the knot complement). The degree of the colored Jones polynomial can be computed by a suitable (almost tight) state sum and the solution of a …
Polynomial inequalities lie at the heart of many mathematical disciplines. In this paper, we consider the fundamental computational task of automatically searching for proofs of polynomial inequalities. We adopt the framework of semi-algebraic proof systems that manipulate polynomial inequalities via elementary inferen…
We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) a…
EKM solves the K-medoids problem in polynomial time.
problem The -medoids problem in data analysis.
method EKM is a novel algorithm using transformational programming and combinatorial generation.
result EKM solves the -medoids problem in worst-case $O\left(N^{K+1}
ight)$ time complexity.
The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in , where is an matrix such that . In this paper, we show that this method can solve SDPs in polynomial time in a smooth…
We show that for a special alternating link diagram, the following three polynomials are essentially the same: a) the part of the HOMFLY polynomial that corresponds to the leading term in the Alexander polynomial; b) the -vector for a triangulation of the root polytope of the Seifert graph and c) the enumerator of p…
SDP Feasibility Problems and sos Representation Ranks for OT-FKM Type Isoparametric Polynomialsmath.DG
The paper studies SDP feasibility and sos ranks for specific polynomials.
problem Characterizing sos representations of nonnegative polynomials.
method Explicit SDP formulation based on Clifford systems.
result Quantitative rank bounds for sos representations, with rigidity.
Polynomial-time convex optimization for CNNs with ReLU activations.
problem Training Convolutional Neural Networks (CNNs) with ReLU activations.
method Developed a convex analytic framework using semi-infinite duality to formulate equivalent convex optimization problems for CNN architectures.
result Proved that two-layer CNNs can be globally optimized via an norm regularized convex program.
A fast branching algorithm for unknot recognition with experimental polynomial-time behaviourmath.GT
It is a major unsolved problem as to whether unknot recognition - that is, testing whether a given closed loop in R^3 can be untangled to form a plain circle - has a polynomial time algorithm. In practice, trivial knots (which can be untangled) are typically easy to identify using fast simplification techniques, wherea…
This paper shows neural networks can solve complex graph problems efficiently.
problem Solving exact maximum flow computation and minimum spanning tree problems.
method Introduces Max-Affine Arithmetic Programs and shows equivalence to neural networks.
result Two combinatorial optimization problems can be solved with polynomial-size neural networks.
In a polynomial regression model, the divisibility conditions implicit in polynomial hierarchy give way to a natural construction of constraints for the model parameters. We use this principle to derive versions of strong and weak hierarchy and to extend existing work in the literature, which at the moment is only conc…
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.
Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice. A major open question is to explain why this is true. We give a natural condition under which we …
Researchers compute Khovanov polynomials for satellite knots.
problem Computing Khovanov polynomials for satellite knots.
method Explicit computation using a computer program for two families of satellite knots.
result Khovanov polynomials can be expressed as a linear combination of pattern and companion invariants, with a jump at a critical point.
Low-rank approximations of data matrices are an important dimensionality reduction tool in machine learning and regression analysis. We consider the case of categorical variables, where it can be formulated as the problem of finding low-rank approximations to Boolean matrices. In this paper we give what is to the best …
In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear …
A new method calculates HOMFLY-PT polynomials for bipartite links.
problem Computing HOMFLY-PT polynomials for bipartite links efficiently.
method Generalizes Goeritz matrix method for bipartite links.
result Reduces HOMFLY-PT polynomial calculation to matrix algebra.
Optimal experiments tighten causal effect bounds efficiently.
problem Selecting experiments to tighten causal effect bounds from observational data.
method Formalized as max-potency problem, NP-hard. Polynomial-programming framework with graphical pruning criteria.
result Pruning criteria reduce search space significantly, enabling efficient experiment selection.
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…
New method trains quantized neural networks to global optimality.
problem Training optimal quantized neural networks is intractable due to combinatorial non-convex optimization.
method Convex optimization strategy using hidden convexity, semidefinite lifting, and Grothendieck's identity.
result Quantized NN problems can be solved to global optimality in polynomial-time.
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.
LiPopt uses polynomial optimization to estimate neural network Lipschitz constants efficiently.
problem Estimating the Lipschitz constant of neural networks efficiently.
method Sparse polynomial optimization, leveraging network connectivity to reduce complexity.
result Superior estimates of the -Lipschitz constant compared to existing methods.
A new, simple method to compute a knot invariant.
problem Computing a powerful knot invariant efficiently.
method Using a quadratic expression in the entries of the inverse of a standard matrix.
result The method leads to a powerful knot invariant with concise formulas.
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.
New algorithm solves complex stopping problems with robust optimization.
problem Solving complex stochastic optimal stopping problems.
method Simulation-based robust optimization with exact reformulation as a zero-one bilinear program.
result Developed polynomial-time heuristics and algorithms for practical solution.
Witten's conjecture suggests that the polynomial invariants of Donaldson are expressible in terms of the Seiberg-Witten invariants if the underlying four-manifold is of simple type. A higher rank version of the Donaldson invariants was introduced by Kronheimer. Before even having been defined, the physicists Mariño and…
AMP algorithms can be efficiently simulated by SDPs even with corrupted data.
problem Optimizing average-case optimization problems with corrupted data.
method Local statistics hierarchy semidefinite programs (SDPs) simulate AMP algorithms robustly.
result Robust guarantees for many AMP algorithms are offered, contrasting with strong lower bounds for SDPs.
Paper characterizes MDM for consumer choice modeling and prediction.
problem Modeling consumer choice behavior with parsimonious models.
method Establishes necessary and sufficient conditions for MDM consistency.
result Characterization leads to exact set of representable choice probabilities.
Develops new optimization techniques for decision-making under uncertainty.
problem Decision-making under uncertainty with complex cost functions and nested expectations.
method Introduces Multistage Conditional Compositional Optimization (MCCO) and develops multilevel Monte Carlo techniques.
result New optimization techniques reduce scenario complexity from exponential to polynomial growth.
Computing polynomial invariants for knots and links using braid representations relies heavily on finding the trace of Hecke algebra elements. There is no easy method known for computing the trace and hence it becomes difficult to compute the known polynomial invariants of knots using their braid representations. In th…
The paper analyzes tensor recovery from symmetric rank-one measurements using information theory.
problem Recovering tensors with low symmetric rank from symmetric rank-one measurements.
method Covering numbers argument, Carbery-Wright inequality, orthogonal polynomials, Fano's inequality.
result Near-optimal sample complexity bounds for log-concave distributions.
Transformers improve solving mixed-integer programs, especially CLSP.
problem Solving Capacitated Lot Sizing Problem (CLSP) with mixed-integer programming.
method Employing transformer models to predict binary variables in CLSP.
result Transformer model outperforms CPLEX and LSTM in solving CLSP.
Classical knot theory can be generalized to virtual knot theory and spatial graph theory. In 2007, Fleming and Mellor combined virtual knot theory and spatial graph theory to form, combinatorially, virtual spatial graph theory. In this paper, we introduce a topological definition of virtual spatial graphs that is simil…
Convex optimization refines neural network training, improving model performance and reducing hyperparameter sensitivity.
problem Training deep neural networks using non-convex optimization methods often leads to suboptimal solutions and requires extensive tuning.
method Formulate neural network training as convex programs with regularization terms, leveraging sparse recovery models and semi-infinite programming theory.
result Convex models can achieve global optima and outperform traditional non-convex methods, with improved robustness to hyperparameters.
We make a new attempt at the recently suggested program to express knot polynomials through topological vertices, which can be considered as a possible approach to the tangle calculus: we discuss the Macdonald deformation of the relation between the convolution of two topological vertices and the HOMFLY-PT invariant of…
Topological recursion recovers a specific partition function for colored knots.
problem Recovering the extended Ooguri-Vafa partition function for colored HOMFLY-PT polynomials of torus knots.
method Applying topological recursion to the spectral curve of colored HOMFLY-PT polynomials of torus knots.
result Topological recursion reproduces the n-point functions of the extended Ooguri-Vafa partition function.
Extends gradient-based optimization to spline functions.
problem Limitations of standard differentiable programming methods.
method Derives Jacobian of spline functions and uses it in predictive models.
result Improved performance in various applications.
Harer-Zagier formulas generalized to knot matrix models.
problem Understanding knot polynomials through matrix models.
method Defined knot matrix models and extracted averages.
result Harer-Zagier formulas factorize for torus knots but not for others.
This research optimizes Andrews plots for better visual clarity in high-dimensional data.
problem Visualizing high-dimensional datasets with clarity and aesthetics.
method Developed a method to add spectral smoothing to Andrews plots to reduce visual clutter.
result Optimal spatial-spectral smoothing leads to more aesthetically pleasing and clutter-free visualizations.
We consider a fundamental integer programming (IP) model for cost-benefit analysis flood protection through dike building in the Netherlands, due to Verweij and Zwaneveld. Experimental analysis with data for the Ijsselmeer lead to integral optimal solution of the linear programming relaxation of the IP model. This natu…
Polynomial braid combingmath.GT
Braid combing is a procedure defined by Emil Artin to solve the word problem in braid groups for the first time. It is well-known to have exponential complexity. In this paper, we use the theory of straight line programs to give a polynomial algorithm which performs braid combing. This procedure can be applied to braid…
Maximizes determinant of vector sums under matroid constraints.
problem Finding a basis in a matroid that maximizes the determinant of vector sums.
method New approximation algorithm with guarantees depending only on vector dimension.
result Significant improvement in approximation guarantees for various matroids.