In a recent paper, Razborov (in ''Feasible Mathematics II'' (P. Clote
and J. Remmel, Eds.), gave a new combinatorial proof of Hastad's switc
hing lemma (in ''Randomness and Computation'' (S. Micali, Ed.), pp. 14
3-170, 1989) eliminating the probabilistic argument altogether. In thi
s paper we adapt his proof and propose a Kolmogorov complexity-style s
witching lemma, from which we derive the probabilistic switching lemma
as well as a Kolmogorov complexity-style proof of circuit lower bound
s for parity. (C) 1995 Academic Press, Inc.