Recommendations
- The critical complexity of all (monotone) boolean functions and monotone graph properties
- scientific article; zbMATH DE number 3916178
- On Graph Complexity
- An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
- An asymptotic bound for the complexity of monotone graph properties
Cited in
(18)- The critical complexity of all (monotone) boolean functions and monotone graph properties
- scientific article; zbMATH DE number 3916178 (Why is no real title available?)
- An improved lower bound on the sensitivity complexity of graph properties
- On induced subgraphs of the cube
- A tighter relation between sensitivity complexity and certificate complexity
- Block sensitivity of minterm-transitive functions
- Properties of complexity measures for PRAMs and WRAMs
- On Graph Complexity
- scientific article; zbMATH DE number 4024813 (Why is no real title available?)
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
- Some results on the complexity of families of sets
- Block sensitivity of weakly symmetric functions
- Threshold circuits of bounded depth
- Complexity measures and decision tree complexity: a survey.
- Certificate complexity of elementary symmetric Boolean functions
- On the relationship between energy complexity and other Boolean function measures
This page was built for publication: The critical complexity of graph properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795503)
