Circuit Complexity - Models of Computation: Exploring the Power of Computing - page 458

Razborov's lower bound, deriving an exponential one. Later Razborov [ 273 ]demonstrated
that the obvious generalization of the approximation method cannot yield better lower bounds
than Ω( n 2 ) for Boolean functions on n inputs realized by circuits over complete bases.
Berkowitz [ 37 ] introduced the concept of pseudo-inverse and established Theorem 9.6.9 .
Va l i an t [ 347 ], Wegener [ 358 ], and Paterson (unpublished — see [ 92 , 360 ]) independently im-
proved upon the size of the monotone circuit realizing all pseudo-negations from O ( n 2 log n )
to O ( n log 2 n ) to produce Theorem 9.6.8 . Lemma 9.6.9 is due to Dunne [ 90 ].
In his Ph.D. thesis Dunne [ 88 ] has given the most general definition of pseudo-negation.
He shows that a Boolean function h is a pseudo-negation on variable x i of a Boolean function
f on the n variables x 1 , ... , x n if and only if h satisfies
f ( x ) | x i = 0 ≤ h ( x 1 , ... , x i− 1 , x i + 1 , ... , x n ) ≤ f ( x ) | x i = 1

Here f ( x )

| x i = a denotes the function obtained from f by fixing x i at a .
Dunne [ 89 ]demonstratedthat HALF - CLIQUE CENTRAL SLICE is NP -complete (The-
orem 9.6.10 ) and showed that the central slices of the HAMILTONIAN CIRCUIT (there is a
closed path containing each vertex once) and SATISFIABILITY are NP -complete. As men-
tioned by Dunne [ 91 ], not all NP -complete problems have NP -complete central slices.
The concept of communication complexity arose in the context of the VLSI model of
computation discussed in Chapter 12 . In this case it measures the amount of information that
must be transmitted from the inputs to the outputs of a function. The communication game
described in Section 9.7.1 is different: it characterizes a search problem because its goal is to
find an input variable on which two n -tuples in disjoint sets disagree.
Yao [ 366 ] developed a method to derive lower bounds on the communication complexity
of functions f : X Z . He considered the matrix of values of f where the rows

and columns are indexed by the values of X and Y . He defined monochromatic rectangles
as submatrices in which all entries are the same. He then established that the logarithm of
the minimal number of disjoint rectangles in this matrix is a lower bound on the number of
bits that must be exchanged to compute f . (This result shows, for example, that the identity
function f :

× Y →

2 n

n
requires the exchange of at least n + 1 bits.) Savage [ 288 ] adapted the crossing sequence
argument from one-tape Turing machines (an application of the pigeonhole principle) to derive
lower bounds on predicates. Mehlhorn and Schmidt [ 220 ] show that functions f : X

B →B

defined for f ( x , y )= 1ifandonlyif x i = y i for all 1

≤ i ≤

→
Z for which Z is a subset of a field have a communication complexity that is at most the rank
of the two-dimensional matrix of values of f .
The development of the relationship between the circuit depth of a function and its com-
munication complexity follows that given by Karchmer and Wigderson [ 157 ]. Karchmer [ 156 ]
cites Yannakakis for independently discovering the connection D Ω 0 ( f )= C ( f − 1 ( 0 ) , f − 1 ( 1 ))
of Theorem 9.7.1 for non-monotone functions. Karchmer and Wigderson [ 157 ]haveexam-
ined st -connectivity in this framework. This is the problem of determining from the adja-
cency matrix of an undirected graph G with n vertices and two distinguished vertices, s and
t , whether there is a path from s to t .WhencharacterizedasaBooleanfunctionontheedge
variables, this is a monotone function. Karchmer and Wigderson [ 157 ] have shown that the
circuit depth of this function is Ω((log n ) 2 / log log n ) , a result later improved to Ω((log n ) 2 )
independently by Hastad and Boppana in unpublished work. Raz and Wigderson [ 269 ]have
shown via a complex proof that the clique problem on n -vertex graphs studied in Section 9.7.4
has monotone communication complexity and depth Ω( n ) . The simpler but weaker lower
bound for this problem developed in Section 9.7.4 is due to Goldmann and Hastad [ 116 ].

× Y