We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 05 November 2009
In this chapter we describe several other ways to use communication complexity for proving various results on Boolean circuits. These results differ from those in Chapter 10 in that they do not use the connection between the circuit complexity of f and the communication complexity ofthe corresponding relation Rf and in that the circuits considered here are not restricted to use only ∨ and ∧ gates but instead use richer families of gates.
Small Circuits
A Q-circuit is a directed acyclic graph whose gates are taken from a fixed family of gates Q. Each of the gates in the family takes as an input a sequence of bits that are either inputs of the circuit or outputs of previously computed gates and its output is also a bit. The circuit defines a function over {0, 1}m in the natural way. The cost of a circuit here is its size (the number of gates). The results proved in this section can be thought of as an extension of the results proven in Section 9.1 for decision trees (Q-circuits are different than decision trees over Q in that decision trees only apply functions from Q on the input variables). In particular, we get lower bounds for the size of threshold circuits.
Definition 11.1:The Q-circuits complexity of a function f, denoted SQ(f), is the minimum cost of a Q-circuit computing f.
Recall the definition of the measure Dworst (Definition 7.1).
Lemma 11.2: Denote cQ = maxq∈QDworst(q). Then, for all f, SQ(f) ≥ Dworst(f)/cQ.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
