I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned:

Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ such that $(1 / (k + 1))|T| \leq |T_a|, |T^a| \leq (k/(k+1))|T|$ (where $|T|$ denotes the number of leaves of the tree $T$).

I came across the lemma various times during my studies of proof complexity, but I was never able to find the original paper in which it was established:

On time hardware complexity tradeoffs for Boolean functions, by P. M. Spira. Fourth Hawaii International Symp. on Systems Sci., 1971, pp. 525-527.

Does anybody know where I can find it?

Thank you very much!

  • $\begingroup$ what are $T_a$ and $T^a$? $\endgroup$ Mar 4 at 14:26
  • $\begingroup$ Apparently, it’s actually Fourth Hawaii International Conference on System Sciences, cf. books.google.cz/books/about/… . But I do not know how to get hold of it short of finding a physical copy in a library. $\endgroup$ Mar 4 at 14:27
  • $\begingroup$ @mathworker21 Since this is Spira’s lemma, one of those must be the subtree of $T$ rooted at $a$, and the other one whatever is left of $T$ after removing the subtree (possibly leaving $a$ itself in place). The lower and upper bounds apply to both. $\endgroup$ Mar 4 at 14:31
  • $\begingroup$ To add to Emil's answer, hicss.hawaii.edu/resources/proceedings seems to contain information to help you locate a physical copy. It seems IEEE has not indexed proceedings before 1988 (ieeexplore.ieee.org/xpl/conhome/1000730/all-proceedings). If your institutions has some form of IEEE subscription, it might be useful to mention it when you contact the relevant people. $\endgroup$
    – chazisop
    Mar 4 at 16:19
  • 1
    $\begingroup$ UCSD and Oxford and McGill and Hamburg and a few other libraries have a copy, see here $\endgroup$
    – Kaveh
    Mar 5 at 1:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.