next up previous
Next: About this document ... Up: A Degree-Decreasing Lemma for Previous: The Proof of Theorem


M. Ajtai.
$\sum^1_1$ formulae on finite structures.
Annals of Pure and Applied Logic, 24:1-48, 1983.

D. A. M. Barrington, R. Beigel, and S. Rudich.
Representing Boolean functions as polynomials modulo composite numbers.
Comput. Complexity, 4:367-382, 1994.
Appeared also in Proc. 24th Ann. ACM Symp. Theor. Comput., 1992.

D. A. M. Barrington, H. Straubing, and D. Thérien.
Non-uniform automata over groups.
Information and Computation, 89:109-132, 1990.

R. Beigel and J. Tarui.
In Proc. 32nd Ann. IEEE Symp. Found. Comput. Sci., pages 783-792, 1991.

B. Chor and O. Goldreich.
Unbiased bits from sources of weak randomness and probabilistic communication complexity.
In Proc. 26th Ann. IEEE Symp. Found. Comput. Sci., pages 429-442, 1985.
Appeared also in SIAM J. Comput. Vol. 17, (1988).

M. L. Furst, J. B. Saxe, and M. Sipser.
Parity, circuits and the polynomial time hierarchy.
Math. Systems Theory, 17:13-27, 1984.

V. Grolmusz.
A weight-size trade-off for circuits with mod m gates.
In Proc. 26th Ann. ACM Symp. Theor. Comput., pages 68-74, 1994.

V. Grolmusz.
On the weak \(\mathop{\bmod}m\) representation of Boolean functions.
Chicago Journal of Theoretical Computer Science, 1995(2), July 1995.

V. Grolmusz.
Separating the communication complexities of MOD m and MOD p circuits.
J. Comput. System Sci., 51(2):307-313, 1995.
also in Proc. 33rd Ann. IEEE Symp. Found. Comput. Sci., 1992, pp. 278-287.

J. Hstad.
Almost optimal lower bounds for small depth circuits.
In Proc. 18th Ann. ACM Symp. Theor. Comput., pages 6-20, 1986.

J. Kahn and R. Meshulam.
On mod p transversals.
Combinatorica, 10(1):17-22, 1991.

M. Krause and P. Pudlák.
On the computational power of depth 2 circuits with threshold and modulo gates.
In Proc. 26th Ann. ACM Symp. Theor. Comput., 1994.

M. Krause and S. Waack.
Variation ranks of communication matrices and lower bounds for depth-two circuits having nearly symmetric gates with unbounded fan-in.
Mathematical Systems Theory, 28(6):553-564, Nov./Dec. 1995.

A. Razborov.
Lower bounds for the monotone complexity of some Boolean functions.
Sov. Math. Dokl., 31:354-357, 1985.

A. Razborov.
Lower bounds on the size of bounded depth networks over a complete basis with logical addition, (in Russian).
Mat. Zametki, 41:598-607, 1987.

R. Smolensky.
Algebraic methods in the theory of lower bounds for Boolean circuit complexity.
In Proc. 19th Ann. ACM Symp. Theor. Comput., pages 77-82, 1987.

R. Smolensky.
On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gates.
In Proc. 31st Ann. IEEE Symp. Found. Comput. Sci., pages 628-631, 1990.

M. Szegedy.
Functions with bounded symmetric communication complexity and circuits with MOD m gates.
In Proc. 22nd ANN. ACM SYMP. THEOR. COMPUT., pages 278-286, 1990.

G. Tardos and D. A. M. Barrington.
A lower bound on the MOD 6 degree of the OR function.
In Proceedings of the Third Israel Symosium on the Theory of Computing and Systems (ISTCS'95), pages 52-56, 1995.

J. van Leeuwen, editor.
Handbook of Theoretical Computer Science, volume A, chapter 14. The complexity of finite functions, by R.B. Boppana and M. Sipser.
Elsevier-MIT Press, 1990.

P. Yan and I. Parberry.
Exponential size lower bounds for some depth three circuits.
Information and Computation, 112:117-130, 1994.

A. C. Yao.
Separating the polynomial-time hierarchy by oracles.
In Proc. 26th Ann. IEEE Symp. Found. Comput. Sci., pages 1-10, 1985.

A. C. Yao.
On ACC and threshold circuits.
In Proc. 31st Ann. IEEE Symp. Found. Comput. Sci., pages 619-627, 1990.

Vince Grolmusz