A topological approach to evasiveness
From MaRDI portal
Publication:1065831
DOI10.1007/BF02579140zbMath0577.05061MaRDI QIDQ1065831
Jeffry Kahn, Dean G. Sturtevant, Michael E. Saks
Publication date: 1984
Published in: Combinatorica (Search for Journal in Brave)
adjacency matrixgraph propertiesacycliccollapsible simplicial complexesAanderaa-Rosenberg conjectureevasive graph propertiesevasive properties
Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99) Homology and cohomology theories in algebraic topology (55N99)
Related Items (52)
Topology of bounded-degree graph complexes. ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ On lattices with Möbius function \(\pm 1,0\) ⋮ Order complexes of coset posets of finite groups are not contractible. ⋮ Homotopy properties of greedoids ⋮ Linear colorings of simplicial complexes and collapsing ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ On the recognition complexity of some graph properties ⋮ Collapsibility of CAT(0) spaces ⋮ The complexity of graph connectivity ⋮ A hierarchy of dismantlings in graphs ⋮ Knots in collapsible and non-collapsible balls ⋮ A generalization of a result of Dong and Santos-Sturmfels on the Alexander dual of spheres and balls ⋮ Bipartite perfect matching as a real polynomial ⋮ Query complexity of tournament solutions ⋮ Elusive properties of infinite graphs ⋮ Using Brouwer’s Fixed Point Theorem ⋮ Topological invariants of classification problems ⋮ Subdivisions, Shellability, and collapsibility of products ⋮ Barycentric subdivisions of convex complexes are collapsible ⋮ Cooperative games on simplicial complexes ⋮ Nontrivial monotone weakly symmetric Boolean functions with six variables are elusive ⋮ Complexes of graphs with bounded matching size ⋮ An asymptotic bound for the complexity of monotone graph properties ⋮ The smallest nonevasive graph property ⋮ An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties ⋮ An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties ⋮ Strong homotopy types, nerves and collapses ⋮ Unnamed Item ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ Collapsing along monotone poset maps ⋮ Random Discrete Morse Theory and a New Library of Triangulations ⋮ On the elusiveness of Hamiltonian property ⋮ A note on the query complexity of the Condorcet winner problem ⋮ One-point suspensions and wreath products of polytopes and spheres ⋮ The topology of the independence complex ⋮ Unnamed Item ⋮ A new perspective on implementation by voting trees ⋮ New bounds for energy complexity of Boolean functions ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ The worst way to collapse a simplex ⋮ Coxeter groups and nonuniform complexity ⋮ Fixed points of group actions on link collapsible simplicial complexes ⋮ Simplicial simple-homotopy of flag complexes in terms of graphs ⋮ The Rivest-Vuillemin conjecture on monotone Boolean functions is true for ten variables ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Decision tree complexity of graph properties with dimension at most 5 ⋮ Some results related to the evasiveness conjecture. ⋮ Complexity measures and decision tree complexity: a survey. ⋮ A combinatorial technique for simplicial complexes and some applications to finite groups ⋮ Any monotone property of 3-uniform hypergraphs is weakly evasive ⋮ A lower bound for the recognition of digraph properties
Cites Work
This page was built for publication: A topological approach to evasiveness
