A topological approach to evasiveness
From MaRDI portal
Publication:1065831
DOI10.1007/BF02579140zbMath0577.05061MaRDI QIDQ1065831
Jeffry Kahn, Michael E. Saks, Dean G. Sturtevant
Publication date: 1984
Published in: Combinatorica (Search for Journal in Brave)
adjacency matrix; graph properties; acyclic; collapsible simplicial complexes; Aanderaa-Rosenberg conjecture; evasive graph properties; evasive properties
68Q25: Analysis of algorithms and problem complexity
05C99: Graph theory
55N99: Homology and cohomology theories in algebraic topology
Related Items
On the elusiveness of Hamiltonian property, One-point suspensions and wreath products of polytopes and spheres, A combinatorial technique for simplicial complexes and some applications to finite groups, A lower bound for the recognition of digraph properties, Topological invariants of classification problems, Complexes of graphs with bounded matching size, On lattices with Möbius function \(\pm 1,0\), Homotopy properties of greedoids, 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, The Rivest-Vuillemin conjecture on monotone Boolean functions is true for ten variables, Decision tree complexity of graph properties with dimension at most 5, Coxeter groups and nonuniform complexity, Some results related to the evasiveness conjecture., Complexity measures and decision tree complexity: a survey., Topology of bounded-degree graph complexes., On the recognition complexity of some graph properties, Nontrivial monotone weakly symmetric Boolean functions with six variables are elusive, Linear colorings of simplicial complexes and collapsing, Collapsing along monotone poset maps, The topology of the independence complex
Cites Work
