5
$\begingroup$

We consider the size and depth of a circuit under most situations, but recently I read some papers which consider the “width” of a circuit, so I wonder what's the definition of the width of a circuit? I have searched some definitions but they doesn't seem to be well-defined, can you provide a link or a formal definition of the width for a circuit (you can take Yao's garbled circuits as an example)?

$\endgroup$
3
$\begingroup$

The width of a circuit is in some sense related to concept of circuit depth which you appear to already be familiar with. To understand these concepts it is very helpful to think about the graphic representation of circuits in the form of circuit diagrams. I drew an example of such a diagram here:

example boolean circuit

The depth of a circuit is loosely speaking the number of layers we can partition the circuit into so all gates in layer $i$ can be evaluated if we have the output of all gates in layers $0,\ldots,i-1$. The diagram above is a circuit with three layers, i.e., the circuit has depth three.

On the other hand, the width of the circuit is then the number of gates in the layer with the most gates. So in the example diagram the width is also three because the top layer has three gates.

In the field of secure computation (including Yao circuits) the width of the circuit is typically interesting because it says something about how parallelizable the evaluation of a circuit is. I.e., circuits with wide layers parallelize better.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I just noticed the top three arrows of the diagram does not really make sense as the gates should take two inputs each. However, just ignore them at it should be fine :). $\endgroup$ – Guut Boy Aug 2 '16 at 8:42
2
$\begingroup$

From Adaptively Secure Garbled Circuits from One-Way Functions:

Note that, if we think of the circuit as representing a Turing Machine or RAM computation, then the width w of the circuit corresponds to the maximum of the input size n, output size m, and space complexity s of the computation.

The space complexity indicates how much space (memory, usually main memory, thus RAM) is required to be able to execute the algorithm and includes the size of the input.

Basically the with is the maximum size of the state of an algorithm, where the first state is the input and the final state is the output of the algorithm.

Usually these kind of measurements are represented by the number of bits or bytes, but it could also be used with other units such as blocks.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Note that'you'd probably only consider the smallest amount memory necessary to represent the maximum state (as you'd be able to represent the state with any amount of memory the same size or higher) :) $\endgroup$ – Maarten Bodewes Aug 1 '16 at 19:26
  • $\begingroup$ Thanks @Maarten! Actually my question was arised from this paper, now I think it is more convenient for me to consider the width of a circuit using the decomposable circuit. $\endgroup$ – CryptoLover Aug 2 '16 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.