{"results":[{"id":"arxiv_2507.23504","title":"A Verifier Hierarchy","authors":[{"name":"Maurits Kaptein"}],"abstract":"We investigate the trade-off between certificate length and verifier runtime. We prove a Verifier Trade-off Theorem showing that reducing the inherent verification time of a language from \\(f(n)\\) to \\(g(n)\\), where \\(f(n) \\ge g(n)\\), requires certificates of length at least \\(Ω(\\log(f(n) / g(n)))\\). This theorem induces a natural hierarchy based on certificate complexity. We demonstrate its applicability to analyzing conjectured separations between complexity classes (e.g., \\(\\np\\) and \\(\\exptime\\)) and to studying natural problems such as string periodicity and rotation detection. Additionally, we provide perspectives on the \\(\\p\\) vs. \\(\\np\\) problem by relating it to the existence of sub-linear certificates.","source":"arXiv","year":2025,"language":"en","subjects":["cs.LG"],"url":"https://arxiv.org/abs/2507.23504","pdf_url":"https://arxiv.org/pdf/2507.23504","is_open_access":true,"published_at":"2025-07-31T12:42:42Z","score":69},{"id":"ss_2acee78f69943354f112fb6a08e22bbadc3a4406","title":"A Dichotomy for Finite Abstract Simplicial Complexes","authors":[{"name":"Sebastian Meyer"}],"abstract":"Given two finite abstract simplicial complexes A and B, one can define a new simplicial complex on the set of simplicial maps from A to B. After adding two technicalities, we call this complex Homsc(A, B). We prove the following dichotomy: For a fixed finite abstract simplicial complex B, either Homsc(A, B) is always a disjoint union of contractible spaces or every finite CW-complex can be obtained up to a homotopy equivalence as Homsc(A, B) by choosing A in a right way. We furthermore show that the first case is equivalent to the existence of a nontrivial social choice function and that in this case, the space itself is homotopy equivalent to a discrete set. Secondly, we give a generalization to finite relational structures and show that this dichotomy coincides with a complexity theoretic dichotomy for constraint satisfaction problems, namely in the first case, the problem is in P and in the second case NP-complete. This generalizes a result from [SW24] respectively arXiv:2307.03446 [cs.CC]","source":"Semantic Scholar","year":2024,"language":"en","subjects":["Mathematics","Computer Science"],"doi":"10.48550/arXiv.2408.08199","url":"https://www.semanticscholar.org/paper/2acee78f69943354f112fb6a08e22bbadc3a4406","is_open_access":true,"citations":3,"published_at":"","score":68.09},{"id":"doaj_10.46298/dmtcs.12544","title":"Leanness Computation: Small Values and Special Graph Classes","authors":[{"name":"David Coudert"},{"name":"Samuel Coulomb"},{"name":"Guillaume Ducoffe"}],"abstract":"Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as \u0026quot;interval thinness\u0026quot; and \u0026quot;fellow traveler property\u0026quot;. Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS'21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.","source":"DOAJ","year":2024,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.12544","url":"http://dmtcs.episciences.org/12544/pdf","pdf_url":"http://dmtcs.episciences.org/12544/pdf","is_open_access":true,"published_at":"","score":68},{"id":"doaj_10.46298/dmtcs.10952","title":"Holonomic equations and efficient random generation of binary trees","authors":[{"name":"Pierre Lescanne"}],"abstract":"Holonomic equations are recursive equations which allow computing efficiently numbers of combinatoric objects.  Rémy showed that the holonomic equation associated with binary trees yields an efficient linear random generator of binary trees.  I extend this paradigm to Motzkin trees and Schröder trees and show that despite slight differences my algorithm that generates random Schröder trees has linear expected complexity and my algorithm that generates Motzkin trees is in O(n) expected complexity, only if we can implement a specific oracle with a O(1) complexity.  For Motzkin trees, I propose a solution which works well for realistic values (up to size ten millions) and yields an efficient algorithm.","source":"DOAJ","year":2024,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.10952","url":"http://dmtcs.episciences.org/10952/pdf","pdf_url":"http://dmtcs.episciences.org/10952/pdf","is_open_access":true,"published_at":"","score":68},{"id":"arxiv_2408.08199","title":"A Dichotomy for Finite Abstract Simplicial Complexes","authors":[{"name":"Sebastian Meyer"}],"abstract":"Given two finite abstract simplicial complexes A and B, one can define a new simplicial complex on the set of simplicial maps from A to B. After adding two technicalities, we call this complex Homsc(A, B).   We prove the following dichotomy: For a fixed finite abstract simplicial complex B, either Homsc(A, B) is always a disjoint union of contractible spaces or every finite CW-complex can be obtained up to a homotopy equivalence as Homsc(A, B) by choosing A in a right way.   We furthermore show that the first case is equivalent to the existence of a nontrivial social choice function and that in this case, the space itself is homotopy equivalent to a discrete set.   Secondly, we give a generalization to finite relational structures and show that this dichotomy coincides with a complexity theoretic dichotomy for constraint satisfaction problems, namely in the first case, the problem is in P and in the second case NP-complete. This generalizes a result from [SW24] respectively arXiv:2307.03446 [cs.CC]","source":"arXiv","year":2024,"language":"en","subjects":["math.GN","cs.CC"],"url":"https://arxiv.org/abs/2408.08199","pdf_url":"https://arxiv.org/pdf/2408.08199","is_open_access":true,"published_at":"2024-08-15T15:08:09Z","score":68},{"id":"doaj_10.46298/dmtcs.9302","title":"From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows","authors":[{"name":"Cláudio Carvalho"},{"name":"Jonas Costa"},{"name":"Raul Lopes"},{"name":"Ana Karolinna Maia"},{"name":"Nicolas Nisse"},{"name":"Cláudia Sales"}],"abstract":"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. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \\ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. On thepositive side, we show that it guarantees the existence of the desired flows in some particular casesdepending on the choice of the capacity function or on the structure of the underlying graph of D,for example. We remark that, in those positive cases, polynomial time algorithms to find the flowscan be extracted from the constructive proofs.","source":"DOAJ","year":2023,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.9302","url":"http://dmtcs.episciences.org/9302/pdf","pdf_url":"http://dmtcs.episciences.org/9302/pdf","is_open_access":true,"published_at":"","score":67},{"id":"doaj_10.46298/dmtcs.5734","title":"Freezing, Bounded-Change and Convergent Cellular Automata","authors":[{"name":"Nicolas Ollinger"},{"name":"Guillaume Theyssier"}],"abstract":"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 number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension~1, but also dimension~1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension~ 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.","source":"DOAJ","year":2022,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.5734","url":"https://dmtcs.episciences.org/5734/pdf","pdf_url":"https://dmtcs.episciences.org/5734/pdf","is_open_access":true,"published_at":"","score":66},{"id":"arxiv_2111.04335","title":"Differential information theory","authors":[{"name":"Pieter Adriaans"}],"abstract":"This paper presents a new foundational approach to information theory based on the concept of the information efficiency of a recursive function, which is defined as the difference between the information in the input and the output. The theory allows us to study planar representations of various infinite domains. Dilation theory studies the information effects of recursive operations in terms of topological deformations of the plane. I show that the well-known class of finite sets of natural numbers behaves erratically under such transformations. It is subject to phase transitions that in some cases have a fractal nature. The class is \\emph{semi-countable}: there is no intrinsic information theory for this class and there are no efficient methods for systematic search.   There is a relation between the information efficiency of the function and the time needed to compute it: a deterministic computational process can destroy information in linear time, but it can only generate information at logarithmic speed. Checking functions for problems in $NP$ are information discarding. Consequently, when we try to solve a decision problem based on an efficiently computable checking function, we need exponential time to reconstruct the information destroyed by such a function. At the end of the paper I sketch a systematic taxonomy for problems in $NP$.","source":"arXiv","year":2021,"language":"en","subjects":["cs.IT","cs.CC"],"url":"https://arxiv.org/abs/2111.04335","pdf_url":"https://arxiv.org/pdf/2111.04335","is_open_access":true,"published_at":"2021-11-08T08:53:29Z","score":65},{"id":"doaj_10.23638/DMTCS-22-4-2","title":"A Type System Describing Unboundedness","authors":[{"name":"Paweł Parys"}],"abstract":"We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.","source":"DOAJ","year":2020,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-22-4-2","url":"https://dmtcs.episciences.org/4748/pdf","pdf_url":"https://dmtcs.episciences.org/4748/pdf","is_open_access":true,"published_at":"","score":64},{"id":"doaj_10.23638/DMTCS-22-1-10","title":"New schemes for simplifying binary constraint satisfaction problems","authors":[{"name":"Wady Naanaa"}],"abstract":"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 present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of valuedomains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrizedgeneralizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhoodsubstitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination,which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs byidentifying a new tractable class of binary CSP.","source":"DOAJ","year":2020,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-22-1-10","url":"https://dmtcs.episciences.org/4398/pdf","pdf_url":"https://dmtcs.episciences.org/4398/pdf","is_open_access":true,"published_at":"","score":64},{"id":"doaj_10.23638/DMTCS-22-1-1","title":"Vertex order with optimal number of adjacent predecessors","authors":[{"name":"Jérémy Omer"},{"name":"Tangi Migot"}],"abstract":"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). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥ K + 1 and U ≥ 2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete.","source":"DOAJ","year":2020,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-22-1-1","url":"https://dmtcs.episciences.org/5208/pdf","pdf_url":"https://dmtcs.episciences.org/5208/pdf","is_open_access":true,"published_at":"","score":64},{"id":"ss_0694f121a3795fcd307185954be8d450999ed5c3","title":"Counting perfect matchings and the eight-vertex model","authors":[{"name":"Jin-Yi Cai"},{"name":"Tianyu Liu"}],"abstract":"We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in arXiv:1811.03126 [cs.CC]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the previously known FPRASable region, we show that computing the partition function can be reduced to (with or without approximation) counting perfect matchings. Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems of this kind.","source":"Semantic Scholar","year":2019,"language":"en","subjects":["Computer Science","Mathematics"],"doi":"10.4230/LIPIcs.ICALP.2020.23","url":"https://www.semanticscholar.org/paper/0694f121a3795fcd307185954be8d450999ed5c3","is_open_access":true,"citations":5,"published_at":"","score":63.15},{"id":"doaj_10.23638/DMTCS-21-1-11","title":"Computing metric hulls in graphs","authors":[{"name":"Kolja Knauer"},{"name":"Nicolas Nisse"}],"abstract":"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 its convex subgraphs are given as input. We then show that deciding if the smallest preimage of a closed set is logarithmic in the size of the ground set is LOGSNP-hard if only the ground set is given. A special instance of this problem is to compute the dimension of a poset given its linear extension graph, that is conjectured to be in P.The intent to show that the latter problem is LOGSNP-complete leads to several interesting questions and to the definition of the isometric hull, i.e., a smallest isometric subgraph containing a given set of vertices $S$. While for $|S|=2$ an isometric hull is just a shortest path, we show that computing the isometric hull of a set of vertices is NP-complete even if $|S|=3$. Finally, we consider the problem of computing the isometric hull number of a graph and show that computing it is $\\Sigma^P_2$ complete.","source":"DOAJ","year":2019,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-21-1-11","url":"https://dmtcs.episciences.org/4720/pdf","pdf_url":"https://dmtcs.episciences.org/4720/pdf","is_open_access":true,"published_at":"","score":63},{"id":"doaj_10.23638/DMTCS-21-4-3","title":"Constrained ear decompositions in graphs and digraphs","authors":[{"name":"Frédéric Havet"},{"name":"Nicolas Nisse"}],"abstract":"Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most is polynomial-time solvable for all fixed positive integer. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is N P-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is N P-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most is polynomial-time solvable for all positive integer ; deciding whether a digraph admits a handle decomposition without handles of length in F is N P-complete for any finite set F of positive integers (and minimizing the number of handles of length in F is not approximable up to n(1 −)); for any k ≥ 2, deciding whether a digraph admits a handle decomposition with all handles of length 0 mod k is N P-complete. Also, in contrast with the result of Lovász, we prove that deciding whether a digraph admits a handle decomposition with all handles of odd length is N P-complete. Finally, we conjecture that, for every set A of integers, deciding whether a digraph has a handle decomposition with all handles of length in A is N P-complete, unless there exists h ∈ N such that A = {1, · · · , h}.","source":"DOAJ","year":2019,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-21-4-3","url":"https://dmtcs.episciences.org/4544/pdf","pdf_url":"https://dmtcs.episciences.org/4544/pdf","is_open_access":true,"published_at":"","score":63},{"id":"arxiv_1904.10493","title":"Counting perfect matchings and the eight-vertex model","authors":[{"name":"Jin-Yi Cai"},{"name":"Tianyu Liu"}],"abstract":"We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in arXiv:1811.03126 [cs.CC].   In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the previously known FPRASable region, we show that computing the partition function can be reduced to (with or without approximation) counting perfect matchings. Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma.   We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems of this kind.","source":"arXiv","year":2019,"language":"en","subjects":["cs.CC","cs.DM"],"url":"https://arxiv.org/abs/1904.10493","pdf_url":"https://arxiv.org/pdf/1904.10493","is_open_access":true,"published_at":"2019-04-23T18:52:15Z","score":63},{"id":"crossref_10.1007/978-1-349-94186-5_307","title":"The Center for Cross-Cultural Study (CC-CS)","authors":null,"abstract":"","source":"CrossRef","year":2018,"language":"en","subjects":null,"doi":"10.1007/978-1-349-94186-5_307","url":"https://doi.org/10.1007/978-1-349-94186-5_307","is_open_access":true,"published_at":"","score":62},{"id":"crossref_10.1007/978-1-349-95810-8_309","title":"The Center for Cross-Cultural Study (CC-CS)","authors":null,"abstract":"","source":"CrossRef","year":2018,"language":"en","subjects":null,"doi":"10.1007/978-1-349-95810-8_309","url":"https://doi.org/10.1007/978-1-349-95810-8_309","is_open_access":true,"published_at":"","score":62},{"id":"doaj_10.23638/DMTCS-20-1-13","title":"On interval number in cycle convexity","authors":[{"name":"Julio Araujo"},{"name":"Guillaume Ducoffe"},{"name":"Nicolas Nisse"},{"name":"Karol Suchan"}],"abstract":"Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \\ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q − 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G.Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.","source":"DOAJ","year":2018,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-20-1-13","url":"https://dmtcs.episciences.org/3812/pdf","pdf_url":"https://dmtcs.episciences.org/3812/pdf","is_open_access":true,"published_at":"","score":62},{"id":"doaj_10.46298/dmtcs.1329","title":"Permutation Pattern matching in (213, 231)-avoiding permutations","authors":[{"name":"Both Neou"},{"name":"Romeo Rizzi"},{"name":"Stéphane Vialette"}],"abstract":"Given permutations σ of size k and π of size n with k \u003c n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where only σ avoids 213 and 231, we present a O(max(kn 2 , n 2 log log n)-time algorithm. We extend our research to bivincular patterns that avoid 213 and 231 and present a O(kn 4)-time algorithm. Finally we look at the related problem of the longest subsequence which avoids 213 and 231.","source":"DOAJ","year":2017,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.1329","url":"https://dmtcs.episciences.org/1329/pdf","pdf_url":"https://dmtcs.episciences.org/1329/pdf","is_open_access":true,"published_at":"","score":61},{"id":"arxiv_1708.09398","title":"Designing Strassen's algorithm","authors":[{"name":"Joshua A. Grochow"},{"name":"Cristopher Moore"}],"abstract":"In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with only 7 multiplications instead of 8. The latter construction was arrived at by a process of elimination and appears to come out of thin air. Here, we give the simplest and most transparent proof of Strassen's algorithm that we are aware of, using only a simple unitary 2-design and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use 2-designs coming from group orbits to generalize our construction to all n (although the resulting algorithms aren't optimal for n at least 3).","source":"arXiv","year":2017,"language":"en","subjects":["cs.DS","cs.CC","cs.SC","math.RT"],"url":"https://arxiv.org/abs/1708.09398","pdf_url":"https://arxiv.org/pdf/1708.09398","is_open_access":true,"published_at":"2017-08-30T18:00:06Z","score":61}],"total":114308,"page":1,"page_size":20,"sources":["CrossRef","DOAJ","arXiv","Semantic Scholar"],"query":"cs.CC"}