Results 1 to 10 of about 1,098,765 (109)
Query Order and the Polynomial Hierarchy [PDF]
Journal of universal computer science (Online), 1998 Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which information sources are accessed.
Hemaspaandra, Edith +2 more
core +3 more sources
The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [PDF]
Annual Conference Computational Learning Theory, 2023 Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex ...
Alexandros Hollender +1 more
semanticscholar +1 more source
Freezing, Bounded-Change and Convergent Cellular Automata [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded ...
Nicolas Ollinger, Guillaume Theyssier
doaj +1 more source
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains [PDF]
Canadian Conference on Computational Geometry, 2022 Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple type of fixed-angle linkage: every edge has unit length (equilateral), and ...
E. Demaine +3 more
semanticscholar +1 more source
From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans.
Cláudio Carvalho +5 more
doaj +1 more source
New schemes for simplifying binary constraint satisfaction problems [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivatedthe multitude of works that have been devoted to developing techniques that simplify CSP instances before or duringtheir resolution.The ...
Wady Naanaa
doaj +1 more source
Vertex order with optimal number of adjacent predecessors [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs ...
Jérémy Omer, Tangi Migot
doaj +1 more source
Computing metric hulls in graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This implies that there is a polynomial time algorithm to compute the convex hull number of a graph, when all
Kolja Knauer, Nicolas Nisse
doaj +1 more source
The Computational Complexity of Plethysm Coefficients [PDF]
Computational Complexity, 2020 In two papers, Bürgisser and Ikenmeyer (STOC 2011, STOC 2013) used an adaption of the geometric complexity theory (GCT) approach by Mulmuley and Sohoni (Siam J Comput 2001, 2008) to prove lower bounds on the border rank of the matrix multiplication ...
N. Fischer, Christian Ikenmeyer
semanticscholar +1 more source
Model Checking CTL is Almost Always Inherently Sequential [PDF]
Logical Methods in Computer Science, 2011 The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the use of temporal modalities or the use of negations---restrictions already ...
Olaf Beyersdorff +5 more
doaj +1 more source