%%\magnification=\magstep1 %\def\hbn{\hfill\break\noindent} {\centerline{\bf List of publications}} \bigskip {\centerline{ L\'aszl\'o Babai }} \vskip1cm \item{1969} \itemitem{1.} L. Babai: Coloring infinite graphs (Hungarian), Matematikai Lapok, 20 (1969), 141-143. \item{1970} \itemitem{2.} L. Babai: Representation of permutation groups by graphs, in:Combinatorial Theory and its Applications (Proc. Conf. Balatonf\"ured, Hungary, 1969, P. Erd\H os et al. eds.) Bolyai - North-Holland (1970), 55-80. \item{1972} \itemitem{3.} L. Babai: Automorphism groups of planar graphs I, Discrete Math. 2 (1972), 285-307. \item{1973} \itemitem{4.} L. Babai: Groups of graphs on given surfaces, Acta Math. Acad. Sci. Hung. 24 (1973), 215-221. \itemitem{5.} L. Babai, W. Imrich: On groups of polyhedral graphs, Discrete Math. 5 (1973), 101-103. \itemitem{6.} L. Babai, L. Lov\'asz: Permutation groups and almost regular graphs, Studia Sci. Math. Hung. 8 (1973), 141-150. \itemitem{7.} L. Babai, W. Imrich, L. Lov\'asz: Finite homeomorphism groups of the 2-sphere, in: Topics in Topology (Proc. Conf. Keszthely, Hungary 1972, \'A. Cs\'asz\'ar ed. Bolyai - North-Holland (1973), 61-75. \itemitem{8.} L. Babai, A. M\'at\'e: Inner set mappings on locally compact spaces, in: Topics in Topology (Proc. Conf. Keszthely, Hungary 1972, \'A. Cs\'asz\'ar ed. Bolyai - North-Holland (1973), 77-95. \item{1974} \itemitem{9.} L. Babai: Automorphism groups of graphs and edge-contraction, Discrete Math. 8 (1974), 13-20. \itemitem{10.} L. Babai: A remark on contraction of graphs with given group, Acta Math. Acad. Sci. Hung. 25 (1974), 89-91. \itemitem{11.} L. Babai: On the minimum order of graphs with given group, Canad. Math. Bull. 17 (1974), 467-470. \item{1975} \itemitem{12.} L. Babai: Automorphism groups of planar graphs II, in: Infinite and finite sets (Proc. Conf. Keszthely, Hungary, 1973, A. Hajnal et al eds.) Bolyai - North-Holland (1975), 29-84. \itemitem{13.} L. Babai, W. Imrich: Sense preserving groups of polyhedral graphs, Monatshefte Math. 79 (1975), 1-2. \itemitem{14.} L. Babai: Automorphism groups of graphs (Ph. D. dissertation, Hungarian), Hungarian Academy of Sciences 1975, 308 pages. \item{1977} \itemitem{15.} L. Babai: Asymmetric trees with two prescribed degrees, Acta Math. Acad. Sci. Hung. 28 (1977), 193-200. \itemitem{16.} L. Babai: Some applications of graph contractions, J. of Graph Theory 1 (1977), 125-130. \itemitem{17.} L. Babai: Isomorphism problem for a class of point symmetric structures, Acta Math. Acad. Sci. Hung. 29 (1977), 329-336. \itemitem{18.} L. Babai: On the collineation groups of infinite projective and affine planes, J. of Geometry 10 (1977), 138-145. \itemitem{19.} L. Babai: Symmetry groups of vertex transitive polytopes, Geometriae Dedicata 6 (1977), 331-338. \itemitem{20.} L. Babai: On the isomorphism problem, appended to Proc. Conf. FCT'77 (Fundamentals of Computation Theory), Poznan-Kornik 1977 (pp.10) \item{1978} \itemitem{21.} L. Babai: Chromatic number and subgraphs of Cayley graphs, in: Theory and Appl. of Graphs (Y. Alavi and D.R. Lick, eds. ) Springer Lecture Notes in Math. vol. 642 (1978), 10-22. \itemitem{22.} L. Babai: Automorphism group and category of cospectral graphs, Acta Math. Acad. Sci. Hung. 31 (1978), 295-306. \itemitem{23.} L. Babai, P. Frankl: Isomorphisms of Cayley graphs I, in: Combinatorics (Proc. Conf. Keszthely, Hungary, 1976, A. Hajnal and Vera T. S\'os, eds.) Bolyai - North-Holland (1978), 35-52. \itemitem{24.} L. Babai, J. Ne\v set\v ril: High chromatic rigid graphs I, in: Combinatorics (Proc. Conf. Keszthely, Hungary, 1976, A. Hajnal and Vera T. S\'os, eds.) Bolyai - North-Holland (1978), 53-60. \itemitem{25.} L. Babai: Embedding graphs in Cayley graphs, in: Probl. Combinatoires et Theorie des Graphes (Proc. Conf. Paris-Orsay 1976, J-C. Bermond et al., eds.) Centre National de Rech. Sci., Paris (1978), 13-15. \itemitem{26.} L. Babai, P. Frankl: Infinite quasigroups with given regular automorphism groups, Algebra Universalis 8 (1978), 310-319. \itemitem{27.} L. Babai: Infinite digraphs with given regular automorphism groups, J. Combinatorial Theory - B 25 (1978), 26-46. \itemitem{28.} L. Babai, F. Pastijn: On semigroups with high symmetry, Simon Stevin 52 (1978), 73-84 \itemitem{29.} L. Babai: On a conjecture of M.E. Watkins on graphical regular representations of finite groups, Compositio Math. 37 (1978), 291-296. \itemitem{30.} L. Babai: Vector representable matroids of given rank with given automorphism group, Discrete Math. 24 (1978), 119-125. \item{1979} \itemitem{31.} L. Babai: Tournaments with given (infinite) automorphism group, Periodica Math. Hung. 10 (1979), 99-104. \itemitem{32.} L. Babai: Endomorphisms of sub- and factorsemigroups, in: Algebraic theory of semigroups (Proc. Conf. Szeged, 1976, G. Poll\'ak ed.), Colloq. Math. Soc. J. Bolyai 20 (1979), Bolyai - North-Holland 43-50. \itemitem{33.} L. Babai, P. Frankl, J. Koll\'ar, G. Sabidussi: Hamiltonian cubic graphs and centralizers of involutions, Canad. J. Math. 31 (1979), 458-464. \itemitem{34.} L. Babai, L. Ku\v cera: Canonical labelling of graphs in linear average time, in: Proc. 20th Ann. IEEE Symp. on Foundations of Comp. Sci. (1979), 39-46. \itemitem{35.} L. Babai: Monte Carlo algorithms in graph isomorphism testing, Universit\'e de Montr\'eal Tech. Rep. DMS 79-10, 1979 (pp. 42) \itemitem{36.} L. Babai: Long cycles in vertex transitive graphs, J. Graph Theory 3 (1979), 301-304. \itemitem{37.} L. Babai: Spectra of Cayley graphs, J. Comb. Theory B 27 (1979), 180-189. \itemitem{38.} L. Babai, W. Imrich: Tournaments with given regular group, Aequationes Math. 19 (1979), 232-244. \itemitem{39.} L. Babai, P. Frankl: Isomorphisms of Cayley graphs II, Acta Math. Acad. Sci. Hung. 34 (1979), 177-183. \item{1980} \itemitem{40.} L. Babai: On the complexity of canonical labelling of strongly regular graphs, SIAM J. on Computing 9 (1980), 212-216. \itemitem{41.} L. Babai, P. Frankl: On set-intersections, J. Comb. Th.-A 28 (1980), 103-105. \itemitem{42.} L. Babai, M.E. Watkins: Connectivity of infinite graphs having a transitive torsion group action, Archiv der Math. 34 (1980), 90-96. \itemitem{43.} L. Babai, P. Erd\H os, S.M. Selkow: Random graphs isomorphism, SIAM J. on Computing 9 (1980), 628-635. \itemitem{44.} L. Babai: Almost all Steiner triple systems are asymmetric, in: Topics on Steiner Systems (C.C. Lindner and A. Rosa, eds.), Annals of Discrete Math. 7 (1980), 37-39. \itemitem{45.} L. Babai, A. Pultr: Endomorphism monoids and topological subgraphs of graphs, J. Comb. Theory-B 28 (1980), 278-283. \itemitem{46.} L. Babai: Two remarks on the complexity of graph isomorphism testing, in: Proc. West Coast Conf. on Combinatorics, Graph Th. and Computing (P.Z. Chinn and D. McCarthy, eds.), Humboldt State University 1979, Utilitas Math., Winnipeg (1980), 95-99. \itemitem{47.} L. Babai: Finite digraphs with given regular automorphism groups, Periodica Math. Hung. 11 (1980), 257-270. \itemitem{48.} L. Babai: Isomorphism testing and symmetry of graphs, in: Combinatorics 79 (M. Deza and I.G. Rosenberg, eds.), Annals of Discrete Math. 8 (1980), 101-109. \itemitem{49.} M.E. Adams, L. Babai, J. Sichler: Automorphism groups of finite distributive lattices with a given sublattice of fixed points, Monatsh. Math. 90 (1980), 259-266. \item{1981} \itemitem{50.} L. Babai: Kospektrale Graphen mit vorgegebenen Automorphismengruppen, Wissenschaftliche Zeitschr. der Technischen Hochschule Ilmenau 27/4 (1981), 31-37. \itemitem{51.} L. Babai: Some problems on lattice automorphisms, Studia Sci. Math. Hung. 13 (1978), 139-142. \itemitem{52.} L. Babai: On the abstract group of automorphisms, in: Combinatorics (Proc. 8th British Combinatorial Conf., Swansea 1981, H.N.V. Temperley ed.), London Math. Soc. Lecture Note 52 (1981), Cambridge Univ. Press, 1-40. \itemitem{53.} L. Babai: On the order of uniprimitive permutation groups, Annals of Mathematics 113 (1981), 553-568. \itemitem{54.} L. Babai: Moderately exponential bound for graph isomorphism, in: Fundamentals of Computation Theory (Proc. Conf. FCT'81, Szeged, F. G\'ecseg ed.), Lecture Notes in Computer Science 117, Springer 1981. 34-50. \itemitem{55.} L. Babai, D. Duffus: Dimension and automorphism groups of lattices, Algebra Universalis 12 (1981), 279-289. \itemitem{56.} L. Babai: On strong embeddings of categories, in: Universal Algebra (B. Cs\'ak\'any and E.T. Schmidt, eds., Proc. Conf. Esztergom 1977), Coll. Math. Soc. J. Bolyai 29 (1981), North-Holland, pp. 37-51. \itemitem{57.} L. Babai, P.J. Cameron, M. Deza, N.M. Singhi: On sharply edge-transitive permutation groups, J. Algebra 73 (1981), 573-585. \itemitem{58.} Babai L.: Pr\'\i msz\'amok \'es titkos\'\i r\'as (Prime numbers and cryptography, in Hungarian), Term\'eszet Vil\'aga 112. \'evf. 6. sz. (1981), 250--253. \item{1982} \itemitem{59.} L. Babai: On the order of doubly transitive permutation groups, Inventiones Math. 65 (1982), 473-484. \itemitem{60.} L. Babai, C.D. Godsil: On the automorphism groups of almost all Cayley graphs, Eur. J. Comb. 3 (1982), 9-15. \itemitem{61.} L. Babai, J. Ne\v set\v ril: High chromatic rigid graphs II, in: "Algebraic and Geometric Combinatorics" (E. Mendelsohn ed.), Annals of Discr. Math. 15 (1982), 55-61. \itemitem{62.} L. Babai, F.R.K. Chung, P. Erd\H os, R.L. Graham, J. Spencer: On graphs which contain all sparse graphs, in: ``Theory and Practice of Combinatorics'' (A. Rosa, G. Sabidussi, J. Turgeon eds.) Annals of Discrete Math. 12 (1982), 21-26. \itemitem{63.} L. Babai, P. Erd\H os: Representation of group elements as short products, in: ``Theory and Practice of Combinatorics'' (A. Rosa, G. Sabidussi, J. Turgeon eds.) Annals of Discrete Math. 12 (1982), 27-30. \itemitem{64.} L. Babai, D. Yu. Grigor'ev and D. M. Mount: Isomorphism of graphs with bounded eigenvalue multiplicity, in: Proc. 14th ACM Symp. on Theory of Computing, San Francisco 1982, 310-324. \itemitem{65.} L. Babai, P. J. Cameron and P.P. P\'alfy: On the orders of primitive groups with restricted nonabelian composition factors, J. Algebra 79 (1982), 161-168. \itemitem{66.} Babai L., Freud R\'obert, Kunfalvy Rezs\H o: Pr\'\i msz\'amvad\'aszat sz\'am\'\i t\'og\'eppel, (Hunting for prime numbers with a computer, in Hungarian), Term\'eszet Vil\'aga 113. \'evf. 5. sz. (1982), 201--205. \item{1983} \itemitem{67.} L. Babai, E. M. Luks: Canonical labeling of graphs, in: Proc. 15th ACM Symp. Thy. Computing, Boston (1983), 171-183. \itemitem{68.} L. Babai, W. M. Kantor and E. M. Luks: Computational complexity and the classification of finite simple groups, in: Proc. 24th IEEE Symp. Found. Comp. Sci., Tucson AZ (1983), 162-171. \item{1984} \itemitem{69.} L. Babai: Permutation Groups, Coherent Configurations and Graph Isomorphism. D.Sc. Thesis (Hungarian), Hungarian Academy of Sciences, 1984 \itemitem{70.} L. Babai, E. Szemer\'edi: On the complexity of matrix group problems I, in: Proc. 25th IEEE Symp. Found. Comp. Sci., Palm Beach, FL (1984), 229-240. \item{1985} \itemitem{71.} L. Babai: On Lov\'asz' lattice reduction and the nearest lattice point problem, in: Proc. 2nd Ann. Symp. on Theoretical Aspects of Comp. Sci. (STACS 85), Saarbr\"ucken, Springer Lecture Notes in Comp. Sci. 182 (1985), 13-20. (See item 77) \itemitem{72.} L. Babai: Trading group theory for randomness, in: Proc. 17th ACM Symp. on Theory of Computing, Providence RI (1985), 421-429. \itemitem{73.} L. Babai: An anti-Ramsey theorem, Graphs and Combinatorics 1 (1985), 23-28. \itemitem{74.} L. Babai: Arc transitive covering digraphs and their eigenvalues, J. Graph Theory 8 (1985), 363-370. \itemitem{75.} L. Babai, Vera T. S\'os: Sidon sets in groups and induced subgraphs of Cayley graphs, Europ. J. Combinatorics (1985), 101-114. \item{1986} \itemitem{76.} M. Ajtai, L. Babai, P. Hajnal, J. Koml\'os, P. Pudl\'ak, V. R\"odl, E. Szemer\'edi, G. Tur\'an: Two lower bounds for branching programs, Proc. 18th ACM Symp. on Theory of Computing, Berkeley CA 1986, pp. 30--38. \itemitem{77.} L. Babai: On Lov\'asz' lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), 1--14. (full version of item 71) \itemitem{78.} L. Babai: A Las Vegas --NC algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues, Proc. 27th IEEE Symp. on Foundations of Computer Science, Toronto (1986), 303--312. \itemitem{79.} L. Babai, P. Frankl, J. Simon: Complexity classes in communication complexity theory, Proc. 27th IEEE Symp. on Foundations of Computer Science, Toronto (1986), 337--347. \itemitem{80.} L. Babai: On the length of subgroup chains in the symmetric group, Communications in Algebra 14 (1986), 1729--1736. \itemitem{81.} N. Alon, L. Babai, A. Itai: A fast and simple randomized parallel algorithm for the maximal independent set problem, J. of Algorithms 7 (1986), 567--583. \item{1987} \itemitem{82.} L. Babai: On the non-uniform Fisher inequality, Discrete Math. 66 (1987), 303--307. \itemitem{83.} L. Babai, E.M. Luks, \'A. Seress: Permutation groups in NC, in: Proc. 19th ACM STOC, New York 1987, pp. 409-420. \itemitem{84.} L. Babai, \'A. Seress: On the degree of transitivity of permutation groups: a short proof, J. Combinatorial Theory-A 45 (1987), 310-315. \itemitem{85.} L. Babai, G. Tur\'an: The complexity of definig a relation on a finite graph, Zeitschr. f\"ur Math. Logik und Grundl. der Math. 33 (1987), 277--288. \itemitem{86.} L. Babai, P. Hajnal, E. Szemer\'edi, G. Tur\'an, A lower bound for read-once-only branching programs, J. Computer and Sys. Sci. 35 (1987), 153-162. \item{1988} \itemitem{87.} L. Babai, Random oracles separate PSPACE from the polynomial-time hierarchy, Information Processing Letters 26 (1987/88), 51-53. \itemitem{88.} L. Babai, \'A. Seress: On the diameter of Cayley graphs of the symmetric group, J. Combinatorial Theory-A 49 (1988), 175--179. \itemitem{89.} L. Babai, S. Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, J. Computer and Sys. Sci. 36 (1988), 254--276. \itemitem{90.} L. Babai: On the non-uniform Ray-Chaudhuri--Wilson inequality, Combinatorica 8 (1988), 133--135. \itemitem{91.} L. Babai, E.M. Luks, \'A. Seress: Fast management of permutation groups, IEEE FOCS 29 (1988), 272--282. \itemitem{92.} L. Babai, Bettina Just, F. Meier auf der Heide: On the limits of computations with the floor function, Information and Computation 78 (1988), 99--107. \item{1989} \itemitem{93.} L. Babai, N. Nisan, M. Szegedy: Multiparty protocols and Logspace-hard pseudorandom sequences, in: Proc. 21st ACM STOC, Seattle WA 1989, pp. 1--11. (see item 126) \itemitem{94.} L. Babai: The probability of generating the symmetric group, J. Combinatorial Theory A 52 (1989), 148--153. \itemitem{95.} L. Babai, S. Moran: Proving properties of interactive proofs by a generalized counting technique, Information and Computation 82 (1989), 185--197. \itemitem{96.} L. Babai, L. R\'onyai: Computing irreducible representations of finite groups, in: Proc. 30th IEEE FOCS, Research Triangle N.C. (1989), 93-98. (See item 102) \itemitem{97.} L. Babai, W.M. Kantor, A. Lubotsky: Small diameter Cayley graphs for finite simple groups, European J. Comb. 10 (1989), 507-522. \item{1990} \itemitem{98.} L. Babai: E-mail and the unexpected power of interaction, in: Proc. 5th IEEE Structure in Complexity Theory conf., Barcelona 1990, pp. 30-44. (Polish translation: item 151) \itemitem{99.} L. Babai, L. Fortnow, C. Lund: Nondeterministic exponential time has two-prover interactive protocols, in: 31st IEEE FOCS, St. Louis MO, 1990, pp. 16-25. (See item 108) \itemitem{100.} L. Babai, L. Fortnow: A characterization of $\#P$ by arithmetic straight line programs, in: 31st IEEE FOCS, St. Louis MO, 1990, pp. 26-34. (See item 109) \itemitem{101.} L. Babai, G. Hetyei, W.M. Kantor, A. Lubotsky, \'A. Seress: On the diameter of finite groups, in: 31st IEEE FOCS, St. Louis MO, 1990, pp. 857-865. \itemitem{102} L. Babai, L. R\'onyai: Computing irreducible representations of finite groups, Mathematics of Computation 55 (1990), 705-722. (full version of item 96) \itemitem{103.} L. Babai, P. Pudl\'ak, V. R\"odl, E. Szemer\'edi: Lower bounds to the complexity of symmetric Boolean functions, Theoretical Computer Science 74 (1990), 313--324. \itemitem{104.} L. Babai, M. Simonovits, J. Spencer: Extremal subgraphs of random graphs, J. Graph Theory 14 (1990), 599-622. \item{1991} \itemitem{105.} L. Babai, L. Fortnow, L. A. Levin, M. Szegedy: Checking computations in polylogarithmic time, Proc. 23rd ACM STOC, 1991, pp. 21--31. \itemitem{106.} L. Babai, G. Cooperman, L. Finkelstein, E. M. Luks, \'A. Seress: Fast Monte-Carlo algorithms for permutation groups Proc. 23rd ACM STOC, 1991, pp. 90--100. \itemitem{107.} L. Babai: Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd ACM STOC, 1991, pp. 164--174. \itemitem{108} L. Babai, L. Fortnow, C. Lund: Nondeterministic exponential time has two-prover interactive protocols, Computational Complexity 1 (1991), 3--40 (full version of item 99) \itemitem{109} L. Babai, L. Fortnow: Arithmetization: a new method in structural complexity theory, Computational Complexity 1 (1991), 41--67 (full version of item 100) \itemitem{110.} L. Babai, A. J. Goodman, L. Lov\'asz: Graphs with given automorphism group and few edge orbits, Europ. J. Comb. 12 (1991), 185--203. \itemitem{111.} L. Babai, L. Fortnow, N. Nisan, A. Wigderson: {\it BPP}\/ has subexponential simulations unless {\it EXPTIME}\/ has publishable proofs, Proc. 6th Ann. Conf. on Structure in Complexity Theory, IEEE, Chicago 1991, pp. 213--219. \itemitem{112.} L. Babai, G. Cooperman, L. Finkelstein, \'A. Seress: Nearly linear time algorithms for permutation groups with a small base, Proc. ISSAC'91 (Internat. Symp. on Symbolic and Algebraic Computation), Bonn 1991, pp. 200--209. \itemitem{113.} N. Alon, L. Babai, H. Suzuki: Multilinear polynomials and Frankl--Ray-Chaudhuri--Wilson type inequalities, J. Combinat. Theory--A 58 (1991), 165--180. \itemitem{114.} L. Babai: Vertex-transitive graphs and vertex-transitive maps, J. Graph Theory 15 (1991), 587--627. \itemitem{115.} L. Babai, K. Friedl: Approximate representation theory of finite groups, 32nd IEEE FOCS, Puerto Rico 1991, pp. 733--742. \itemitem{116.} L. Babai: Computational complexity in finite groups, in: Proc. Internat. Congress of Mathematicians, Kyoto 1990, Springer-Verlag, Tokyo 1991, pp.1479--1489. \item{1992} \itemitem{117.} L.Babai: Deciding finiteness of matrix groups in Las Vegas polynomial time, in: Proc. 3rd ACM--SIAM Symp. on Discrete Algorithms, Orlando FL, 1992, pp. 33--40. \itemitem{118.} L. Babai: Bounded round interactive proofs in finite groups, SIAM J. Discr. Math. 5 (1992), 88-111. \itemitem{119.} L. Babai, R. Beals, P. Tak\'acsi-Nagy: Symmetry and complexity, Proc. 24th ACM STOC, 1992, Vancouver B.C., pp. 438--449. \itemitem{120.} L. Babai, M. Szegedy: Local expansion of symmetrical graphs, Combinatorics, Probability, and Computing 1 (1992), 1--11. \itemitem{121.} L. Babai, T. Lengyel: A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109--119. \itemitem{122.} L. Babai: Transparent Proofs, FOCUS (MAA Newsletter) 12, No. 3 (June 1992), pp. 1--2. \itemitem{123.} L. Babai: Combinatorial Optimization Is Hard, FOCUS (MAA Newsletter) 12, No. 4 (Sep. 1992), pp. 3/6/18. \itemitem{124} L. Babai, P. Frankl: {\sl Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science}, book, Preliminary version 2, University of Chicago 1992, pp. 216. \itemitem{125.} L. Babai, \'A. Seress: On the diameter of permutation groups, Europ. J. Comb. 13 (1992), 231-243. \itemitem{126} L. Babai, N. Nisan, M. Szegedy: Multiparty protocols, pseudorandom generators for Logspace, and time-space trade-offs, J. Comp. Sys. Sci. 45, No. 2 (special issue) (1992), 204--232 (full version of item 93) \itemitem{127.} L. Babai, G. L. Hetyei: On the diameter of random Cayley graphs of the symmetric group, Combinatorics, Probability, and Computing 1 (1992), 201-208. \itemitem{128.} L. Babai, Vera T. S\'os: Tibor Gallai, 1912--1992. Combinatorica 12 (1992), 371--372. \item{1993} \itemitem{129.} L. Babai: Transparent (holographic) proofs, in: Proc. 10th Ann. Symp. on Theoret. Aspects of Comp. Sci. (STACS'93), W\"urzburg (Germany) 1993, Springer Lect. Notes in Comp. Sci. 665 (1993), 525-534. \itemitem{130.} L. Babai, A. J. Goodman, L. Pyber: On faithful permutation representations of small degree, Comm. Algebra 21 (1993), 1587--1602. \itemitem{131.} L. Babai, A. J. Goodman: Subdirectly reducible groups and edge-minimal graphs with given automorphism group, J. London Math. Soc. 47 (1993), 417--432. \itemitem{132.} L. Babai, R. Beals, D. Rockmore: Deciding finiteness of matrix groups in deterministic polynomial time, Proc. ISSAC'93 (Internat. Symp. on Symbolic and Algebraic Computation), Kiev 1993, ACM Press 1993, pp.117--126. \itemitem{133.} L. Babai, K. Friedl, M. Stricker: Decomposition of *-closed algebras in polynomial time, Proc. ISSAC'93 (Internat. Symp. on Symbolic and Algebraic Computation), Kiev 1993, ACM Press 1993, pp. 86--94. \itemitem{134.} L. Babai, A. J. Goodman: On the abstract group of automorphisms. In: ``Coding Theory, Desing Theory, Group Theory'' (D.~Jungnickel and S.~A. Vanstone, Eds.), Proc. of Marshall Hall Conf., Burlington VT 1990, Wiley 1993, pp. 121--143. \itemitem{135.} L. Babai, E. M. Luks, \'A. Seress: Computing composition series in primitive groups. In: ``Groups and Computation'', (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. in Discr. Math. and Theor. Comp. Sci. Vol 11, A.M.S. 1993, pp. 1--16. %% Workshop on groups and computation, Oct 7-10, 1991. \itemitem{136.} S. Arora, L. Babai, J. Stern, Z. Sweedyk: The hardness of approximate optima in lattices, codes, and systems of linear equations. Proc. 34th IEEE FOCS, 1993, Palo Alto CA, pp. 724--733. \itemitem{137.} R. Beals, L. Babai: Las Vegas algorithms for matrix groups, Proc. 34th IEEE FOCS, 1993, Palo Alto CA, pp. 427--436. \itemitem{138} L. Babai, L. Fortnow, N. Nisan, A. Wigderson: {\it BPP}\/ has subexponential time simulations unless {\it EXPTIME}\/ has publishable proofs, Computational Complexity 3 (1993), 307--318 (full version of item 111) \item{1994} \itemitem{139.} L. Babai, L. Pyber: Permutation groups without exponentially many orbits on the power set, J. Combinat. Theory, Ser. A, 66 (1994), 160--168. \itemitem{140.} L. Babai, H. Oral, K. T. Phelps: Eulerian self-dual codes, SIAM J. Discr. Math. 7 (1994), 325--330. \itemitem{141.} L. Babai: Transparent proofs and limits to approximation. In: Proc. First European Congress of Mathematics (1992), Vol. I, Birkh\"auser Verlag, 1994, pp. 31--91. \item{1995} \itemitem{142.} L. Babai, P. Kimmel, Satyanarayana V. Lokam: Simultaneous messages vs communication. in: 12th Ann. Symp. on Theoretical Aspects of Comp. Sci. (STACS'95), Munich (E. Mayr, C. Puech, eds.), Lect. Notes in Comp. Sci. Vol. 900, Springer 1995, pp. 361-372. \itemitem{143.} L. Babai, H. Snevily, R. M. Wilson: A new proof of several inequalities on codes and sets, J. Combinat. Theory-A 71 (1995), 146-153. \itemitem{144.} L. Babai, G. Cooperman, L. Finkelstein, E. M. Luks, \'A. Seress: Fast Monte Carlo algorithms for permutation groups J. Computer and System Sciences 50 (1995), 296-307. (special issue; full version of item 106) \itemitem{145.} L. Babai: Automorphism groups, isomorphism, reconstruction. Chapter 27 of the {\sl Handbook of Combinatorics}, R.~L. Graham, M. Gr\"otschel, L. Lov\'asz, eds., North-Holland -- Elsevier, 1995, pp. 1447--1540. \item{1996} \itemitem{146.} L. Babai, R. Beals, J-y. Cai, G. Ivanyos, E. M. Luks: Multiplicative equations over commuting matrices, in: Proc. 7th ACM-SIAM Symp. on Discrete Algorithms, 1996, pp. 498--507. \itemitem{147.} L. Babai, A. G\'al, J. Koll\'ar, L. R\'onyai, T. Szab\'o, A. Wigderson: Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs, in: Proc. 28th ACM STOC, 1996, pp. 603--611. \itemitem{148.} L. Babai: In and Out of Hungary: Paul Erd\H{o}s, His Friends, and Times. In: ``Combinatorics: Paul Erd\H{o}s Is Eighty'' (D. Mikl\'os, V.~T.~S\'os, T.~Sz\H{o}nyi, ed.) Vol. 2., J. Bolyai Mathematical Society, Budapest, 1996, pp. 7--95. \itemitem{149.} L. Babai: We stare in disbelief $\ldots$ (Untitled letter on the death of Paul Erd\H{o}s) Combinatorica 16 (1996), p. 452. \itemitem{150.} L. Babai: Paul Erd\H{o}s (1913-1996), SIGACT News 27/4 (1996), 62--65. \itemitem{151} L. Babai: Poczta komputerowa i niezwyk{\l}a moc interakcji, Wiadomo\'sci Matematyczne XXXI (1995), 55-80 (appeared Sep. 1996) {\it (Polish translation of item 98.)} \item{1997} \itemitem{152} L. Babai: The growth rate of vertex-transitive planar graphs. In: Proc. 8th Ann. Symp. on Discrete Algorithms (SODA'97), New Orleans LA, ACM---SIAM 1997, pp. 564--573. \itemitem{153} L. Babai: Randomization in group algorithms: conceptual questions. In: ``Groups and Computation II'' (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. in Discr. Math. and Theor. Comp. Sci. Vol 28, A.M.S. 1997, pp. 1--16. %% Workshop on groups and computation, June 7-10, 1995. \itemitem{154.} L. Babai: Paul Erd\H{o}s and His Influence on the Theory of Computing, SIAM News 30/1 (1997), p.3. \itemitem{155.} L. Babai: Paul Erd\H{o}s (1913--1996): His Influence on the Theory of Computing, in: Proc. 29th ACM Symposium on Theory of Computing, 1997, pp. 383--401. \itemitem{156.} L. Babai, P. Kimmel: Randomized simultaneous messages: solution of a problem of Yao in communication complexity. Proc. 12th IEEE Symp. on Computational Complexity, 1997, pp. 239--246. \itemitem{157.} L. Babai, A. J. Goodman, W. M. Kantor, E.~M. Luks, P.~P. P\'alfy: Short presentations for finite groups, J. Algebra 194 (1997), 79-112. \itemitem{158.} L. Babai, A. Goodman, L. Pyber: Groups without faithful transitive permutation representations of small degree. J. Algebra 195 (1997), 1-29. \itemitem{159.} L. Babai, E.M. Luks, \'A. Seress: Fast management of permutation groups I, SIAM J. Comput. 26 (1997), 1310--1342 (full version of item 91) \itemitem{160.} S. Arora, L. Babai, J. Stern, Z. Sweedyk: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Sys. Sci. 54 (1997), 317--331 (full version of item 136) \itemitem{161.} L. Babai: Communication complexity. In: Math. Foundations of Comp. Sci. 1997, Proc. 22nd Internat. Symp, MFCS'97 (I. Pr{\'\i}vara, P. Ru{\v z}i{\v c}ka, eds.), Lecture Notes in Computer Science, Vol. 1295, Springer 1997, pp. 5--18. \item{1998} \itemitem{162.} L. Babai (organizer), C. Pomerance, P. V\'ertesi: The mathematics of Paul Erd\H{o}s. Notices of the A.M.S. 45/1, January 1998, pp. 19--31. \itemitem{163.} L. Babai: Finite and Transfinite Combinatorics. Part of item 161, pp. 23--28. \itemitem{164.} L. Babai, J. Spencer: Paul Erd\H{o}s (1913--1996). Notices of the A.M.S. 45/1, January 1998, pp. 64--73. \itemitem{165.} L. Babai: Paul Erd\H{o}s just left town. Part of item 163, pp. 66--73. \itemitem{166.} L. Babai: The Forbidden Sidetrip. In: People \&\ Ideas in Theoretical Computer Science (C.~S. Calude, Ed.), Springer 1998, pp. 1--31. \itemitem{167.} L. Babai, T. Hayes, P. Kimmel: The cost of the missing bit: Communication complexity with help. In: 30th ACM STOC, 1998, pp. 673--682. \itemitem{168.} Babai L.: Magyarorsz\'agon \'es a vil\'agban: Erd\H{o}s P\'al, bar\'atai, \'es kora. Term\'eszet Vil\'aga 129 (1998) III. k\"ul\"onsz\'am, pp. 31--36. {\it (Hungarian translation of parts of item 148.)} \item{1999} \itemitem{169.} L. Babai, R. Beals: A polynomial-time theory of black box groups I. In: {\it Groups St Andrews 1997 in Bath, I} (C.M. Campbell, E.F. Robertson, N. Ruskuc, G. C. Smith, eds.), London Math. Soc. Lect. Notes 260, Cambr. U. Press, 1999, pp. 30-64. \itemitem{170.} L. Babai, A. G\'al, A. Wigderson: Superpolynomial lower bounds for monotone span programs. Combinatorica 19 (1999), 301--320. (expanded version of part of item 147) \itemitem{171.} L. Babai, S. Laplante: Stronger separations for random-self-reducibility, rounds, and advice. In: Proc. ``Complexity '99'' (14th Ann. IEEE Conf. on Computational Complexity, Atlanta 1999), IEEE Comp. Soc., 1999, pp. 98--104. \item{2000} \itemitem{172.} L. Babai, I. Pak: Strong bias of group generators: an obstacle to the ``product replacement algorithm.'' In: Proc. 11th Ann. Symp. on Discrete Algorithms (SODA 2000), ACM---SIAM 2000, San Francisco CA, pp. 627--635. \itemitem{173.} L. Babai, P. J. Cameron: Automorphisms and enumeration of switching classes of tournaments. Electronic J. Comb. 7 (2000), \#R38, 24 pp. \item{2001} \itemitem{174.} L. Babai, A. Shalev: Recognizing simplicity of black-box groups and the frequency of ${p}$-singular elements in affine groups. In: Groups and Computation III. Proc. 1999 Workshop at the Ohio State University (W.~M. Kantor and \'Akos Seress, eds.) Ohio State University Mathematical Research Institute Publications 8, deGruyter, Berlin -- New York, 2001, pp. 39--62. \itemitem{175.} L. R\'onyai, L. Babai, Murali K. Ganapathy: On the number of zero-patterns of a sequence of polynomials. J. Amer. Math. Soc. 14 (2001), 717--735. \itemitem{176.} L. Babai, P. Frankl, S. Kutin, D. {\v S}tefankovi{\v c}}: Set systems with restricted intersections modulo prime powers. J. Combinatorial Theory - A 95 (2001), 39--73. \itemitem{177.} L. Babai, T. Hayes, P. Kimmel: The cost of the missing bit: Communication complexity with help. Combinatorica 21 (2001), 455-488 (Expanded version of item 167.) \vskip.7cm {\centerline{\bf Book, chapter of a book, major survey articles}} \bigskip\noindent L. Babai, P. Frankl: {\sl Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science}, book, Preliminary version 2, University of Chicago 1992, pp. 216. \medskip\noindent L. Babai: Transparent proofs and limits to approximation. In: Proc. First European Congress of Mathematics (1992), Vol. I, Birkh\"auser Verlag, 1994, pp. 31--91. \medskip\noindent L. Babai: Automorphism groups, isomorphism, reconstruction. Chapter 27 of the {\sl Handbook of Combinatorics}, R.~L. Graham, M. Gr\"otschel, L. Lov\'asz, eds., North-Holland -- Elsevier, 1995, pp. 1447--1540. \vskip.7cm {\centerline{\bf Lecture notes}} \bigskip\noindent L. Babai: Finite Probability Spaces. (1994. Last update: April 1999.) \medskip\noindent L. Babai: The Fourier Transform and Equations over Finite Abelian Groups. (1989) \vfill\break %% % Submitted/accepted: %\itemitem{***.} L. Babai, A. G\'al, P. Kimmel, Satya V. Lokam: % Communication Complexity of Simultaneous Messages. % SIAM J. Comp. (accepted, Dec 2000) % (Greatly expanded version of item 142.) %\itemitem{***.} L. Babai, P. P. P\'alfy, J. Saxl: % On the number of $p$-regular elements in simple groups. %\itemitem{***} L. Babai, W. M. Kantor, P. P. P\'alfy, \'A. Seress: % Black-box recognition of finite simple groups % of Lie type by statistics of element orders. %\itemitem{} L. Babai, R. Beals, D. Rockmore: % Deciding finiteness of matrix groups in polynomial time, % Israel J. Math. %\itemitem{} L. Babai, M. Szegedy: % Contractions of Cayley graphs %\itemitem{} L. Babai, L.\,A. Levin, L. Fortnow, M. Szegedy: % Transparent proofs (full version of item 105) %\itemitem{} L. Babai, S. Kannan, E. M. Luks: % Bounded round interactive proofs for nonisomorphism % of matrix groups %\itemitem{} L. Babai: % Vertex-transitive graphs, excluded minors, and % hyperbolic geometry % Babai-Beals: The number of orders of permutation groups \vskip1.5cm {\centerline{\bf Popular articles}} \bigskip\noindent \itemitem{1.} Babai L.: Pr\'\i msz\'amok \'es titkos\'\i r\'as (Prime numbers and cryptography, in Hungarian), Term\'eszet Vil\'aga 112. \'evf. 6. sz. (1981), 250--253. \itemitem{2.} Babai L., Freud R\'obert, Kunfalvy Rezs\H o: Pr\'\i msz\'amvad\'aszat sz\'am\'\i t\'og\'eppel (Hunting for prime numbers with a computer, in Hungarian), Term\'eszet Vil\'aga 113. \'evf. 5. sz. (1982), 201--205. \itemitem{3.} L. Babai: E-mail and the unexpected power of interaction, in: Proc. 5th IEEE Structure in Complexity Theory conf., Barcelona 1990, pp. 30-44. {\it Polish translation:} \hangindent=.7in Poczta komputerowa i niezwyk{\l}a moc interakcji, Wiadomo\'sci Matematyczne XXXI (1995), 55-80 (appeared Sep. 1996) \itemitem{4.} L. Babai: Transparent Proofs, FOCUS (MAA Newsletter) 12, No. 3 (June 1992), pp. 1--2. \itemitem{5.} L. Babai: Combinatorial Optimization Is Hard, FOCUS (MAA Newsletter) 12, No. 4 (Sep. 1992), pp. 3/6/18. \itemitem{6.} L. Babai: Probably True Theorems, Cry Wolf? Notices of the A.M.S. 41 (1994) %%*** \itemitem{7.} L. Babai: The Forbidden Sidetrip. In: People \&\ Ideas in Theoretical Computer Science (C.~S. Calude, Ed.), Springer 1998, pp. 1--31. \bigskip {\centerline{\bf Biographies, obituaries, memorial articles}} \bigskip \itemitem{1.} L. Babai, Vera T. S\'os: Tibor Gallai, 1912--1992. Combinatorica 12 (1992), 371--372. \itemitem{2.} L. Babai: In and Out of Hungary: Paul Erd\H{o}s, His Friends, and Times. In: ``Combinatorics: Paul Erd\H{o}s Is Eighty'' (D. Mikl\'os, V.~T.~S\'os, T.~Sz\H{o}nyi, ed.) Vol. 2., J. Bolyai Mathematical Society, Budapest, 1996, pp. 7--95. {\it Partial Hungarian translation:} \hangindent=.7in Magyarorsz\'agon \'es a vil\'agban: Erd\H{o}s P\'al, bar\'atai, \'es kora. Term\'eszet Vil\'aga 129 (1998) III. k\"ul\"onsz\'am, pp. 31--36. \itemitem{3.} L. Babai: Paul Erd\H{o}s (1913-1996), SIGACT News 27/4 (1996), 62--65. \itemitem{4.} L. Babai: We stare in disbelief $\ldots$ (Untitled letter to the death of Paul Erd\H{o}s) Combinatorica 16 (1996), p. 452. \itemitem{5.} L. Babai: Paul Erd\H{o}s and His Influence on the Theory of Computing, SIAM News 30/1 (1997), p.3. \itemitem{6.} L. Babai: Paul Erd\H{o}s (1913--1996): His Influence on the Theory of Computing, in: Proc. 29th ACM Symposium on Theory of Computing, 1997, pp. 383--401. \itemitem{7.} L. Babai (organizer), C. Pomerance, P. V\'ertesi: The mathematics of Paul Erd\H{o}s. Notices of the A.M.S. 45/1, January 1998, pp. 19--31. \itemitem{8.} L. Babai: Finite and Infinite Combinatorics. Part of item 7, pp. 23--28. \itemitem{9.} L. Babai, J. Spencer: Paul Erd\H{o}s (1913--1996). Notices of the A.M.S. 45/1, January 1998, pp. 64--73. \itemitem{10.} L. Babai: Paul Erd\H{o}s just left town. Part of item 9, pp. 66--73. \bye %Addendum: Computational Complexity 2 (1992), p. 374 % (to BFL: Sec 7.1 --> BFLS)