The critical complexity of graph properties
The critical complexity of a Boolean function \(f(x_ 1,...,x_ n)\) is \(c(f):=\max \{| \{i:\quad f(x)\neq f(x^ i)\}|:\quad x\in \{0,1\}^ n\},\) where \(x^ i\) is obtained by changing the i-th component of x. \textit{S. Cook} and \textit{C. Dwork} [Bounds on the time for parallel RAMs to compute simple functions, Proc. 14th ACM STOC, 231-233 (1982)] proved that log c(f) (in base \({1\over2}(5+\sqrt{21}))\) is a lower bound to the time needed by a parallel RAM to compute f. \textit{H.-U. Simon} [Lect. Notes Comput. Sci. 158, 439-444 (1983; Zbl 0523.68036)] gave a sharp \(\Omega\) (log n) bound for the critical complexity of nondegenerate Boolean functions. Here it is shown that if \(n=\left( \begin{matrix} m\\ 2\end{matrix} \right)\) and f is a nontrivial property of graphs on m vertices, then \(c(f)\geq \lfloor m/4\rfloor.\) (The property of containing an isolated point shows that the bound is sharp within a constant factor.) This implies an \(\Omega\) (log n) lower bound to the parallel complexity of graph properties.
- 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
- On induced subgraphs of the cube
- Some results on the complexity of families of sets
- Complexity measures and decision tree complexity: a survey.
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
- Certificate complexity of elementary symmetric Boolean functions
- Threshold circuits of bounded depth
- Block sensitivity of weakly symmetric functions
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- On Graph Complexity
- scientific article; zbMATH DE number 3916178 (Why is no real title available?)
- The critical complexity of all (monotone) boolean functions and monotone graph properties
- scientific article; zbMATH DE number 4024813 (Why is no real title available?)
- An improved lower bound on the sensitivity complexity of graph properties
- Properties of complexity measures for PRAMs and WRAMs
- A tighter relation between sensitivity complexity and certificate complexity
- On the relationship between energy complexity and other Boolean function measures
- Separations between combinatorial measures for transitive functions
- Decision tree complexity versus block sensitivity and degree
- Block sensitivity of minterm-transitive functions
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
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)
