Chapter Combinatorics in Computer Science L Lovasz Department of Computer Science Eotvos University Budapest H   Hungary and Princeton University Princeton NJ USA DB Shmoys and E Tardos School of Operations Research and Industrial Engineering Cornell University Ithaca NY USA 􀀀December Communication complexity Circuit complexity Data structures Cryptography and pseudo random numb e r s It is not surprising that computer science is perhaps the most important eld of appli cations of combinatorial ideas Modern computers operate in a discrete fashion both in time and space and much of classical mathematics must be discretized before it can be implemented on computers as for example in the case of numerical analysis The connection between combinatorics and computer science might b e e v en stronger than sug gested by t h i s o b s e r v ation each eld has pro ted from the other Combinatorics was the rst eld of mathematics where the ideas and concepts of computer science in particular complexity theory had a profound impact This framework for much o f c o m binatorics has been surveyed in Chapter In this chapter we illustrate what computer science pro ts from combinatorics we h a ve collected a number of examples all of them rather important in computer science where methods and results from classical discrete mathematics play a crucial role Since many of these examples rely on concepts from theoretical computer science that have been discussed in Chapter the reader is encouraged to refer to that chapter for background material Communication complexity There are many situations where the amount of communication between two proces sors jointly solving a certain task is the real bottleneck examples range from commu nication between the earth and a rocket approaching Jupiter to communication between dierent parts of a computer chip We shall see that communication complexity also plays an important role in theoretical studies and in particular in the complexity theory of cir cuits Other examples of such indirect applications of communication complexity include bounds on the depth of decision trees 􀀀Hajnal Maass and Turan and pseudoran dom number generation 􀀀Babai Nisan and Szegedy Communication complexity i s a m uch simpler and cleaner model than computational or circuit complexity and it illustrates notions from complexity theory like non determinism and randomization in a particularly simple way O u r i n terest in this eld also stems from the many w ays in which it relates to combinatorial problems and methods This section gives just a glimpse of this theory see Lovasz for a broader survey Suppose that there are two p l a yers Alice and Bob who want t o e v aluate a function fxy in twovariablesforsimplicity weassumethatthevalueof f is a single bit Alice knows the value of the variable x Bob knows the value of the variable y and they can communicate with each o t h e r Local computation is free but communication is costly What is the minimum number of bits that they have t o c o m m unicate We can describe the problem by a matrix as follows Let aa N be the possible inputs of Alice and bb M the possible inputs of Bob Note that since local computa tion is free we need not worry about how these are encoded Let cij fai b j The NM matrix Ccij determines the communication problem Both players know t h e ij matrix C Alice also knows the index i of a row Bob knows the index j of a column and they want to determine the entry cij To solve their task for a particular matrix C Alice and Bob before learning their inputs i and j agree in advance on a protocol which i s t h e c o m m unication analogue to the fundamental notion of an algorithm in computational complexity theory Informally a communication protocol is a set of rules specifying the order and meaning of the messages sent The protocol prescribes each action for Alice and Bob who is to send the rst bit depending on the input of that processor what this bit should be depending on this bit who is to send the second bit and depending on the input of that processor and on the rst bit sent what this second bit should be and so on The protocol terminates when one processor knows the output bit and the other one knows this about the rst one The complexity ofaprotocol is the numberofbitscom m unicatedintheworst case The trivial protocol is that Alice tells her input to Bob We shall see that sometimes there is no better protocol than this trivial one This protocol takes dlog Ne bits if MN then the reverse trivial protocol is clearly better 􀀀For the remainder of this chapter we shall use log to denote log A protocol has the following combinatorial description in terms of the matrix First it determines who sends the rst bit say Alice does This bit is determined by the input of Alice in other words the protocol partitions the rows of the matrix C into two classes and the rst bit of Alice tells Bob which of the two classes contains her row From now o n t h e game is limited to the submatrix C formed by the rows in this class Next the protocol describes a partition of either the rows or columns of C into two classes depending on who is to send the second bit and the second bit itself speci es which of these two classes contains the line 􀀀row or column of the sender This limits the game to a submatrix C and so it continues If the game ends after k bits then the remaining submatrix Ck is the union of an all  submatrix and an all  submatrix We shall call this an almosthomogeneous matrix If for example Alice knows the answer then her row i n Ck must be all  or all  and since Bob knows for sure that Alice knows the answer this must be true for every row o f Ck We can therefore characterize the communication complexity b y the following com binatorial problem given a matrix C i n h o w many rounds can we partition it into almost homogeneous submatrices if in each round we can split each of the current subma trices into two either horizontally or vertically We shall denote this numb e r b y C If rk􀀀 C denotes the rank of C then the following inequality observed by Mehlhorn and Schmidt relates the communication complexity to the rank of the matrix Lemma Over any eld log rk􀀀 CC rk􀀀 C 􀀀The lower bound is tightest if we use the real eld whereas the upper bound might b e tightened by considering a nite eld In particular we obtain that if C has full row rank then the trivial protocol is op timal This corollary applies directly to a number of communication problems of which we m e n tion three Suppose that Alice knows a subset X of an n element s e t S and Bob knows a subset Y of S T he equality problem is to decide if the two subsets are equal the disjointness problem is to decide if the two subsets are disjoint the binary inner product problem is to decide if the intersection of the two sets has odd cardinality In nn the rst two cases it is trivial to see that the corresponding matrices have f u l l n rank in the third case the rank of the matrix is Hence the trivial protocols are optimal 􀀀It is interesting to remark that in the third case the rank over GF􀀀 which might seem more natural to use in this problem gives a very poor bound here the GF􀀀 rank of C is only n The lower bound in the lemma is often sharp on the other hand no communication problem is known for which C i s a n ywhere near the bound rk􀀀 C In particular it is open whether C can be bounded by a n y polynomial of log rk􀀀 C To p o i n t out that the situation is not always trivial consider again the equality prob lem Recall that if N denotes the number of inputs then the trivial protocol takes dlog Ne bits and this is optimal In contrast Freivalds obtained the very nice result that if Alice and Bob tolerate errors occurring with probability then the situation changes drastically Consider the following protocol which can be viewed as an extension of a parity c heck Treat the inputs as two natural numb e r s x and y xyN Alice selects a random prime p 􀀀log N computes the remainder x of x modulo p and then sends the pair xp to Bob Bob then computes the remainder y of y modulo p and compares it with x If they are distinct he concludes that xy if they are the same he concludes that xy If the two n umbers x and y are equal then of course so are x and y and so the protocol reaches the right conclusion If x and y are dierent then it could happen that xy and so the protocol reaches the wrong conclusion This happens if and only if p is a divisor of xy Since jxyj N it follows that xy has fewer than log N dierent prime divisors On the other hand Alice had about 􀀀log N log log N primes from which t o choose and so the probability that she chose one of the divisors of xy tends to For N suciently large the error will be smaller than Clearly this protocol uses at most log log N bits Randomization need not lead to such dramatic improvements for all problems We have seen that the binary inner product problem and the disjointness problem behave q u i t e similarly to the equality problem from the point of view of deterministic communication complexity the corresponding matrices have essentially full rank and hence the trivial protocols are optimal But unlike for the equality problem randomization is of little help here Chor and Goldreich proved that the randomized communication complex ity of computing the binary inner product problem is n Improving results of Babai Frankl and Simon XXX showed that the randomized communication com plexity of the disjointness problem is n The proofs of these facts combine the work of Yao on randomized communication complexity with rather involved combinatorial considerations Just as in computational complexity theory non determinism plays a crucial role in communication complexity theory Non deterministic protocols were introduced by Lipton and Sedgewick Perhaps the best way to view a non deterministic protocol is as a scheme by w h i c h a third party k n o wing both inputs can convince Alice and Bob what the value of f isAgain wewant to minimizethenumberofbitssuch a certicate contains for the worst inputs For example if in the disjointness problem the two subsets are not disjoint announcing a common element c o n vinces both players that the answer is no This certi cate takes only dlog ne bits which i s m uch smaller than the number of bits Alice and Bob would need to nd the answer which i s n as w e h ave seen Ontheother hand if the sets are disjoint then no such simple non deterministic scheme exists We shall distinguish between the non deterministic protocol for the and for the In both cases there is always the trivial protocol that announces the input of Alice To g i v e a formal and combinatorial description of non deterministic protocols consider a non deterministic protocol for a particular certi cate p and those entries of C 􀀀ie inputs for Alice and Bob for which this certi cate works If the proof scheme is correct these must be all s from the fact that Alice and Bob have t o v erify the certi cate independently w e also see that these s must form a submatrix Thus a non deterministic protocol corresponds to a covering of C by all  submatrices Conversely every such covering gives a non deterministic protocol one can simply use the name of the submatrix containing the given entry as a certi cate The number of bits needed is the logarithm of the number of dierent certi cates used the non deterministic communication complexity C of a matrix C is the least natural numb e r t such that the s in C can be covered t by a t m o s t all  submatrices One can analogously de ne C the non deterministic communication complexity of certifying a Note that the all  submatrices in the covering need not be disjoint Therefore there is no immediate relation b e t ween rk C and C It is easy to formulate the non deterministic communication complexity of a matrix as a set covering problem consider the hypergraph whose vertices are the s in C and whose edges are the all  submatrices C is the logarithm of the minimum number of edges covering all vertices An immediate lower bound on C follows from a simple counting argument if C has a s but each all  submatrix of C has at most b entries then trivially C log a log b We can also consider the natural dual problem if is the maximum number of s in C such that no two occur in the same all  submatrix then C log Returning to the three problems on two sets mentioned above we see that the s nn n in the identity matrix cannot be covered by fewer that all  submatrices hence the non deterministic communication complexity of equality i s n Similarly the n non deterministic communication complexity of set disjointness is n since F or the binary inner product problem it is easy to see by elementary linear algebra that an all  n nn submatrix has at most entries and that exactly entries are s This n gives that at least all  submatrices are needed to cover the s and so Cn For this matrix a similar argument a l s o s h o ws that Cn We h a ve derived the following lower bound on the communication complexity o f a matrix max log rk􀀀 CCC C The identity matrix shows that might b e a v ery weak bound C can be exponentially large compared with C Interchanging the roles of and we obtain that C might also be very far from C No such example is known for log rk􀀀 C but it is likely that the situation is similar However it is a surprising fact that the product of any t wo of these three lower bounds is an upper bound on the communication complexity The rst part of the following theorem is due to Aho Ullman and Yannakakis and the other two to Lovasz and Saks Theorem For every matrix C 􀀀a C C C 􀀀b C blog rk􀀀 C c C 􀀀c C blog 􀀀rk􀀀 C c C We shall sketch a result that is stronger than each of 􀀀a b and 􀀀c Let C denote the size of the largest square submatrix of C such that after a suitable reordering of the rows and columns each diagonal entry is but each e n try above the diagonal is 1 C It is clear that C rk􀀀 C and C Ifwe de ne C analogously t h e n C rk􀀀 C By using these inequalities we can obtain all three parts of Theorem from the following result Theorem C blog C c C Proof We use induction on C If C then trivially C Assume that C and let kC then the elements of C can be covered by all  submatrices k CC l where l Let Ai denote the submatrix formed by t h o s e r o ws of C that meet Ci and let Bi denote the analogous submatrix formed from columns of C Observe that Ai Bi Ci l this will play a crucial role in the following protocol First Alice looks at her row to see if it intersects any submatrix Ci with Ai C If so she sends a and the name i of such a submatrix They have thereby reduced the problem to the matrix Ai If not she sends a When Bob receives this he looks at his column to see if it intersects any submatrix Ci with Bi C If so he sends a and the name i of such a submatrix They have thereby reduced the problem to the matrix Bi If not he sends a If both Alice and Bob failed to nd an appropriate submatrix then by the intersection of their lines cannot belong to any Ci and so it must be a They have found the answer Theorem 􀀀a has an interesting interpretation De ne a communication problem as a class H of matrices for simplicity assume that they are square matrices The communication complexity o f a n y NN matrix is at most log N We saythat H is in Pcomm if it can be solved substantially better if there exists a constant c such that c C 􀀀log log N for each NN matrix C H Similarly w e say that H is in NP comm c if there exists a constant c s u c h that for each C H C 􀀀log log N and de neco NP comm analogously based on C Just as for the analogous computational complexity classes we h a ve the trivial containment Pcomm NP comm co NP comm However for the communication complexity classes we a l s o have the following rather interesting facts Pcomm NP comm NP comm co NP comm which f o l l o w from the equality problem but Pcomm NP comm co NP comm by Theorem 􀀀a This idea was developed by Babai Frankl and Simon who de ned and studied communication analogues of many other well known complexity classes such as PP SP A CE and BP P Our previous examples were trivial from the point of view of communication the trivial protocols are optimal This is quite atypical Let us de ne a round in the protocol as a maximal period during which one player sends bits to the other The trivial protocol k consists of one round Let C denote the minimum number of bits needed by a c o m munication protocol with at most k rounds Halstenberg and Reischuk proved that k for every k there exist arbitrarily large matrices C such that C is exponentially k larger than C We consider two combinatorial examples to illustrate that protocols can be signi cantly more ecient than the trivial ones Yannakakis considered the following problem Alice and Bob are given a graph G on n nodes Alice is given a stable set A and Bob is given a clique B they must decide whether these sets intersect The corresponding matrix C has rank n but size exponential in n and so the trivial protocol takes n bits 􀀀Recall that we always focus on the worst case complexity On the other hand the non deterministic communication complexity of non disjointness is log n since the name of a common node of A and B is a certi cate by Theorem C log n 􀀀The number of rounds in the protocol is O 􀀀log n It is not known whether the deterministic complexity o r e v en the non deterministic complexity of disjointness is smaller such a s O 􀀀log n It is interesting to remark that the latter question is equivalent to the following purely graph theoretic question is there a constant c so that in eachgraph G on n c nodes there exist n cutssuch that each p a ir o f d isjo in tsets UV w h ere U is a stable set and V is a clique is separated by one of these cuts In the subtree disjointness problem there is a tree T known to both players Alice gets a subtree TA and Bob gets a subtree TB and their task is to decide whether TA and TB are node disjoint It can be shown that the corresponding matrix C has rank n but has exponential size The non deterministic complexity of non disjointness is log n and hence by Theorem C log n In this case one can do better by using the following simple protocol Alice sends any n o d e x of her tree to Bob If y is the node in Bobs tree that is closest to x Bob responds by sen d in g y to Alice Then Alice checks if yTA if so then clearly the subtrees are not disjoint if not the subtrees are disjoint This protocol uses log n bits Lovasz and Saks showed that it can be modi ed to use only log n log log n bits An interesting and rather general class of communication problems for which g o o d bounds on the complexity can be obtained by non trivial combinatorial means was formu lated by Hajnal Maass and Turan Let L be a nite lattice Assume that Alice is given an element a L and Bob is given an element b L and their task is to decide whether ab the minimal element of the lattice This problem generalizes both the disjointness problem 􀀀where L is a Boolean algebra and the subtree disjointness problem where L is the lattice of subtrees of a tree A third special case worth mentioning is the following spanning subgraph problem Alice is given a graph GA and Bob is given a graph GB on the same set of nodes V they wish to decide whether GA GB is connected This case relies on the lattice of partitions of V but upside down so that the indiscrete partition is Alice can compute the partition a of V into the connected components of GA Bob can compute the partition b of V into the connected components of GB and then they decide whether ab For a given lattice L le t C be the matrix associated with the corresponding problem its rows and columns are indexed by the elements of L and cij if and only if ij To nd the rank of this matrix we g i v e the following factorization of it using the Mobius function of L 􀀀see Chapter for the de nition and some basic properties Let Zzij be the zeta matrix of the lattice ie let zij if and only if i jij L Let Ddij denote the diagonal matrix de ned by dii identity found by Wilf and Lindstrom ZTC D i Z Then it is easy to verify the following 􀀀see Chapter Since Z is trivially non singular this implies that rk􀀀 C r k D jfi i gj This gives a lower bound on the communication complexity of our problem but how g o o d is this bound One case when this bound is tight occurs when i for all i We obtain a lower bound of dlog jLje which is also the upper bound achieved by the trivial protocol that is the trivial protocol is optimal By Corollary of Chapter this case occurs when L is a geometric lattice or a geometric lattice upside down In particular we see that for the spanning subgraph problem the trivial protocol is optimal It turns out that the lower bound given by log rk􀀀 C is not too far from the truth for any lattice Theorem For every lattice L log rk􀀀 CC log rk􀀀 C Proof 􀀀upper bound Observe that a non deterministic certi cate of non disjointness of two elements ab L can be provided by exhibiting an atom of the lattice below b o t h a and b Hence the logarithm of the number of atoms is an upper bound on C Since for every atom ii it follows from the identity that the number of atoms is at most rk􀀀 C Hence the upper bound follows directly from Theorem Circuit complexity One promising approach to proving lower bounds on the computational complexity o f a problem focuses on the Boolean circuit model of computation and recent results in this area are possibly the deepest applications of combinatorial methods to computer science thus far The best way to view a circuit is not as an abstract electronic device instead view it as the bit operational skeleton of any computational procedure MR this way i t is not hard to see that this model is equivalent to other models such a s t h e T uring machine or RAM and that the number of functional elements or gates in a circuit is equivalent to the time taken by an algorithm in those models 􀀀More precisely a RAM algorithm for example is equivalent to a family of Boolean circuits one for each input length As a result the extremely dicult task of proving lower bounds on the computational complexity of a given problem can be posed in a way m uch more suited to combinatorial methods Many people believe that this is the direction of research that may e v entually lead to the solution of famous problems such a s P vs NP Unfortunately the handful of results obtained at this point are rather dicult and yet quite far from this objective Let us recall some de nitions from Chapter A Boolean circuit is an acyclic directed graph nodes of indegree are called input gates and are labelled with the input variables xx n nodes with outdegree are called output gates e v ery node with indegree r is called a functional gate and is labelled with a Boolean function in r variables corresponding to the predecessors of the node For our purposes it suces to allow only the logical negation conjunction and disjunction as functions The numb e r of gates in a circuit is called its size th e circuit complexity of a problem is the size of the smallest circuit that computes this Boolean function The outdegree and indegree of a node are referred to as its fanout and fanin respectively Another important parameter of a circuit is its depth the maximum length of a path from an input gate to an output gate A circuit can also be viewed as parallel algorithm and then the depth corresponds to the 􀀀parallel time that the algorithm takes Note that every Boolean function can be computed by a Boolean circuit of depth this is easily derived from its conjunctive normal form Of course the number of gates which i s essentially the number of terms in this normal form is typically exponential A circuit is monotone if only conjunctions and disjunctions are allowed as functional gates Note that every monotone increasing Boolean function can be computed by a monotone Boolean circuit The predominant approach to proving circuit complexity l o wer bounds is to restrict the class of allowed circuits Two kinds of restrictions have p r o ved suciently strong and yet reasonably interesting to allow the derivation of superpolynomial lower bounds on the number of gates monotonicity and bounding the depth Two main methods seem to emerge the random restriction method and the approximation method Both methods have applications for both kinds of restricted problems The rst superpolynomial lower bound in a restricted model of computation concerned constant depth circuits Note that for this class of circuits to make sense we m ust allow that the gates have arbitrarily large fan out and fan in Furst Saxe and Sipser and Ajtai proved independently that every constant depth circuit computing the parity function has superpolynomial size the parity function maps xx n xxn where here and throughout this section addition is the mod sum Yao established a truly exponential lower bound by extending the techniques of Furst Saxe and Sipser Hastad has further strengthened the bound and greatly simpli ed the proof All of these proofs are based on probabilistic combinatorial arguments the proof of the following theorem can be found in Chapter Theorem If C is a circuit with n input bits and depth d that computes the parity 1 d 1 n function then C h a s a t least gates Razborov gave an exponential lower bound on the size of constant depth cir cuits that compute another simple Boolean function the so called majority function ie the function if at least n of the xi are fx x n otherwise In fact he proved a stronger result by allowing circuits that may h a ve parity gates in addition to the usual AND OR and NOT gates where a parity gate computes the parity of the number of s in its input The proof uses the approximation method w hich w as rst used by Razborov a in his pathbreaking paper on monotone circuits The later application of the method is perhaps the cleanest and we are able to reproduce the full proof Theorem If C is a circuit of depth d with AND OR NOT and parity gates that p 1 d n computes the majority function of n input bits then C has at least n gates Proof Consider a circuit that computes the majority function We can assume without loss of generality that the circuit uses only parity and OR gates since these can be used to simulate both AND and NOT gates within constant depth The idea of the proof is to intro duce approximations of the gates used during the computation Using the approximate gates instead of the real gates one computes an approximation of the majority function The quality of the approximation will be measured in terms of the number of inputs on which the modi ed circuit diers from the original The main point of the approximation istokeep the computedfunction simpleinsomesenseWewillshow thatevery sim ple function and in particular the approximation we compute diers from the majority function on a signi cant fraction of the inputs Since the approximation of each gate has a limited e ect on the function computed we can conclude that many a p p r o ximations had to occur Each Boolean function can be expressed as a polynomial over the two element e l d GF The measure of simplicity of a Boolean function f for this proof is the degree of the polynomial representing the function or for short the degree of the function In fact the approximation technique is applied not to the majority function but to a closely related function the k threshold function fk This function is when at least k of the inputs are It is easy to see that if there is a circuit of size s that computes the majority function of n elem en tsindepth d then for each k kn th ere is a circuit of depth d and size at most s that computes the k threshold function on n elements Therefore any e x p o n e n tial lower bound for fk implies a similar bound for the majority function We shall consider k d nh e for an appropriate h First we show that any function of low degree has to dier from the k threshold function on a signi cant fraction of the inputs Lemma Let n kn Every polynomial with n variables of degree h kn n diers from the k threshold function on at least k inputs Proof Let g be a polynomial of degree h and let B denote the set of vectors where it diers from fk L et A denote the set of all vectors of length n containing exactly k s P For each Boolean function f consider the summation function fx yx fy It is trivial to see that the summation function of the monomial xi1 x ir is for the incidence vector of the set fii rg and on all other vectors Hence it follows that f has degree at most h if and only if f vanishes on all vectors with more than h s In contrast to this the summation function of the k threshold fk is on all vectors with fewer than k s but on all vectors with exactly k s Consider the matrix Mmab whose rows are indexed by the members of A w hose columns are indexed by the memb e r s o f B and if ab mab otherwise We w ant to show that the columns of this matrix generate the whole linear space This n will imply that jBj jAj k Let aa A and let aa denote their coordinatewise minimum Then we h a ve by the de nition of B XXX XX ma b fk ugu fk u gu ba1 ba1 a ua1 a ua1 a ua1 a b B b B The second term of this last expression is since aa contains at least h s The rst term is also except if aa The columns of M therefore generate the unit vector corresponding to the coordinate a and so they generate the whole space If p and p are polynomials representing two functions then pp is the polynomial corresponding to the parity of the two functions The polynomial pp corresponds to their AND w h ic h m a k esiteasy toseethat pp corresponds to their OR Note that the inputs have degree ie they are very simple Since the degree is not increased by computing the sum the parity gates do not have t o b e a p p r o ximated On the other hand unbounded fan in OR gates can greatly increase the degree of the computed functions We will approximate the OR gates so that the approximated function will have fairly low degree The following lemma will serve as the basis for the approximation Lemma Let gg m be B o olean functions of degree at most h If r and m fgi then there is a function f ofdegree at m ost rh that diers from f on at most i nr inputs Proof Randomly select r subsets Ij f m g jr where each i is indepen dently included in Ij with probability Let fj be the sum of the gi with iIj and r consider f We claim that the probability that f satis es the requirements of j fj the lemma is non zero It is clear that the degree of the polynomial for f is at most rh Furthermore consider an input w e claim that the probability that ff is at r most T o see this consider two cases If gi for every i then both f and f On the other hand if there exists an index i for which gi then f and for each jfj independently with probability at most Therefore f r with probability at most and the expected number of inputs on which ff is at nr most Hence for at least one particular choice of the sets Ij the polynomial f diers nr from f on at most inputs To nish the proof assume that there is a circuit of size s and depth d to compute d the k threshold function for inputs of size n N o w apply Lemma with r bn c to approximate the OR gates in this circuit The functions computed by the gates at the ith i level will be approximated by polynomials of degree at most r Therefore each resulting d approximation pk of the k threshold function will have degree at most r Lemma d implies that for k d nr e the polynomial pk diers from the k threshold function n nrn on at least inputs This shows that s F rom this routine calculations yield kk that r n rn s p k n which establishes the desired exponential lower bound Smolensky generalized this result to prove that every constant depth circuit that decides whether the sum of the inputs is modulo p using AND OR and modulo q gates has exponential size where p and q arepowersofdi erentprim es How far can one relax the assumption on bounded depth and still obtain superpolyno mial lower bounds The methods of Yao Hastad and Razborov can be extended to depth near log n log log n One cannot hope for much more since the parity function can in fact be computed by a linear size circuit of depth O 􀀀log n log log n Perhaps the deepest result on circuit complexity is contained in the groundbreaking paper of Razborov a He gave a superpolynomial lower bound on the monotone circuit complexity of the clique problem without any restriction on the depth Shortly afterwards Andreev used similar techniques to obtain an exponential lower bound on a less natural NP complete problem Alon and Boppana by strengthening the combinatorial arguments of Razborov proved an exponential lower bound on the monotone circuit complexity o f t h e k clique function n Theorem If C is a monotone circuit with input bits that decides whether a given graph on n nodes contains a clique with at least s nodes then the number of gates in C is at least p s n s log n The proof uses a much more elaborate application of the approximation technique The main combinatorial tool used is the sun$ower theorem of Erdos and Rado 􀀀see Chapter How dierent can the monotone and non monotone circuit complexity of a monotone function be Pratt proved that the monotone circuit complexity of Boolean matrix log multiplication is n This together with the On matrix multiplication technique of Strassen proves that these two notions are distinct Razborov 􀀀b using techniques similar to those used for the clique lower bound showed that the perfect match ing problem which i s i n P has superpolynomial monotone circuit complexity thereby establishing a superpolynomial gap Tardos showed that this could be increased to an exponential separation by c o m bining the arguments of Razborov a Alon and Boppana and results of Grotschel Lovasz and Schrijver on the polynomial computability o f a graph function that is closely related to the clique function 􀀀see Chapter As remarked above no methods are known to handle general circuits with depth greater than log n In the case of monotone circuits with fan in however a version of the random restriction method has been successfully applied by Karchmer and Wigderson to prove a l o wer bound on the depth proportional to log n It is clear that a circuit with fan in and size N must have depth at least log N hence Theorem implies that every monotone circuit with fan in computing the k clique function must have d e p t h n However the function that Karchmer and Wigderson consider is computable by polynomial size monotone circuit and so no non trivial bound on the depth is implied by only considering its size Karchmer and Wigderson considered the undirected reachability problem given a graph G and two nodes s and t is there an st path in G This problem is clearly in P and in fact it can be decided by a polynomial size monotone circuit that has depth O 􀀀log n Karchmer and Wigderson proved the following result Theorem There exists a constant c such that if C is a monotone circuit with fan in that solves the undirected r eachability problem for a graph on n nodes its depth is least c log n The proof which uses a version of the random restriction method is quite involved and is not given here We describe however the starting point which i s a n e w c haracterization of the depth of circuits with fan in at most in terms of communication complexity thereby establishing a surprising link with the material of the previous section Consider the following game between two p l a yers The game is given by a Boolean n function f in n variables The rst player gets x fg such that fx and the n second player gets y fg such that fy The goal of the game is that the two players should agree on a coordinate i such that xi yi Let f denote the minimum number of bits that the two players must communicate to agree on such a coordinate 􀀀For example the rst player could tell x to the second player and then the second player can nd an appropriate coordinate to tell to the rst player so fn lo g n Karchmer and Wigderson proved that the minimum depth in which a Boolean function f can be computed with a circuit with fan in is equal to f A similar characterization can be given for the monotone circuit complexity of monotone Boolean functions In the case of the undirected reachability problem the corresponding game can be phrased as follows the rst player is given an st ' path and the second player is given an st ' cut and the goal of the game is to nd an edge in the intersection of the path and the cut Consider the following protocol for this connectivity game the rst player sends the name of the midpoint on the path and the second player responds by telling on which side of the cut this node lies This protocol requires O 􀀀log n rounds and in each round the rst player sends log n bits and the second player sends Karchmer and Wigderson prove that even if the second player were allowed to send On b i t s i n e a c h round instead of just the players would still need at least 􀀀log n rounds The claimed lower bound on the monotone circuit depth is a consequence of this fact Data structures Imagine a huge science library It contains a wealth of information but to make this information useful catalogues reference and review volumes indices 􀀀and librarians are needed Similarly information in the memory of a computer is useful only if it is accessible ie it is provided with extra structures that make the storage retrieval and modi cation of this information possible and in fact easy This is particularly important when implementing complicated algorithms the fast storage and retrieval of certain partial results of the computation is often the main bottleneck in speeding up such algorithms Such auxiliary structures called data structures are becoming increasingly important as the amount of information stored increases The theory of data structures is very broad and we shall restrict ourselves to two examples that illustrate the depth of combinatorial ideas used in this eld For a more thorough treatment see Aho Hopcroft and Ullman Tarjan and Gonnet a Shortest paths and Fibonacci heaps Let G VGE G be a graph with n nodes and m edges and with a speci ed node s Let every edge e have a non negative length ce We w ant to nd a shortest path from s toevery othernode We have seen in Chapter that using Dijkstras algorithm this is quite easily done in polynomial On steps 􀀀To be precise we use the RAM machine model of computation and a step means an arithmetic operation addition multiplication comparison storage or retrieval of numbers whose length is at most a constant m ultiple of the maximum of log n and the length of the input parameters Let us review this procedure We construct a subtree T of G one node at a time We shall only be concerned with the nodes of this tree so w econsider T as a set of nodes Initially w e let T fsg At any g iv enstep foreach vT we know the length of the shortest path from s to v ie the distance dsv It would be easy to also obtain the edges of the tree then the unique sv ' path in this tree realizes this distance The essence of Dijkstras algorithm is to nd an edge uv EG with uT and v VG n T for which dsu cuv is minimal and then add v to T As shown in Chapter we then have t h a t dsv dsu cuv The issue is to nd this edge economically At rst glance we h a ve to select the smallest member from a set of size Om and we h a ve to repeat this n times so this rough implementation of Dijkstras algorithm takes O mn steps We can easily do better however by k eeping track of some of the partial results that we h a ve obtained Let S denote the set of nodes not in T but adjacent t o T Foreach node vS w e m aintainthevalue v m in fdsu cuv g where the minimum is taken over all edges uv with uT For vS w ede ne v for notational convenience Clearly v is an upper bound on dsv At the beginning v csv for each neighb o r v of s and u for each other node u A step then consists of 􀀀a selecting the node vS for which v is minimum and setting dsv v 􀀀b deleting v from S and adding it to T c adding each neighb o r w of v that is in VG n TS to S and 􀀀d updating the value w foreach neighbor w of v that is in S by w m in w d sv cvw This way it takes On steps to select the node vS for which v is minimum and so the total number of steps spent on selecting these nodes is On There is also the time needed to update the values w this is a constant n umber of steps per node and we h a ve at most d v nodes to consider where d v is the degree of v Updating therefore takes P O v d v O m steps which is dominated by O n by maintaining the current b e s t path lengths Dijkstras algorithm takes On step s Canwe do better Itisnaturaltoassumethatwe have to take at least m steps in order to read the data If m is proportional to n the algorithm just described is best possible But for most real life problems the graph is sparse ie m is much smaller than n and then there is space for improvement To obtain this improvement we shall store the set S together with the values v in a clever way A rst idea is to keep the set S sorted in order of the value of v This makes it trivial to select the next node v and delete it from S buttoachieve􀀀 c a n d d w einsert new items in the sorted list which can be done in O 􀀀log n steps per insertion However even this is non trivial If we simply store the sorted elements of S in an array ie in consecutive elds then to insert a new element we e x p e c t t o m o ve half of the old elements for each insertion Another possibility is to store these elements in a list each element i s stored along with a pointer which speci es the memory location of the next element i n the list In this data structure insertion is trivial but to nd the point of insertion we must traverse the list which takes a linear number of steps Advantages of both methods can be combined using a data structure called a binary search t r e e W e shall not discuss these in detail since we will show h o w to do better with another kind of data structure called a heap Nonetheless Dijkstras algorithm with the current best path lengths stored in a binary search tree takes Om log n steps This may b e m uch better than On but there is still room for improvement At this point it is worth while to formulate the requirements of the desired data structure in an axiomatic way W e h a ve some objects the elements of S w h icharetobe stored Each object has a value v associated with it which is called its key Reviewing the algorithm we see that we m ust perform the following operations on this collection of data DELETEMIN We m ig h t w ant to ndtheelement o f S with smallest key and delete it from S 􀀀steps 􀀀a and 􀀀b INSERT We might w ant to add new elements to S 􀀀step c DECREASEKEY We might c hange the key of elements of S in fact we only need to decrease it 􀀀step 􀀀d Observe that and are performed On times since every node is added at most once and deleted once whereas is performed Om times As mentioned above a heap is a data structure that can handle these operations in logarithmic time Since DECREASEKEY is performed more often than the other two operations we can improve t h e o verall running time by decreasing the cost of performing just this operation Fredman and Tarjan showed how t o d o t h i s b y using a more sophisticated data structure called a Fibonacci heap A heap is a rooted tree de ned on the elements of S with the property that the key ofany node is no m ore than the keyofany of its children Inparticular theroot is an element with the smallest key If the tree is a single path then the heap is a sorted list but it will be worth while to consider more compact trees Before deciding about the shape of the heap let us discuss how to perform the tasks The heap itself can be realized by maintaining a pointer from each non root node to its parent Moreover the children of each node are ordered in an arbitrary way and each c hild contains a pointer to the previous child as well as to the next child Each parent m a i n tains pointers to its rst and last child Each n o d e h a s v e pointers some of which m a y be unde ned parent rst child last child previous sibling next sibling Changes in the heap are made by manipulating these pointers The most common way to implement operations in a heap is as follows DECREASEKEY is perhaps the easiest Assume that we decrease the key of an element p L et pp pt be the path in the tree connecting p to the root If p is still at most p t h e n w e still have a heap otherwise we i n terchange the elements p and p Next we compare the key of p with the key of p if pp we h a ve a heap otherwise interchange p and p and so on After at most tinterchanges we end up with a heap Note that the tree has not changed only the vertices have been permuted INSERT can be reduced to DECREASEKEY if we w ant to add a new element w then we can assign to it a temporary key and make it the child of any preexisting element Trivially this produces a heap We can then decrease the key of wto the right value and reorder the elements as before Finally DELETEMIN can be performed as follows Let rbe theroot element o f th e heap Select any l e a f pof the tree and replace rby p This interchange deletes the root but we do not necessarily have a heap since the key of pmay be larger than the key of one or more of its children Find the child with smallest key and interchange that child with p It is easy to see that the resulting tree again can violate the heap condition only at the node p If phas larger key than some of its children then nd its child with the smallest key and interchange them and so on Eventually w e obtain a heap The height of a node in a rooted tree is the maximum distance to a leaf the height of the tree is the height of its root If the tree has height hthen the operations INSERT and DECREASEKEY take Oh steps to make these operations ecient we w ant t h e tree as short as possible But DELETEMIN puts limits on this it also involves Oh interchanges but before each i n terchange we m ust also nd the child with smallest key and this takes roughly dsteps for a node with dchildren If we u s e balanced kary trees in which with at most one exception all internal nodes have kchildren andeach leaf is at distance hor h from the root then h logk nand so the total number of steps is Onlogk nmlogk n nklogk n T h e b est choiceis k mn and this shows that Dijkstras algorithm with the current best path lengths stored in a kary heap takes Omlog n log mn steps which is a slight improvement One can use more sophisticated trees with a more sophisticated implementation of the basic operations and with a more sophisticated way to count steps A rooted tree is called a Fibonacci tree if for every node vand natural numb e r k thenumber of childrenof vwith degree at most kis at most k 􀀀We use the term degree in the graph theoretic sense the degree of a non root node is one larger than the number of its children The degree of the tree is the degree of the root We w ant to build heaps on such trees For technical reasons it will be convenient to add an arti cial element r with key hence r is always the root Moreover for the root we shall impose the following condition stronger than The degrees of the children of r are distinct A Fibonacci heap is a heap whose underlying tree is a Fibonacci tree that satis es condition We are going to show that by using Fibonacci heaps we can implement Dijkstras algorithm to run in Om n log n steps which is best possible for every m n log n For very sparse graphs this is in some sense an optimal implementation of Dijkstras algorithm but other algorithms may be better Note that the subtree of a Fibonacci tree formed by a node and its descendants is also a Fibonacci tree If we delete a node and its descendants then the only node where condition could be violated is the grandparent of the deleted node In particular if we delete a child of the root and its descendants we are left with a Fibonacci tree By applying induction to this observation we obtain the following lemma which explains the name Fibonacci tree Lemma Let F and F Then the number of nodes in a Fibonacci tree o f degree k is at least Fk the k nd Fibonacci number It follows that a Fibonacci tree with n nodes has degree O 􀀀log n More generally each node has degree O 􀀀log n which f o l l o ws by considering the Fibonacci tree formed by this node and its descendants Assume now that we have a Fibonacci heap and we want to perform INSERT DELETEMIN and DECREASEKEY operations In each case we will rst produce a heap that satis es the Fibonacci property at all non root nodes we will then give a pro cedure that restores the stronger property at the root 􀀀a INSERT Add the new node x as a child of r 􀀀b DELETEMIN Of course we d o n o t w ant to delete the root but the minimal real element Find the child of the root with the smallest key delete it and make its children have the root as their new parent 􀀀c DECREASEKEY Suppose that we w ant to decrease the key of a node v If v is a child of the root simply decrease the key Otherwise let vv v tr be the path connecting v to the root Delete the edge connecting v to its parent v and let v become a child of the root The resulting tree satis es the heap condition even with the decreased key Moreover condition is satis ed by all non root nodes except possibly by v the grandparent o f v U n til condition is satis ed at all non root nodes x the violation at vj by making vj a c hild of the root After at most t steps we obtain a tree that satis es for all non root nodes 􀀀d For each of the three operations we nish by restoring property To do this we look at the degrees of the roots children and assume that two c hildren u and v have th e same degree t Suppose that the key of u is no more than the key of v th e n w edelete the edge vr and make v a c hild of u W e w i l l s h o w that property remains valid at every non root This is trivial for all nodes except u To see that it holds for u consider any s If st then u has the same children with degree at most s as before and so their number is at m ost s For s tu now has at most s children altogether 􀀀It will be important that a nearly identical argument applies even if a child of v were deleted)􀀀* If we nd two c hildren of the root with the same degree then we can transform the heap into one where is still valid at all non roots and the root has lower degree We repeat this until all children of the root have d i e r e n t degrees then is trivially satis ed at the root There are two p o i n ts to clarify (H ow do w e know in􀀀 c how m anyedges vivi must be deleted To c heck condition for each vi would take t o o m uch t i m e Instead we will classify each node as either safe or unsafe If a node is safe then deleting one of its children will not violate at a non root node In contrast classifying a node as unsafe implies only that we are not sure if such a violation would occur Thus we can always classify the root and its children as safe In particular each newly inserted node is safe We shall reclassify a node in only two cases 􀀀i If an unsafe node becomes a child of the root 􀀀in a DELETEMIN or DECREASEKEY operation then it is reclassi ed as safe 􀀀ii If a safe node dierent from the root loses a child 􀀀in a DECREASEKEY operation then it is reclassi ed as unsafe It follows that in the DECREASEKEY operation we delete all edges of the path vv v tr up to the rst safe node vj and make vv j children of the root We reclassify vj as unsafe and vv j as safe Note that in the parenthetical remark we h a ve already indicated that when r gets a new grandchild v in step 􀀀d it is correct to still classify v as safe In performing d how d o w e nd those children of the root with the same degree To sort the degrees would be too time consuming We wish to perform 􀀀d in Od steps where d is the degree of the root after performing steps 􀀀a 􀀀c For each n o d e w e can always store its current degree in an array We w i l l a l s o m a i n tain an array a where ak kd indicates the name of a child of the root of degree k if one exists This array is not changed during steps 􀀀a 􀀀c but is updated during step 􀀀d instead It is trivial to update a to re$ect the deletion of a child of the root To update a for the new children of the root added during steps 􀀀a 􀀀c we consider them one at a time To update a to re$ect the next child u if u has degree k thenwe check if ak contains the name of a node If not we let ak u If it already contains the name of a child v then w e m akeoneof u and v the child of the other and update ak accordingly This creates a child of degree k which w e m ust then be checked with ak and so forth Since each collision of two c hildren with the same degree causes the degree of r to decrease there are fewer than d collisions overall and so the new children are added in Od t i m e In fact if adding t children causes c collisions the total work of step 􀀀d is proportional to tc We m ust still bound the time needed to perform these operations It is easy to see from Lemma that INSERT and DELETEMIN operations take O 􀀀log n steps But a DECREASEKEY operation may take enormous time) For example if the 􀀀Fibonacci tree is a single path from the root with all nodes but the root and its child unsafe then it takes about n steps to decrease the key of the bottom node Furthermore if the root has roughly log n children then adding just a single child of the root could take roughly log n steps The remedy is a book keeping trick called amortization of costs Imagine that we maintain the Fibonacci heap as a service The customer may order any of the INSERT DELETEMIN and DECREASEKEY operations For each operation we o u g h t t o c harge him the actual cost say a c e n t for each step But suppose that we also require that he pay a deposit of one dollar for each unsafe node that is created and a deposit of cents for each c hild of the root that is created If either the number of unsafe nodes or the numb e r of children of the root decreases the appropriate deposit is refunded With this billing system an INSERT or DELETEMIN operation still costs only O 􀀀log n cents but now we can bound the cost 􀀀to him of a DECREASEKEY operation Let t be thenumber of n o d e s t o b e m a d e c hildren of the root this is at most one larger than the number of unsafe nodes becoming safe Since in step 􀀀c at most one node becomes unsafe the customer then gets a net refund of at least t cents The actual cost of step 􀀀c is proportional to t certainly at most t The actual cost of step 􀀀d is proportional to tc certainly at most tc However in step 􀀀d the customer also gets a refund of c cents The total cost to the customer of steps 􀀀c and 􀀀d is at most dollars with this billing system a DECREASEKEY operation costs only a constant a m o u n t Summarizing we h a ve shown the following theorem Theorem In a Fibonacci heap performing n INSERT n DELETEMIN and m DE CREASEKEY operations takes On log nm steps For our original problem we get the following result Theorem Dijkstras algorithm can be implemented using Fibonacci heaps in On log nm steps b Shortest spanning trees and the UNION FIND problem Many of the data structures discussed in the previous subsection can also be used in computing a shortest spanning subtree of a graph In particular Fibonacci heaps can be used to implement Prims algorithm to run on a connected graph G with n nodes and m edges in Om n log n time However in some cases we m a y already know the sorted order of the lengths of the edges or can nd this sorted order extremely quickly such as when the lengths are known to be small integers In these cases we can obtain an even more ecient algorithm by using Kruskals algorithm implemented with a data structure with surprising combinatorial complications For the following discussion assume that the sorted order of the edge lengths is known in advance Kruskals algorithm is very simple it takes the edges one by one in the given sorted order and it adds the next edge to a set T if it does not form a circuit with the edges already in T otherwise it disposes of the edge This seems to take m steps except that we must check whether the new edge forms a circuit with T Let uv be the edge considered To search T for a uv ' path would be too time consuming it would lead to an O mn implementation of Kruskals algorithm We can do better by maintaining the partition fVV kg of VG induced by t h e connected components of the graph VG T Each iteration amounts to checking whether u and v belong to the same class if not we add uv to T Furthermore updating the partition is simple adding uv to T will cause the two classes containing u and v to merge To implement Kruskals algorithm e ciently w e m ust therefore nd a good way t o store a partition of VG so that the following two operations can be performed eciently FIND Given an element u return the partition class containing u UNION Given two partition classes replace them by their union We assume that each partition class has a name and for our purposes it will be convenient to use an arbitrary element of the class to name the partition class We shall call this element t h e boss In a UNION operation we can keep either one of the old bosses as the new boss Kruskals algorithm uses m FIND operations and n UNION operations A trivial way to implement a UNION FIND structure is to maintain a pointer for each element p o i n ting to the boss of its class A FIND operation is then trivial it takes only one step On the other hand to do a UNION operation we m a y h a ve to re direct almost n p o i n ters which yields an On implementation of Kruskals algorithm This is unsatisfactory for sparse graphs and so we m ust do the UNION operation more economically An almost trivial observation already yields a lot when merging two classes we re direct the pointers in the smaller class We call this rule selection by size To estimate the number of steps needed when using this rule observe that whenever a pointer is re directed the size of the class containing it gets at least doubled Hence each pointer is redirected at most log n times The total number of steps spent on UNION operations is therefore On log n andwe get an Om n log n implementation of Kruskals algorithm For mn log n this is optimal To be able to do better for really sparse graphs 􀀀eg with a linear number of edges we use a more sophisticated way t o k eep track of the boss We shall maintain a rooted tree on each class with the boss as its root Each UNION operations then takes only constant time we m a k e one boss the child of the other But this makes the FIND operation more expensive we have to w alkup in the treetotheroot soitmay take as m uch tim e as the height of the tree This suggests that we should keep the trees short We can use an analogue to the selection by size rule called selection by height when merging the two trees if r is the root of greater height then it is made the parent o f r the root of the other tree This increases the height only if the two trees had the same height Of course it is time consuming to compute the height of the trees at each UNION operation but we can maintain the height hv foreach node v This is easily updated it changes only if the union of two trees is performed and the roots have hr hr then is added at the new root It is easy to verify by induction that the number of elements in hr a tree w ith root r is at least Hence hr log n for every r and the cost of a FIND operation is O 􀀀log n This does not yet yield any i m p r o vement in the implementation of Kruskals algorithm But we can use another idea called path compression Suppose thatwe perform a FIND operation which i n volves traversing a fairly long path vv kr Then we can traverse this path again and make each vi the child of the root This doubles the numb e r of steps but the tree becomes shorter We combine this idea with a variant of selection by height called selection by rank For each element v w e m a i n tain a numb e r v called its rank The rank of each n o d e i s initially if two trees with roots r and r are merged where r r we m a k e r a child of r and update by setting r if vr and rr v v otherwise A path compression does not change The numb e r v is no longer the height o f v but it will be an upper bound on the height Moreover the number of elements in a tree with v root v is still at least We shall need the following generalization of this fact which also follows by induction Lemma The number of elements v with vt is at most n t For each leaf vv is strictly increasing along any path to the root Note that this guarantees that the height of the tree is at most log n Tarjan showed that using selection by rank with path compression reduces the cost substantially the average cost of a FIND operation grows only very v ery slowly Let us recall Ackermans function from Chapter First we de ne a series of func tions fi IN IN by the double recurrence fnn fi i fi nfi fi n n Thus fn fn is roughly a tower of n s and so on Ackermans function is the diagonal An fn n This grows faster than any fi and in fact faster than any primitive recursive function The inverse Ackerman function n is de ned by n minfkAk ng This function grows extremely slowly eg slower than log log n or log n We shall also need to introduce inverse functions i of the fi de ned by i n m ax fkfi kn g The de nition is made so that for xed n i n is strictly decreasing as a function of i until it reaches Tarjans result in a slightly weakened form is as follows Theorem In a rooted forest with n elements using selec t i o n b y r ank and path compression m FIND operations and at most n UNION operations take Onm n steps Proof A UNION operation takes only a constant n umber of steps To analyze the FIND operation we rst develop a few tools For each non root node v le t v denote its parent We de ne the level of a node v as the least i for which vv a root is on ii level 􀀀Note that if i v i v then i v i v Initially e a c h node is therefore on level When a node becomes a non root it then reaches a positive level Note that from this step on v does not change The value v can change in only two w ays v may get a new parent from a path compression or v has the same parent and yet v 'c hanges 􀀀from a UNION operation In either case v increases Hence the level of the node v can only increase with time On the other hand the level of a node remains very small it is bounded by the least i for which i n i which is easily seen to be at most n which i s On Let vv kr be a path that is being compressed where r is a root The cost of this compression is proportional to k using the charging analogy again let us say a t most k dollars Consider a node vj jk on the path and let i be its level If i r i vj then charge one dollar to the node Otherwise charge one dollar to the customer How m uch d o w e c harge to the customer per path compression If he is charged for a node vj at level i t h e n b y the monotonicity o f i and w e see that i vj i vji r This implies that vj v k r are at level i or lower i e vj is the last node at level i on the path So the customer gets charged for at most one node at each level which is a total charge of On For m path compressions this is a total of Om n How m uch c harge is left on the nodes While a node v stays on level i the value i v increases whenever v is charged a dollar and so the total charge it accumulates is bounded by the maximum value i v can attain Note that i v i v by the de nition of level i and so from the de nition of i we have vfii vfi fii vfi fii v fi v and hence vv i So the charge accumulated by a n o d e v while at level i is at most v and since v never decreases we can use the nal value in this bound Adding this over all nodes we can use Lemma to show that the total contribution of level i to the charges to the nodes is at most XX n vnt n t vt Since there are On levels the total charge to the nodes is On n Corollary Kruskals algorithm with pre sorted edges can be implemented in Om n steps For a discussion of other implementations of Kruskals algorithm and its relatives see Tarjan Cryptography and pseudorandom numb e r s Let f fg fg be a one to one function and assume that this function can be evaluated in polynomial time Can the inverse function be evaluated in polynomial time We dont know the answer but it is quite likely that the answer is in the negative there are some suspected examples 􀀀and some constructions that have been disproved It turns out that such oneway functions and their extensions could be used in various important applications of complexity theory We examine some of these applications and constructions a Cryptography The basic goal of cryptography is to provide a means for private communication in the presence of adversaries Until fairly recently cryptography has been more of an art than a science No guarantees were given for the security level of the codes and in fact all the classical codes were eventually broken Modern cryptography has suggested ways to use complexity theory for designing schemes with provable levels of security We will not be able to discuss in detail or even mention most of the results here We i n tend rather to give a$ a vor of the problems considered and the results proved The interested reader is referred to the surveys by R i v est Goldreich Gold wasser or to the special issue of SIAM Journal on Computing 􀀀April on cryptography A traditional solution uses secret key crypto systems Suppose that two parties wish to communicate a message M a string of s and s of length n and they agree in advance on a secret key K a string of s and s of the same length as M They send the encrypted message CMK instead of the real message M where denotes the componentwise addition over GF This scheme is provably secure in the sense that assuming the key K is kept secret an adversary can learn nothing about the message by i n tercepting it every string of length n is equally likely to be the message encoded by the string C Unfortunately i t i s v ery inconvenient to use this system since before each transmission the two parties must agree on a new secret key In the paper that founded the area of modern cryptography Die and Hellman suggested the idea of public key crypto systems They proposed that a transmission might be suciently secure if the task of decryption is computationally infeasible rather than impossible in an information theoretic sense Such a w eaker assumption might m a k e i t possible to securely communicate without agreeing on a new secret key every time and also to achieve a v ariety of tasks previously considered impossible We illustrate the idea of security through intractability b y a simple example Assume that you have a bank account that can be accessed electronically by a password If the password is long enough and you keep it safely then this is secure enough Except that the programmer of the computer may inspect the memory learn your password and then access your account It would seem that there is no protection against this the computer has to remember the password and a good hacker can learn anything stored in the computer But the computer does not have t o k n o w y our password) When you open your account you rst generate a Hamiltonian circuit H on say nodes and then add edges arbitrarily to obtain a graph G The computer of the bank will only store the graph G while your password is the code of a Hamiltonian circuit H When you punch i n y our password the computer checks whether it is the code of a Hamiltonian circuit in G an d lets you access the account i f i t i s F or you the Hamiltonian circuit functions like a password in the usual sense But what about the programmer He can learn the graph G but to access your ac count he should specify a Hamiltonian circuit of G w h i c h is a computationally intractable task This intractability protects your account) The crucial point h e r e i s t h a t g i v en a Hamiltonian circuit it is easy to construct a graph containing it but given a graph it can be quite hard to nd a Hamiltonian circuit in it Unfortunately it is easy to nd a Hamiltonian circuit in most graphs and there is no way known to produce graphs for which nding the Hamiltonian circuit is expected to be dicult These considerations motivate the following de nition A oneway function is a one to one function f fg fg such that f can be computed in polynomial time but no polynomial time algorithm can invert f on even a polynomial fraction of the instances of length n Given a one way function f w e can choose an x fg as our password and store the value fx in the computer The length of the word chosen is the security parameter of the scheme This is indeed done in practice 􀀀The above s c heme with Hamiltonian circuits leads to a somewhat weaker notion a one way relation but for most applications we need a one way function The password scheme above is just a simple example of what can be achieved by a publickey cryptosystem This can have a n y n umber of participants The participants agree on an encryption function a decryption function and a security parameter n Messages to be sent are divided into pieces of length n The system functions as follows (E a c h participant should randomly choose a public encryption key E and a corresponding secret decryption key D depending on the security parameter n A directory of the public keys is published There must be a deterministic polynomial time algorithm that given a message M of length n and an encryption key E produces the encrypted message EM Similarly there must exist a deterministic polynomial time algorithm that given a message M of length n and a decryption key D produces the decrypted message DM It is required that for every message MDEM M and the crucial security requirement One cannot eciently compute DM without knowing the secret key D More precisely f o r e v ery constant c and suciently large n the probability that a 􀀀randomized polynomial time algorithm using the public key E but not the private key D can decrypt c a randomly chosen message of length n is less than n When a user named Bob wants to send a message M to another user named Alice he looks up Alices public key EA in this directory and sends her the encrypted message EA M By the assumptions only Alice can decrypt this message using her private key DA The question is how d o w e nd such encryption and decryption functions The basic ingredient of such a system is a trapdoor function The encryption function E fo r a xed participant m ust be easy to compute but hard to invert ie a one way function but in order for a one way function to be useful in the above s c heme we need a further feature it has to be a trapdoor function which is a  variable function like+ i n t h e nnn n scheme above fgfg fg such that for every E fg fE is one to one and easily computable but its inverse is dicult to compute unless one knows the key D belonging to E Given the present state of complexity theory there is little hope to prove that any particular function is one way or trapdoor 􀀀or even that one way functions exist or that a public key crypto system satis es the last requirement a b o ve Note that the existence of a one way function would imply that P NP Therefore a more realistic hope would be to prove the security of a crypto system based on the assumption that P NP H o wever this seems to be quite dicult for two reasons Complexity theory is mainly concerned with worst case analysis For the purpose of cryptography a verage case analysis and a corresponding notion of completeness 􀀀such as the one suggested by Levin would be more appropriate Furthermore one way functions lead to languages in NP which h ave a unique witness whereas the nondeterministic algorithms for NP complete problems have s e v eral accepting paths for most instances Over the last ten years several public key crypto systems have been suggested and analyzed Some have been proven secure based on assumptions about the computational diculty of a particular problem 􀀀eg factoring integers or on the more general assump tion that one way functions exist Rivest Shamir and Adleman were the rst to suggest such a s c heme Their scheme is based on the assumed diculty of factoring integers Each user of this scheme has to select a numb e r n that is the product of two random primes Random primes can be selected using a randomized primality testing algorithm since every log n thnumb er is expected to be prime The public key consists of a pair of integers ne such that e is relative prime to n where n denotes the numb e r o f i n tegers less than n relatively prime to n A message M is encrypted by CMe 􀀀mod n The private key consists of integers nd where de m od n and decryption is done by computing Cd M 􀀀mod n Given the prime factorization of n one can nd the required private key d in polynomial time but the task of nding the appropriate d given only n and e is equivalent to factoring Rabin suggested a variation on this scheme in which a n y algorithm for de cryption rather than any algorithm for nding the decryption key can be used to factor an integer The idea is to encrypt a message M by CM 􀀀mod n 􀀀Aslight tech nical problem that has to be overcome before turning this into an encryption scheme is that squaring modulo a product of two primes is not a one to one function but rather is four to one An algorithm that can extract square roots modulo n can be used to factor choose a random integer x and let the algorithm nd a square root y of the integer x mod n with probability the greatest common divisor of xy and n is one of the two primes used to create n Unfortunately the problem of factoring an integer is not known to be NP hard it would be conceptually appealing to suggest schemes that are based on NP complete prob lems Merkle and Hellman and since then several others have suggested schemes based on the subset sum problem The public key of such systems is an integer vector aa a n A message M th a t is a v ectoroflength n is encrypted by the inner product C aM One problem with this scheme is that there does not appear to be a private key that can make the task of decryption easier for the intended receiver Crypto systems based on this idea have built some additional trapdoor information into the structure of the vector a and so the decryption problem is based on a restricted variant of the subset sum problem which is not known to be NP hard Furthermore randomly chosen subset sum problems can be easy to solve In an innovative paper Shamir used Lenstras integer programming algorithm to break the Merkle Hellman scheme that is he gave a polynomial time decryption algorithm that does not need the secret key Since then several other subset sum based schemes have b e e n b r o k en by c l e v er use of the LLL basis reduction algorithm see Chapter The schemes mentioned so far have encrypted messages of length n for some given security parameter n An apparentproblemwiththis approach isthatevenifweprovethat no polynomial time algorithm can decrypt the messages it still might be possible to deduce some relevant information about the message in polynomial time To formalize what it means to exclude this Goldwasser and Micali suggested the following framework for a randomized encryption procedure and its security Suppose that there is a function nm B fg fg and a randomized polynomial time algorithm that for any image Bx produces a value y such that By Bx and y is randomly distributed among all such v alues an m bit message can be encrypted by running this algorithm Intuitively this encoding is secure if for any t wo messages M and M and some pair of codes for them E and E ie BEi Mi i it is impossible to gain any advantage in guessing which message corresponds to each encryption More precisely the randomized encryption based on B is secure if for each pair MM a n y randomized polynomial time algorithm that is used to guess given MM and an unknown random ordering of E and E w h i c h v alue comes from which a r g u m e n t the probability that the algorithm cc answers correctly is On for all but an n fraction of the encryptions for every c Note that if the encryption algorithm is a deterministic polynomial time algorithm then it is not secure since one could simply apply the encryption algorithm to M and M to determine the correspondence Goldwasser and Micali proposed a way t o a c hieve this level of security b y encrypting messages bit by bit How does one encode a single bit A natural solution is to append a number of random bits to the one bit of information and encrypt the resulting longer string While this was later shown to be an eective approach Goldwasser and Micali proposed n a dierent randomized bit encryption scheme based on a function B fg fg and proved its security based on a number theoretic assumption namely on the assumed diculty of the quadratic residuosity problem An integer x is a quadratic residue modulo n if xy 􀀀mod n for some integer y T he quadratic residuosity problem is to decide for given integers n and x whether x is a quadratic residue modulo n If n is a prime then it is easy to recognize if x is a n quadratic residue modulo n e g by computing x modulo n this is or if and only if x is a quadratic residue The quadratic residuosity problem for composite moduli is more dicult One has to be careful however since there is a polynomially checkable necessary condition that could help in certain cases To f o r m ulate this de ne the Legendre symb o l for any prime n by if n jx and x is a quadratic residue mod n x if n jx and n x is not a quadratic residue mod n if njx We h a ve seen above that it is easy to compute the Legendre symbol where n is a prime The Jacobi symb o l is a generalization of the Legendre symbol to composite n but not in the obvious way if np pk 􀀀where the pi are not necessarily distinct primes then k Y xx npi i It cannot be seen from this de nition but the Jacobi symbol can be computed in polyno mial time for any n x Now if n and x are coprime integers then is a necessary condition for x n to be a quadratic residue modulo n but it is not su cient if n is a product of two x primes then exactly half of the residue classes x with are quadratic residues n The Goldwasser Micali encryption scheme is based on the assumption that there is no ecient w ay to obtain further information on the quadratic residuosity o f x mod n It works as follows a public key consists of an integer n that is the product of two large y primes and a quadratic non residue y with The bit is encrypted by a random n quadratic residue r 􀀀mod n the bit is encrypted by a random quadratic non residue of the form ry 􀀀mod n The task of distinguishing encryptions of s from encryptions of s is exactly the quadratic residuosity problem Decryption is easy for the intended receiver who knows the prime factorization of n Yao has extended this result by proving that a secure randomized bit encryption scheme exists if a one way function exists in fact from every one way function one can extract a secure bit The following simple construction was given by Goldreich and Levin Let f fg fg be a length preserving one way function where a function is lengthpreserving if it maps n bit strings into n bit strings for all n De ne a Boolean function by Bx fxx where if n jxj then x and x are the rst and last bn c bits of x and denotes inner product 􀀀If we also want to decode this bit we t a k e a trapdoor function for f Die and Hellman noticed that under a further assumption a public key crypto system can also be used to solve t h e signature problem where each participant w ants a w ay to electronically sign its messages so that no one else can forge it in the sense that each recipient can verify that the message must have been signed by the claimed sender The assumption which is not very restrictive is that D is one to one ie EDM M for each message M In this case the system can be used for signatures in the following way When Bob sends a message M to Alice he can use his private decryption key DB to append the signature DB M after the message M Given such a signature Alice can use Bobs public key EB to convince herself that the message came from Bob exactly as she received it The Rivest Shamir and Adleman scheme has this additional property and therefore can be used for signatures as well b Pseudorandom numb e r s When random numbers are used in algorithms and crypto systems it is essential that the random bits used are unbiased and independent The speed or the reliability of the algorithm and the security of the crypto system depend on the quality of the random numbers used Natural sources of randomness such a s c o i n s or noise diodes are fairly slow in generating random bits On the other hand for both of these applications truly random bits could be replaced by a n y sequence of bits that no polynomial time algorithm can distinguish from truly random bits A pseudorandom number generator takes a seed x a truly random string of length n and expands it to a pseudorandom string y of length nk for some constant k A pseudo random numb e r generator can be subjected to certain statistical tests It passes the next bit test if after k seeing the rst i bits of its output y for some in no polynomial time algorithm can c predict the next bit with probability m o r e t h a n n for any constant c Most computers have built in pseudo random number generators one of the simplest ones is the linear congruential generator 􀀀where the seed consists of integers abm and x and the pseudo random numbers are generated by the recurrence xi axi b 􀀀mod m This is easily shown to fail the next bit test Other more sophisticated pseudo random number generators can also be shown to output inappropriate sequences by clever use of the LLL basis reduction algorithm An example is the binary expansion of algebraic numbers 􀀀where the seed is the polynomial de ning the algebraic numb e r The rst provably secure pseudo random bit generator was developed by Blum and Micali They proved that pseudo random bit generators exist based on the following n paradigm there exist a polynomial time computable permutation F of the set fg and n a function B fg fg su chthat Bx yields a secure bit 􀀀as discussed above but given F xBx can be computed in polynomial time Such a n F is necessarily a one way function B is called the hard core of F The GoldreichLevin construction of a secure bit can be used to show that such a pair of functions exists if a one way function exists by taking Fx fxx for some length preserving one way function f The Blum Micali pseudo random number generator produces the sequence bb k de ned by bi Bxki and xi Fxi where the random seed is used to select the functions used and the initial vector x The de ned pseudo random number generator c a n b e p r o ved to pass the next bit test 􀀀Informally suppose that we h a ve an algorithm that can predict bi Bxki given bb i w e will use this to contradict the fact that B yields a secure bit Note that given just xki w e can compute xki x k and use these values Fxki Fxk to compute the bits bb i in polynomial time hence we can use the assumed procedure to predict bi which is impossible One might w onder whether certain pseudo random number generators pass statistical tests other than the next bit test However Yao proved that if a pseudo random number generator passes the next bit test then it passes any statistical test ie no ran domized polynomial time algorithm can distinguish the generated pseudo random numb e r s from truly random numbers c Zeroknowledge proofs Let us return to our example with the bank account access The programmer of the computer of the bank may b e t r i c ky and store your password after you have u s e d i t once Can you avoid using it at all and only prove to your bank that you have a password 􀀀ie know a Hamiltonian circuit in the graph G without giving any help to nd it 􀀀or mimicking you inany other w ay This question also comes up in some of the above cryptographic applications it might be useful to be able to convince someone that a number is the product of two primes without telling the two primes themselves This is impossible in the classical sense of proofs but interactive proof systems discussed in Chapter make it possible In fact this was one of the motivating examples for Goldwasser Micali and Racko when developing their notion of interactive proof systems Informally a n i n teractive proof of a statement is said to be a zero knowledge proof if the veri er cannot learn anything from the proof except the validity of the statement Before formalizing the notion of zero knowledge proofs let us describe a solution to the bank problem due essentially to M Blum To m a k e it more transparent we imagine another setup suppose that you are giving a talk on Hamiltonian graphs and you show your audience a Hamiltonian graph G F or didactical purposes you want t o c o n vince them that the graph G has a Hamiltonian circuit without showing them the circuit itself This seemingly impossible task can be accomplished using an overhead projector You prepare two transparencies both show the same set VG of nodes in some random position the rst shows the edges of the Hamiltonian circuit C in G the second the remaining edges of G On this second transparency the labels of the nodes are also shown but not on the rst) You place both transparencies on the projector and cover them with a piece of paper then switch on the projector and let the readers choose whether the top sheet or the top two sheets should be removed If only the top sheet is removed the audience sees the graph G politely labelled so that the audience can verify that it is indeed the graph G shown at the beginning If both upper sheets are removed the audience sees a Hamiltonian circuit on jVG j randomly placed nodes in the plane In either case no information is given on how the Hamiltonian circuit lies in the graph G The only information the audience gets is that they see what they expect On the other hand if you want t o c heat and show a graph G that is not Hamiltonian then either your bottom transparency does not show a Hamiltonian circuit with the right number ofnodes or the two transparenciestogetherdo not show theright graph So there is a chance of that you get caught) If you repeat this times a bit boring for a talk but easily done on paper and you dont get caught then the audience can be reasonably certain that G is Hamiltonian your chance of getting away with a non Hamiltonian graph is one in To m a k e the above protocol precise we h a ve to get rid of the physical devices like projectors and transparencies but this can be done using the methods of cryptography discussed above The basic cryptographic tool needed for this is a secure bit encryption scheme You must be able to encrypt a bit so that the audience has no chance to gure out on his own what the bit is but later you can prove which b i t w as encrypted To convince the audience that G has a Hamiltonian circuit you choose a random permutation P and use this permutation to obtain a random isomorphic copy G of the graph G Y ou encode the permutation and the nn bits representing the adjacency matrix of the graph G The audience can choose either to ask for a proof that the encoded graph G is isomorphic to the original or to ask for a proof that G has a Hamiltonian circuit In the rst case you decrypt every encrypted bit thereby providing the permutation P and the graph G In the second case you decrypt only the bits corresponding to edges participating in the Hamiltonian circuit C There are several ways to formalize the notion of zero knowledge proofs The one we shall use is computational zero knowledge We s a y that an interactive protocol is a zeroknowledge protocol if the veri er can generate in randomized polynomial time a sequence of communication whose distribution is indistinguishable in polynomial time from the distribution of the true transcript of the conversation In our example above the audience could predict that if it chooses to see both trans parencies together it will see the given graph with nodes randomly drawn in the plane while if it chooses to see the bottom transparency then it will see a circuit with the right number of unlabelled nodes again randomly drawn in the plane In contrast consider the example of the interactive proof for the graph non isomorphism problem 􀀀Chapter Section At rst sight this seems to be a zero knowledge protocol since so long as the veri er does not deviate from the protocol he always knows the provers next move and hence could generate the conversation himself There are zero knowledge protocols for the graph non isomorphism problem but this pro tocol is not in fact zero knowledge since the veri er can use it to test if a third graph is isomorphic to one of the two in the input 􀀀ie the veri er can gain extra information by deviating from the protocol Goldreich Micali and Wigderson and subsequently but independently under a somewhat stronger assumption Brassard and Crepeau proved the following result Theorem If one way functions exist then every language in NP has a zero knowledge interactive proof Proof To prove that all languages in NP have zero knowledge proofs one merely has to provide a zero knowledge proof for a single NP complete problem We h a ve s k etched such a protocol for the Hamiltonian circuit problem Acknowledgments We w ould like to thank Sha Goldwasser and Avi Wigderson for their helpful suggestions and comments on an earlier draft The research of the second author was supported in part by an NSF Presidential Young Investigator award CCR   with matching support from IBM UPS and Sun and by A i r F orce Contract AFOSR   The research o f the third author was supported in part by Air Force Contract AFOSR   and by a Packard Research F ellowship The second and third authors were both supported in part by the National Science Foundation the Air Force Oce of Scienti c Research and the Oce of Naval Research through NSF grant DMS  References M Ajtai formulae on nite structures Ann Pure Appl Logic A V Aho J E Hopcroft and J D Ullman Data Structures and Algorithms Addison Wesley Reading MA A V Aho J D Ullman and M Yannakakis On notions of information trans fer in VLSI circuits Proceedings of the th Annual ACM Symposium on Theory of Computing A CM Press New York NY N Alon and R B Boppana The monotone circuit complexity of Boolean functions Combinatorica A E Andreev On a method for obtaining lower bounds for the complexity o f individual monotone functions in Russian Dokl Akad Nauk SSSR English transl Soviet Math Dokl L Babai P F rankl and J Simon Complexity classes in communication complexity theory Proceedings of the th Annual IEEE Symposium on Foundations of Computer Science IEEE Computer Society Press Washington DC L Babai N Nisan and M Szegedy Multiparty protocols and logspace hard pseu dorandom sequences Proceedings of the st Annual ACM Symposium on Theory of Computing A CM Press New York NY M Blum and S Micali How to generate cryptographically strong sequences of pseudo random bits SIAM J Comput G Brassard and C Crepeau Non transitive transfer of con dence a perfect zero knowledge protocol for SAT a n d b e y ond Proceedings of the th IEEE Symposium on Foundations of Computer Science IEEE Computer Society Press Washington DC B Chor and O Goldreich Unbiased bits from sources of weak randomness and probabilistic communication complexity Proceedings of the th Annual IEEE Sympo sium on Foundations of Computer Science IEEE Computer Society Press Washington DC W Die and ME Hellman New directions in cryptography IEEE Trans Inform Theory M L Fredman and R E Tarjan Fibonacci heaps and their uses in improved network optimization algorithms J Assoc Comput Mach R Freivalds Fast probabilistic algorithms in Mathematical Foundations of Com puter Science 􀀀ed J Becvar Lecture Notes in Computer Science Springer 􀀀Berlin M Furst J B Saxe and M Sipser Parity circuits and the polynomial time hier archy Math Systems Theory O Goldreich Randomness interactive proofs and zero knowledge a survey i n The Universal Turing Machine A Half Century Survey 􀀀ed R Herken Kammerer Unverzagt Hamburg Berlin O Goldreich and LA Levin A hard core predicate for all one way functions Proceedings of the st Annual ACM Symposium on Theory of Computing A CM Press New York NY O Goldreich S Micali and A Wigderson Proofs that yield nothing but their valid ity and a methodology of cryptographic protocol design Proceedings of the th Annual IEEE Sympo s i u m o n F oundations of Computer Science IEEE Computer Society Press Washington DC S Goldwasser Interactive proof systems in Computational Complexity Theory 􀀀ed J Hartmanis AMS Symposia in Applied Mathematics AMS 􀀀Providence S Goldwasser and S Micali Probabilistic encryption J Comput System Sci S Goldwasser S Micali and C Racko The knowledge complexity o f i n teractive proof systems SIAM J Comput G H Gonnet Handbook of Algorithms and Data Structures Addison Wesley Lon don M Grotschel L Lovasz and A Schrijver The ellipsoid method and its consequences in combinatorial optimization Combinatorica A Hajnal W Maass and G Turan On the communication complexity o f g r a p h properties Proceedings of the th Annual ACM Symposium on Theory of Computing ACM Press New York NY B Halstenberg and R Reischuk On dierent modes of communication Proceedings of the th Annual ACM Symposium on Theory of Computing A CM Press New York NY J Hastad Almost optimal lower bounds for small depth circuits Proceedings of the th Annual ACM Symposium on Theory of Computing A CM Press New York NY M Karchmer and A Wigderson Monotone circuits for connectivity require super logarithmic depth SIAM J Discrete Math L Levin Average case complete problems SIAM J Comput B Lindstrom Determinants on semilattices Proc Amer Math Soc R J Lipton and R Sedgewick Lower bounds for VLSI Proceedings of the Annual ACM Symposium on Theory of Computing A CM Press New York NY th L Lovasz Communication complexity a survey in Paths Flows and VLSI 􀀀ed B Korte L Lovasz A Schrijver Algorithms and Combinatorics Springer L Lovasz and M Saks Lattices Mobius functions and communication complexity Proceedings of the th Annual IEEE Symposium on Foundations of Computer Science IEEE Computer Society Press Washington DC L Lovasz and M Saks Lattices Mobius functions and communication complexity K Mehlhorn and E M Schmidt Las Vegas is better than determinism in VLSI and distributed computing Proceedings of the th Annual ACM Symposium on Theory of Computing A CM Press New York NY R C Merkle and M Hellman Hiding information and signatures in trapdoor knapsacks IEEE Trans Inform Theory V R Pratt The power of negative thinking in multiplying Boolean matrices SIAM J Comput M O Rabin Digitalized Signatures as Intractable as Factorization TR  Labo ratory for Computer Science Massachusetts Institute of Technology Cambridge MA A A Razborov 􀀀a Lower bounds on the monotone circuit complexity of some Boolean functions 􀀀in Russian Dokl Akad Nauk SSSR English trans lation Soviet Math Dokl A A Razborov b A l o wer b o u n d on the monotone network complexity o f the logical permanent 􀀀in Russian Math Zametki English translation Mathematical Notes of the Academy of Sciences of the USSR A A Razborov Lower bounds on the size of bounded depth circuits over a com plete basis with logical addition 􀀀in Russian Math Zametki English translation Mathematica l N o t e s o f t h e A cademy of Sciences of the USSR R Rivest Cryptography i n The Handbook of Theoretical Computer Science Vol ume A Algorithms and Complexity edited by J v an Leeuwen Elsevier Amsterdam R Rivest A Shamir and Adleman A method for obtaining digital signatures and public key cryptosystems Comm ACM A Shamir A polynomial time algorithm for breaking the basic Merkle Hellman cryptosystem Proceedings of the th Annual IEEE Symposium on Foundations of Computer Science IEEE Computer Society Press Washington DC R Smolensky Algebraic methods in the theory of lower bounds for Boolean circuit complexity Proceedings of the th Annual ACM Symposium on Theory of Computing ACM Press New York NY V Strassen Gaussian elimination is not optimal Numer Math E Tardos The gap between monotone and non monotone circuit complexity i s exponential Combinatorica R E Tarjan Eciency of a good but not linear set union algorithm J Assoc Comput Mach R E Tarjan Data Structures and Network Algorithms CBMSNSF Regional Conf Series in Applied Math SIAM Philadelphia H S Wilf Hadamard determinants Mobius functions and the chromatic numb e r of a graph Bull Amer Math Soc M Yannakakis Expressing combinatorial optimization problems by linear pro grams Proceedings of the th Annual ACM Symposium on Theory of Computing ACM Press New York NY A C Yao Theory and applications of trapdoor functions Proceedings of the th Annual IEEE Symposium on Foundations of Computer Science IEEE Computer Soci ety Press Washington DC A C Yao Lower bounds by probabilistic arguments Proceedings of the th Annual IEEE Sympo s i u m o n F oundations of Computer Science IEEE Computer Society Press Washington DC A C C Yao Separating the polynomial time hierarchy b y oracles Proceedings of the th Annual IEEE Symposium on Foundations of Computer Science IEEE Com puter Society Press Washington DC