arXiv research

Proves NP and co-NP status for knot core recognition in solid torus.

Develops algorithms for multi-class Neyman-Pearson classification with cost sensitivity.

For a fixed marked surface $S$, we construct polynomial bounds on the periodic and preperiodic lengths of the maximal splitting sequences of a projectively invariant measured train track. We give two consequences of these bounds. Firstly, that the problem of deciding whether a mapping class is pseudo-Anosov lies in $\t…

Deciding 3-manifolds fibering over the circle is in NP

Moving between 3-manifold triangulations is NP-hard

Classical knot recognition problem solved in NP with exponential time algorithm.

We show that the problem of determining whether a knot in the 3-sphere is non-trivial lies in NP. This is a consequence of the following more general result. The problem of determining whether the Thurston norm of a second homology class in a compact orientable 3-manifold is equal to a given integer is in NP. As a coro…

We show that {\sc Heegaard Genus $\leq g$}, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to $g$, is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem {\sc CNF-SAT} to {\sc Heegaard Genus $\leq g$}.

We prove that for every $d\geq 2$, deciding if a pure, $d$-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every $d \ge 2$ and $k \ge 0$, deciding if a pure, $d$-dimensional, simplicial com…

We prove that certain problems naturally arising in knot theory are NP--hard or NP--complete. These are the problems of obtaining one diagram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number $k$, finding a $k$-component unlink as a sub…

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into $\mathbb{R}^3$ is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an $\mathbb{S}^{3}$ filling is NP-hard. The former stands in contrast with the lower dimensional cases wh…

Market competition depends on computational complexity, P != NP makes it impossible.

We show that the problem of showing that a cusped 3-manifold M is not hyperbolic is in NP, assuming $S^3$-RECOGNITION is in coNP. To this end, we show that IRREDUCIBLE TOROIDAL RECOGNITION lies in NP. Along the way we unconditionally recover SATELLITE KNOT RECOGNITION lying in NP. This was previously known only assumin…

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…

We show that the problem of recognizing that a knot diagram represents a specific torus knot, or any torus knot at all, is in the complexity class ${\sf NP} \cap {\sf co\text{-}NP}$, assuming the generalized Riemann hypothesis. We also show that satellite knot detection is in ${\sf NP}$ under the same assumption, and t…

Trading system uses NP-hard optimization to select stocks for high Sharpe ratio trading.

Knot genus problem solved for all 3-manifolds.

Paper introduces scalable neural architecture for solving NP-hard problems.

We prove that the three-sphere recognition problem lies in the complexity class NP. Our work relies on Thompson's original proof that the problem is decidable [Math. Res. Let., 1994], Casson's version of her algorithm, and recent results of Agol, Hass, and Thurston [ArXiv, 2002].

Two DRL policies collaborate to solve NP-hard routing problems.

It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in test…

Rényi Neural Processes replace KL divergence with Rényi divergence to improve NP performance.

NP-iMCMC algorithm for nonparametric models in universal PPLs.

The pinning ideal of multiloops is shown to be NP-complete.

Complex pinning problem simplified for simple multiloops.

Equity-Transformer solves NP-hard min-max routing problems efficiently.

We investigate the computational complexity of some problems in three-dimensional topology and geometry. We show that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. Using similar ideas, we show that deciding whether a curve in a metrized PL 3-manifold bounds a surface of area…

Paper tackles P vs NP problem in portfolio optimization with cardinality constraints and Black-Scholes derivatives.

Optimal CL requires perfect memory and is NP-hard.

Recognition of Seifert fibered spaces with boundary is computationally tractable.

Given a tame knot K presented in the form of a knot diagram, we show that the problem of determining whether K is knotted is in the complexity class NP, assuming the generalized Riemann hypothesis (GRH). In other words, there exists a polynomial-length certificate that can be verified in polynomial time to prove that K…

We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.

In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that $(d,k)$-collapsibility is NP-complete for $d\geq k+2$ except $(2,0)$. By $(d,k)$-collapsibility we mean the following problem: determine whether a given $d$-dimensional simplicial complex can be collapsed to some $k$-dimensional sub…

Bailouts in financial networks are hard to optimize due to NP-hardness.

Researchers prove NP-hardness of learning parameter-bounded Bayes nets.

We show that three natural decision problems about links and 3-manifolds are computationally hard, assuming some conjectures in complexity theory. The first problem is determining whether a link in the 3-sphere bounds a Seifert surface with Thurston norm at most a given integer; this is shown to be NP-complete. The sec…

Neural Processes (NPs) are a class of models that learn a mapping from a context set of input-output pairs to a distribution over functions. They are traditionally trained using maximum likelihood with a KL divergence regularization term. We show that there are desirable classes of problems where NPs, with this loss, f…

New proof shows a link problem is hard without complex links.

Study shows optimal RL with transition look-ahead is NP-hard for $\ell \geq 2$.

We investigate the complexity of finding an embedded non-orientable surface of Euler genus $g$ in a triangulated $3$-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into $3$-manifolds. We prove that the problem is NP…

We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph…

Two fundamental objects in knot theory are the minimal genus surface and the least area surface bounded by a knot in a 3-dimensional manifold. When the knot is embedded in a general 3-manifold, the problems of finding these surfaces were shown to be NP-complete and NP-hard respectively. However, there is evidence that …

New method uses reinforcement learning to improve Simulated Annealing.

Paper solves NP-hard sparse mixed linear regression problem with provable guarantees.

We give a reduction from {\sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.

EPMF factorizes matrices by adjusting their entries to match a specified power.

New algorithm controls type I error in NP classification under label noise.

New MIP formulations for neural network Lipschitz constant estimation.