next up previous contents
Next: About this document ... Up: Boole függvények számítási bonyolultsága Previous: Explicit Ramsey-gráf konstrukciók


H. L. Abbott.
A note on Ramsey's theorem.
Canad. Math. Bull., 15:9-10, 1972.

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

A. Andreev.
On a method for obtaining lower bounds for the complexity of individual monotone functions.
Dokl. Akad. Nauk SSSR, 282(5):1033-1037, 1985.

L. Babai and P. Frankl.
Linear algebra methods in combinatorics.
Department of Computer Science, The University of Chicago, September 1992.
preliminary version.

L. Babai and V. Grolmusz.
A new family of explicit Ramsey graphs.
submitted for publication, 1999.

L. Babai, N. Nisan, and M. Szegedy.
Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs.
J. Comput. System Sci., 45:204-232, 1992.

L. Babai, H. Snevily, and R. M. Wilson.
A new proof for several inequalities on codes and sets.
Journal of Combinatorial Theory, Series A, 71:146-153, 1995.

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 A. Maciel.
Upper and lower bounds for some depth-3 circuit classes.
Comput./ Complex./, 6(3):235-255, 1997.

R. Beigel and J. Tarui.
Computational Complexity, 4(4):350-366, 1994.

J. Bruck and R. Smolensky.
Polynomial threshold functions, AC0 functions and spectral norms.
In Proc. 32nd Ann. IEEE Symp. Found. Comput. Sci., pages 632-641, 1991.

A. K. Chandra, M. L. Furst, and R. J. Lipton.
Multi-party protocols.
In Proc. 15th Ann. ACM Symp. Theor. Comput., pages 94-99, 1983.

S. Cook.
The complexity of theorem prooving procedures.
In Proc. 3rd Ann. ACM Symp. Theor. Comput., 1971.

P. Erdős and G. Szekeres.
A combinatorial problem in geometry.
Composition Math., 2:464-470, 1935.

P. Frankl.
A constructive lower bound for Ramsey numbers.
Ars Cominatorica, 3:297-302, 1977.

P. Frankl.
Constructing finite sets with given intersections.
Ann. Disc. Math., 17:289-291, 1983.

P. Frankl and R. M. Wilson.
Intersection theorems with geometric consequences.
Combinatorica, 1(4):357-368, 1981.

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

R. L. Graham, M. Grötschel, and e. Lovász.
Handbook of combinatorics.
Elsevier-MIT Press, 1995.

V. Grolmusz.
Superpolynomial size set systems with restricted intersections mod 6 and explicit Ramsey graphs.
Combinatorica, to appear.

V. Grolmusz.
The BNS lower bound for multi-party protocols is nearly optimal.
Inform. and Comput., 112(1):51-54, 1994.

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.
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.

V. Grolmusz.
On set systems with restricted intersections modulo a composite number.
In Lecture Notes in Computer Science Vol. 1276, pages 82-90, August 1997.
Journal version to appear in Combinatorica.

V. Grolmusz.
On the power of circuits with gates of low l1 norms.
Theoretical Computer Science A, (188):117-128, 1997.
Also appeared as ECCC Report TR95-046; ftp://ftp.eccc.uni-

V. Grolmusz.
Circuits and multi-party protocols.
Comput. Complexity, 7:1-18, 1998.

V. Grolmusz.
A degree-decreasing lemma for (MOD q-MOD p) circuits.
In Proc. of the ICALP'98, LNCS 1443, pages 215-222, 1998.

V. Grolmusz.
A lower bound for depth-3 circuits with mod m gates.
Inform. Proc. Lett., 67:87-90, 1998.

V. Grolmusz.
Harmonic analysis, real approximation, and the communication complexity of boolean functions.
Algorithmica, 23(4):341-353, 1999.

V. Grolmusz and G. Tardos.
Lower bounds for (MOD p-MOD m) circuits.
In Proc. 39th Ann. IEEE Symp. Found. Comput. Sci., pages 279-289, 1998.
to appear in the SIAM Journal on Computing.

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

J. Hstad and M. Goldmann.
On the power of the small-depth threshold circuits.
Comput. Complexity, 1:113-129, 1991.

J. Kahn, G. Kalai, and N. Linial.
The influence of variables on Boolean functions.
In Proc. 29th Ann. IEEE Symp. Found. Comput. Sci., pages 68-80, 1988.

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

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.

E. Kushilevitz and N. Nisan.
Communication Complexity.
Cambridge University Press, 1997.

N. Linial, Y. Mansour, and N. Nisan.
Constant depth circuits, Fourier transform and learnability.
Journal of the ACM, 40(3):607-620, July 1993.

L. Lovász.
Communication complexity: a survey.
In B. Korte, L. Lovász, H. Prömel, and A. Schrijver, editors, Paths, Flows, and VLSI-Layout, pages 235-265. Springer, 1989.

L. Lovász and M. Saks.
Lattices, Möbius functions, and communication complexity.
In Proc. 29th Ann. IEEE Symp. Found. Comput. Sci., pages 81-90, 1988.

K. Mehlhorn and E. Schmidt.
Las Vegas is better than determinism in VLSI and distributive computing.
In Proc. 14th Ann. ACM Symp. Theor. Comput., pages 330-337, 1982.

Z. Nagy.
A certain constructive estimate for the Ramsey number (in Hungarian).
Matematikai Lapok, 23:301-302, 1972.

N. Nisan.
The communication complexity of threshold gates.
In V. S. D. Miklós and T. Szőnyi, editors, Combinatorics, Paul Erdős is Eighty, Volume I., pages 301-315. János Bolyai Mathematical Society, Budapest, 1993.

N. Nisan and M. Szegedy.
On the degree of Boolean functions as real polynomials.
Comput. Complexity, 4:462-467, 1994.
Appeared also in Proc. 24th Ann. ACM Symp. Theor. Comput., 1992.

F. P. Ramsey.
On a problem of formal logic.
Proc. London Math. Soc., 30:264-286, 1930.

D. K. Ray-Chaudhuri and R. M. Wilson.
On t-designs.
Osaka J. Math., 12:735-744, 1975.

A. Razborov.
A lower bound on the monotone network complexity of the logical permanent, (in Russian).
Mat. Zametki, 37(6):887-900, 1985.

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

A. Razborov.
Lower bounds for the size of circuits of bounded depth with basis (AND, XOR).
Mathematical Notes of the Academy of Science of the USSR, 41(4):333-338, 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.

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.

A. C. Yao.
Some complexity questions related to distributed computing.
In Proc. 11th Ann. ACM Symp. Theor. Comput., pages 209-213, 1979.

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