Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe HOMFLY-PT polynomial is fixed-parameter tractable
76
0
0.0
(
0
)
Added by
Benjamin Burton
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Benjamin A. Burton
Ask ChatGPT about the research
No Arabic abstract
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 the more powerful HOMFLY-PT polynomial remained an open problem. Here we show that computing HOMFLY-PT is fixed-parameter tractable in the treewidth, and we give the first sub-exponential time algorithm to compute it for arbitrary links.
rate research
Read More
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 any 3-manifold triangulation, which leads to significant wasted time in topological enumeration algorithms. Here we give a new algorithm to determine whether a given face pairing graph supports any 3-manifold triangulation, and show this to be fixed parameter tractable in the treewidth of the graph. We extend this result to a meta-theorem by defining a broad class of properties of triangulations, each with a corresponding fixed parameter tractable existence algorithm. We explicitly implement this algorithm in the most generic setting, and we identify heuristics that in practice are seen to mitigate the large constants that so often occur in parameterised complexity, highlighting the practicality of our techniques.
We consider the problem of learning an unknown ReLU network with respect to Gaussian inputs and obtain the first nontrivial results for networks of depth more than two. We give an algorithm whose running time is a fixed polynomial in the ambient dimension and some (exponentially large) function of only the networks parameters. Our bounds depend on the number of hidden units, depth, spectral norm of the weight matrices, and Lipschitz constant of the overall network (we show that some dependence on the Lipschitz constant is necessary). We also give a bound that is doubly exponential in the size of the network but is independent of spectral norm. These results provably cannot be obtained using gradient-based methods and give the first example of a class of efficiently learnable neural networks that gradient descent will fail to learn. In contrast, prior work for learning networks of depth three or higher requires exponential time in the ambient dimension, even when the above parameters are bounded by a constant. Additionally, all prior work for the depth-two case requires well-conditioned weights and/or positive coefficients to obtain efficient run-times. Our algorithm does not require these assumptions. Our main technical tool is a type of filtered PCA that can be used to iteratively recover an approximate basis for the subspace spanned by the hidden units in the first layer. Our analysis leverages new structural results on lattice polynomials from tropical geometry.
The main goal is to find the Homfly polynomial of a link formed by decorating each component of the Hopf link with the closure of a directly oriented tangle. Such decorations are spanned in the Homfly skein of the annulus by elements Q_lambda, depending on partitions lambda. We show how to find the 2-variable Homfly invariant <lambda,mu> of the Hopf link arising from decorations Q_lambda and Q_mu in terms of the Schur symmetric function s_mu of an explicit power series depending on lambda. We show also that the quantum invariant of the Hopf link coloured by irreducible sl(N)_q modules V_lambda and V_mu, which is a 1-variable specialisation of <lambda,mu>, can be expressed in terms of an N x N minor of the Vandermonde matrix (q^{ij}).
For a positive braid link, a link represented as a closed positive braids, we determine the first few coefficients of its HOMFLY polynomial in terms of geometric invariants such as, the maximum euler characteristics, the number of split factors, and the number of prime factors. Our results give improvements of known results for Conway and Jones polynomial of positive braid links. In Appendix, we present a simpler proof of theorem of Cromwell, a positive braid diagram represent composite link if and only if the the diagram is composite.
It is known that testing isomorphism of chordal graphs is as hard as the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a tree. The leafage of a chordal graph, is defined to be the minimum number of leaves in the representing tree. We construct a fixed-parameter tractable algorithm testing isomorphism of chordal graphs with bounded leafage. The key point is a fixed-parameter tractable algorithm finding the automorphism group of a colored order-3 hypergraph with bounded sizes of color classes of vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
