The critical complexity of graph properties
From MaRDI portal
Publication:795503
DOI10.1016/0020-0190(84)90019-XzbMATH Open0542.68026OpenAlexW2089621728MaRDI QIDQ795503FDOQ795503
Authors: Gy. Turán 
Publication date: 1984
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(84)90019-x
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
Cited In (18)
- Title not available (Why is that?)
- An improved lower bound on the sensitivity complexity of graph properties
- A tighter relation between sensitivity complexity and certificate complexity
- On induced subgraphs of the cube
- Block sensitivity of minterm-transitive functions
- On Graph Complexity
- Properties of complexity measures for PRAMs and WRAMs
- Title not available (Why is that?)
- 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
- Block sensitivity of weakly symmetric functions
- Some results on the complexity of families of sets
- 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
- The critical complexity of all (monotone) boolean functions and monotone graph properties
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)
