CIRCUIT LOWER BOUNDS A LA KOLMOGOROV

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.