The critical complexity of graph properties

DOI10.1016/0020-0190(84)90019-XMaRDI QIDQ795503zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Boolean functionparallel processingcritical complexityparallel complexity of graph properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The critical complexity of all (monotone) boolean functions and monotone graph properties
• Publication:3691584
• 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

Cites work

• On recognizing graph properties from adjacency matrices

Cited in

(18)

• Properties of complexity measures for PRAMs and WRAMs
• An improved lower bound on the sensitivity complexity of graph properties
• Certificate complexity of elementary symmetric Boolean functions
• Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
• scientific article; zbMATH DE number 4024813 (Why is no real title available?)
• Block sensitivity of weakly symmetric functions
• On the relationship between energy complexity and other Boolean function measures
• scientific article; zbMATH DE number 3916178 (Why is no real title available?)
• Threshold circuits of bounded depth
• Some results on the complexity of families of sets
• A tighter relation between sensitivity complexity and certificate complexity
• On induced subgraphs of the cube
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Block sensitivity of minterm-transitive functions
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• On Graph Complexity
• Complexity measures and decision tree complexity: a survey.
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions

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)