In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that -collapsibility is NP-complete for except . By -collapsibility we mean the following problem: determine whether a given -dimensional simplicial complex can be collapsed to some -dimensional sub…
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.
169,181 papers · 148 categories
Trend · papers per month
48 results for “NP-Complete”
Shellability is NP-completemath.CO
Proving NP-hardness of shellability and decomposability for simplicial complexes.
problem Determining shellability and decomposability of simplicial complexes.
method Reduction to prove NP-hardness for shellability and decomposability problems.
result Proving NP-hardness and NP-completeness for shellability and decomposability problems in simplicial complexes.
Complex pinning problem simplified for simple multiloops.
problem Complexity of pinning simple multiloops in fixed surfaces.
method Analysis of pinning problem in simple multiloops.
result Pinning problem in simple multiloops is P when 3 strands or fewer, NP-complete when 20 strands or more.
Paper tackles NP-complete subgraph isomorphism counting problem.
problem Counting subgraph isomorphisms in large graphs.
method Learning framework that augments representation learning architectures and iteratively attends pattern and target graphs.
result Scalable learning approach counts subgraph isomorphisms in linear time.
Knot theory problems are proven NP-hard or NP-complete.
problem Problems in knot theory, like diagram transformations and unlinking, are computationally hard.
method Proved NP-hard or NP-complete using Reidemeister moves and sublink analysis.
result Certain knot theory problems are computationally intractable.
Graph Neural Networks solve the decision variant of TSP with high accuracy.
problem Decision variant of the Traveling Salesperson Problem (TSP).
method Graph Neural Networks (GNNs) learn to solve TSP with minimal supervision.
result Graph Neural Networks achieve 80% accuracy in solving TSP with small cost deviations.
The paper connects graph properties to moral graphs and proves the complexity of deciding morality.
problem Deciding the morality of a graph.
method Defining new graph properties and proving their equivalence to morality, and showing the complexity of the problem.
result Morality can be decided in polynomial time for graphs with maximum degree less than 5, but is NP-complete for higher degrees.
Shows NP-completeness of non-hyperbolic 3-manifolds.
problem Determining if a cusped 3-manifold is non-hyperbolic.
method NP-completeness proof using satellite knot recognition and irreducible toroidal recognition.
result Shows NP-completeness of non-hyperbolic 3-manifolds.
Link crossing number problem is NP-hard.
problem Determining the crossing number of a link.
method NP-hardness proof.
result Link crossing number problem is NP-hard.
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 …
Graph colouring model uses GNN to solve NP-Complete problems.
problem Solving NP-Complete problems like graph colouring.
method Simple GNN architecture trained on random instances, generalizes to diverse graph distributions.
result GNN model outperforms Neurosat, Tabucol, and greedy baselines for some graph distributions.
Complex financial networks with CDSs make clearing after shocks NP-complete.
problem Computing solutions for financial networks with CDSs after shocks.
method Computational complexity theory applied to financial network clearing.
result Clearing financial networks with CDSs is NP-complete.
We show that {\sc Heegaard Genus }, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to , is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem {\sc CNF-SAT} to {\sc Heegaard Genus }.
The pinning ideal of multiloops is shown to be NP-complete.
problem Computing the pinning number of multiloops is NP-complete.
method Adapted algorithms from curve intersection and taut loop characterization to prove NP-completeness.
result The pinning number problem is NP-complete for multiloops in the sphere.
Neural model learns efficient, general algorithms for various problems.
problem Learning efficient algorithms that generalize well.
method Carefully designed neural model with imitation and reinforcement learning.
result Neural model outperforms custom solutions on sorting and knapsack problems.
A new approach for inferring optimal decision trees from large datasets.
problem Inferring an optimal decision tree from large datasets is NP-complete.
method Incremental generation of Boolean formula to infer a decision tree of minimum depth.
result The approach scales well and runs efficiently on large datasets.
Let be a 3-manifold. Every knotted (embedded) surface in can be moved via an ambient isotopy in such a way that its projection into is a generic surface. A surface is generic if every point on it is either a regular, double or triple value - the transversal intersection of 1, 2 or 3 embedded surfa…
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…
Glitches cause unreliable AI decisions with steep boundaries.
problem Glitches impair the reliability of AI models with steep decision boundaries.
method Formal definition of glitches, algorithmic search using MILP encoding.
result Glitches are widespread and indicate potential model inconsistencies.
Knot genus problem solved for all 3-manifolds.
problem Determining if a knot bounds a surface of genus g in a fixed 3-manifold.
method Showing the problem is in co-NP for all 3-manifolds.
result The knot genus problem is now solved for all 3-manifolds, not just rational homology 3-spheres.
GraphDETR detects subgraphs in large graphs using deep learning.
problem Detecting subgraphs in large graphs efficiently and accurately.
method Formulates subgraph detection as a set prediction problem using GraphDETR, a deep learning framework.
result GraphDETR can detect diverse patterns in large graphs, achieving strong performance on molecular functional group detection.
This paper unifies observability notions for colored graphs and identifies graph modifications to improve observability.
problem Observability of colored graphs and its relationship to graph properties.
method Unified framework of observability notions, graph modifications, and NP-completeness results.
result Identification of graph modifications to improve observability and NP-completeness of one modification problem.
New algorithm speeds up robustness verification for tree-based models.
problem Formal robustness verification of tree-based models, especially ensembles.
method Reformulated as max-clique problem on a multi-partite graph with bounded boxicity; developed efficient multi-level verification algorithm.
result Tight lower bounds on robustness of decision tree ensembles, hundreds of times faster than previous approach.
We show the problem of counting homomorphisms from the fundamental group of a homology -sphere to a finite, non-abelian simple group is #P-complete, in the case that is fixed and is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions,…
This paper tackles robustness of ensemble stumps and trees under general ℓ_p norm perturbations.
problem The vulnerability of ensemble stumps and trees to small input perturbations under the ℓ_∞ norm.
method Developed dynamic programming algorithms for robustness verification and certified defense under general ℓ_p norm perturbations.
result First certified defense method for ensemble stumps and trees under ℓ_p norm perturbations.
The paper tackles the computational complexity of PLT algorithms, providing tractable solutions.
problem Finding a tree structure that results in a PLT with low computational costs and low statistical error.
method The paper shows that finding an optimal tree structure is NP-complete. It provides linear time solutions for specific cases and an approximation for the general case.
result The paper provides tractable solutions for finding a tree structure with low computational costs and low statistical error.
There are many fundamental algorithmic problems on triangulated 3-manifolds whose complexities are unknown. Here we study the problem of finding a taut angle structure on a 3-manifold triangulation, whose existence has implications for both the geometry and combinatorics of the triangulation. We prove that detecting ta…
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…
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…
Two GPU memory management approaches reduce deep learning model memory usage.
problem Limited GPU memory in deep learning systems.
method Two orthogonal approaches exploiting iterative training algorithm to optimize memory usage.
result Up to 34.2% reduction in memory usage without communication overhead.
We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general, and we describe a computationally efficient alternativ…
A fast ML method solves complex combinatorial auction problems.
problem Solving winner determination in multi-unit combinatorial auctions.
method Graph Neural Network (GNN) with half-convolution operations for bid-item graph modeling.
result Approaches optimal performance with negligible revenue loss and low complexity.
Recognition of Seifert fibered spaces with boundary is computationally tractable.
problem Recognizing Seifert fibered spaces with boundary.
method Proving the existence of fundamental horizontal surfaces and normal vertical annuli with bounded total weight.
result The decision problem is in NP and the construction problem is in FNP.
Paper proposes efficient algorithms to certify robustness of ReLU networks.
problem NP-complete problem of verifying robustness for ReLU networks.
method Two computationally efficient algorithms Fast-Lin and Fast-Lip.
result Delivers bounds close to exact minimum distortion with significant speedup.
Deep learning models are often successfully trained using gradient descent, despite the worst case hardness of the underlying non-convex optimization problem. The key question is then under what conditions can one prove that optimization will succeed. Here we provide a strong result of this kind. We consider a neural n…
The paper analyzes the complexity of untangling knots with a given number of moves.
problem Determining if a knot diagram can be untangled with a specified number of moves.
method Parameterized complexity analysis with respect to the defect, a measure of move efficiency.
result The problem belongs to W[P] when parameterized by defect, and is W[P]-hard by reduction.
Community detection in graphs has been the subject of many algorithms. Recent methods want to optimize a modularity function which shows a maximum of relationships within communities and found a minimum of inter-community relations. these algorithms are applied to unipartite, multipartite and directed graphs. However, …
We consider active, semi-supervised learning in an offline transductive setting. We show that a previously proposed error bound for active learning on undirected weighted graphs can be generalized by replacing graph cut with an arbitrary symmetric submodular function. Arbitrary non-symmetric submodular functions can be…
New algorithm accurately infers hierarchical network clusters.
problem Statistical inference of complex network structures.
method Scalable and reliable algorithm for hierarchical stochastic block models.
result Inferred models are more accurate than other scalable methods.
Community detection using both graphs and social networks is the focus of many algorithms. Recent methods aimed at optimizing the so-called modularity function proceed by maximizing relations within communities while minimizing inter-community relations. However, given the NP-completeness of the problem, these algorith…
NeuroMatch efficiently matches subgraphs in large graphs using neural networks.
problem Determining the presence and location of a query graph in a large target graph.
method NeuroMatch decomposes graphs into subgraphs, embeds them using graph neural networks, and matches them directly in the embedding space.
result NeuroMatch is 100x faster and 18% more accurate than existing methods.
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 …
The paper proves shellability is hard for d-balls when d is at least 3.
problem Shellability for d-balls is NP-hard when d ≥ 3.
method NP-hardness proof for triangulated d-balls and d-manifolds/d-pseudomanifolds with boundary.
result Shellability is NP-hard for triangulated d-balls when d ≥ 3.
A new NMF variant tackles underdetermined problems with sparse and separable assumptions.
problem Underdetermined blind source separation, especially multispectral image unmixing.
method Sparse Separable Nonnegative Matrix Factorization (SSNMF) combining separability and sparsity assumptions. Algorithm based on SNPA and sparse nonnegative least squares.
result In noiseless settings, the algorithm recovers true underlying sources.
RLHO uses RL to generate better initial solutions for heuristic optimization.
problem High sample complexity in generating initial solutions for combinatorial optimization problems.
method RLHO framework that augments heuristic algorithms with RL to generate better initial solutions.
result RLHO outperforms baseline methods on bin packing problem.
We consider the quantifier-free languages, Bc and Bc0, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of n-dimension…
A new reinforcement learning method improves Max-Cut solutions without needing training data.
problem Max-Cut problem is NP-hard, and existing methods struggle with generalizability and scalability.
method Training-data-free reinforcement learning approach to hyperplane rounding for Max-Cut optimization.
result Our method consistently achieves better Max-Cut solutions across various graph types.
GSO framework optimizes COPs on graphs using Gumbel-softmax.
problem Finding optimal configurations or network structures in combinatorial optimization problems.
method Introducing Gumbel-softmax technique for direct optimization of objective functions.
result High-quality solutions obtained with less time compared to traditional methods.