| [1] |
László Babai.
Coloring infinite graphs (Hungarian).
Matematikai Lapok, 20:141-143, 1969.
[ bib ]
Keywords: combinatorics, transfinite |
| [2] |
László Babai.
Representation of permutation groups by graphs.
In Pál Erdős et al., editor, Combinatorial Theory and
its Applications, Proc. Conf. Balatonfüred, 1969, pages 55-80, Hungary,
1970. Bolyai Society - North-Holland.
[ bib ]
Keywords: automorphisms, groups, prescribed |
| [3] |
László Babai.
Automorphism groups of planar graphs I.
Discrete Math., 2(4):295-307, 1972.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [4] |
László Babai.
Groups of graphs on given surfaces.
Acta Math. Acad. Sci. Hung., 24(1-2):215-221, 1973.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [5] |
László Babai and Wilfried Imrich.
On groups of polyhedral graphs.
Discrete Math., 5(1):101-103, 1973.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [6] |
László Babai and László Lovász.
Permutation groups and almost regular graphs.
Studia Sci. Math. Hung., 8:141-150, 1973.
[ bib ]
Keywords: automorphisms, groups |
| [7] |
László Babai, Wilfried Imrich, and László Lovász.
Finite homeomorphism groups of the 2-sphere.
In Á. Császár, editor, Topics in Topology, Proc.
Conf. Keszthely, 1972, pages 61-75, Hungary, 1973. Bolyai Society -
North-Holland.
[ bib ]
Keywords: automorphisms, groups, topological_graph_theory |
| [8] |
László Babai and Attila Máté.
Inner set mappings on locally compact spaces.
In Á. Császár, editor, Topics in Topology, Proc.
Conf. Keszthely, Hungary 1972, pages 77-95, Hungary, 1973. Bolyai Society -
North-Holland.
[ bib ]
Keywords: topology, transfinite |
| [9] |
László Babai.
Automorphism groups of graphs and edge-contraction.
Discrete Math., 8(1):13-20, 1974.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [10] |
László Babai.
A remark on contraction of graphs with given group.
Acta Math. Acad. Sci. Hung., 25(1-2):89-91, 1974.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [11] |
László Babai.
On the minimum order of graphs with given group.
Canad. Math. Bull., 17(4):467-470, 1974.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed |
| [12] |
László Babai.
Automorphism groups of planar graphs II.
In A. Hajnal et al., editor, Infinite and finite sets, Proc.
Conf. Keszthely, Hungary, 1973, pages 29-84, Hungary, 1975. Bolyai Society
- North-Holland.
[ bib ]
Keywords: automorphisms, groups, topological_graph_theory |
| [13] |
László Babai and Wilfried Imrich.
Sense preserving groups of polyhedral graphs.
Monatshefte Math., 79(1):1-2, 1975.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [14] |
László Babai.
Automorphism groups of graphs.
Ph.D. Thesis, Hungarian Academy of Sciences, 1975.
In Hungarian, 308 pages.
[ bib ]
Keywords: automorphisms, groups, topological_graph_theory |
| [15] |
László Babai.
Asymmetric trees with two prescribed degrees.
Acta Math. Acad. Sci. Hung., 29(1-2):193-200, 1977.
[ bib |
DOI ]
Keywords: automorphisms, asymmetry |
| [16] |
László Babai.
Some applications of graph contractions.
J. Graph Theory, 1(2):125-130, 1977.
[ bib |
DOI ]
Keywords: automorphisms, groups, topological_graph_theory |
| [17] |
László Babai.
Isomorphism problem for a class of point-symmetric structures.
Acta Math. Acad. Sci. Hung., 29(3-4):329-336, 1977.
[ bib |
DOI ]
Keywords: groups, CI, Cayley_graphs |
| [18] |
László Babai.
On the collineation groups of infinite projective and affine planes.
J. of Geometry, 10(1-2):138-145, 1977.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed |
| [19] |
László Babai.
Symmetry groups of vertex-transitive polytopes.
Geometriae Dedicata, 6(3):331-337, 1977.
[ bib |
DOI ]
Keywords: automorphisms, groups, vertex-transitive_graphs, prescribed, GRR |
| [20] |
László Babai.
On the isomorphism problem.
Technical report, 1977.
Appended to Proc. Conf. FCT'77, Poznan-Kornik. 10 pages.
[ bib ]
Keywords: isomorphism, graph_isomorphism, algorithms, complexity |
| [21] |
László Babai.
Chromatic number and subgraphs of Cayley graphs.
In Y. Alavi and D.R. Lick, editors, Theory and Appl. of Graphs,
volume 642 of Lecture Notes in Math., pages 10-22. Springer, 1978.
[ bib |
DOI ]
Keywords: Cayley_graphs, vertex-transitive_graphs, symmetry |
| [22] |
László Babai.
Automorphism group and category of cospectral graphs.
Acta Math. Acad. Sci. Hung., 31(3-4):295-306, 1978.
[ bib |
DOI ]
Keywords: automorphisms, groups, spectrum, semigroups, categories |
| [23] |
László Babai and Péter Frankl.
Isomorphisms of Cayley graphs I.
In A. Hajnal and Vera T. Sós, editors, Combinatorics (Proc.
Conf. Keszthely, Hungary, 1976), pages 35-52. Bolyai Society -
North-Holland, 1978.
[ bib ]
Keywords: groups, CI, Cayley_graphs |
| [24] |
László Babai and Jaroslav Nešetřil.
High chromatic rigid graphs I.
In A. Hajnal and Vera T. Sós, editors, Combinatorics (Proc.
Conf. Keszthely, Hungary, 1976), pages 53-60. Bolyai Society -
North-Holland, 1978.
See item 1982:61.
[ bib ]
Keywords: automorphisms, groups, asymmetry, semigroups |
| [25] |
László Babai.
Embedding graphs in Cayley graphs.
In J-C. Bermond et al., editor, Probl. Combinatoires et Theorie
des Graphes (Proc. Conf. Paris-Orsay 1976), pages 13-15, Paris, 1978.
Centre National de Rech. Sci.
[ bib ]
Keywords: groups, Cayley_graphs, vertex-transitive_graphs |
| [26] |
László Babai and Péter Frankl.
Infinite quasigroups with given regular automorphism groups.
Algebra Universalis, 8(1):310-319, 1978.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed, highly_regular |
| [27] |
László Babai.
Infinite digraphs with given regular automorphism groups.
J. Combin. Theory Ser. B, 25(1):26-46, 1978.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed, transfinite, GRR, combinatorics_journals |
| [28] |
László Babai and Francis J. Pastijn.
On semigroups with high symmetry.
Simon Stevin, 52:73-84, 1978.
[ bib ]
Keywords: automorphisms, groups, semigroups, symmetry |
| [29] |
László Babai.
On a conjecture of M.E. Watkins on graphical regular
representations of finite groups.
Compositio Math., 37(3):291-296, 1978.
[ bib |
http ]
Keywords: automorphisms, groups, GRR |
| [30] |
László Babai.
Vector representable matroids of given rank with given automorphism
group.
Discrete Math., 24(2):119-125, 1978.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed |
| [31] |
László Babai.
Tournaments with given (infinite) automorphism group.
Periodica Math. Hung., 10(1):99-104, 1979.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed |
| [32] |
László Babai.
Endomorphisms of sub- and factorsemigroups.
In G. Pollák, editor, Algebraic theory of semigroups (Proc.
Conf. Szeged, 1976), volume 20, pages 43-50. Colloq. Math. Soc. J. Bolyai,
Bolyai Society - North-Holland, 1979.
[ bib ]
Keywords: automorphisms, groups, semigroups, categories |
| [33] |
László Babai, Péter Frankl, János Kollár, and Gert
Sabidussi.
Hamiltonian cubic graphs and centralizers of involutions.
Canad. J. Math., 31(3):458-464, 1979.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed, group_theory |
| [34] |
László Babai and Luděk Kučera.
Canonical labelling of graphs in linear average time.
In Proc. 20th FOCS, pages 39-46. IEEE, IEEE Comp. Soc. Press,
1979.
[ bib |
DOI ]
Keywords: algorithms, isomorphism, graph_isomorphism, random, FOCS, STOC_FOCS |
| [35] |
László Babai.
Monte Carlo algorithms in graph isomorphism testing.
Tech. Rep. 79-10, Université de Montréal, 1979.
42 pages.
[ bib |
.pdf ]
Keywords: isomorphism, graph_isomorphism, algorithms, groups, random, algorithmic_group_theory |
| [36] |
László Babai.
Long cycles in vertex transitive graphs.
J. Graph Theory, 3(3):301-304, 1979.
[ bib |
DOI ]
Keywords: automorphisms, vertex-transitive_graphs, symmetry |
| [37] |
László Babai.
Spectra of Cayley graphs.
J. Combin. Theory Ser. B, 27(2):180-189, 1979.
[ bib |
DOI ]
Keywords: Cayley graphs, vertex-transitive_graphs, spectrum |
| [38] |
László Babai and Wilfried Imrich.
Tournaments with given regular group.
Aequationes Math., 19(1):232-244, 1979.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed, GRR |
| [39] |
László Babai and Péter Frankl.
Isomorphisms of Cayley graphs II.
Acta Math. Acad. Sci. Hung., 34(1-2):177-183, 1979.
[ bib |
DOI ]
Keywords: groups, CI, Cayley_graphs |
| [40] |
László Babai.
On the complexity of canonical labelling of strongly regular graphs.
SIAM J. Comput., 9(1):212-216, 1980.
[ bib |
DOI ]
Keywords: algorithms, isomorphism, automorphisms, groups, graph isomorphism, highly_regular, asymptotic_group_theory |
| [41] |
László Babai and Péter Frankl.
On set-intersections.
J. Combin. Theory Ser. A, 28(1):103-105, 1980.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics |
| [42] |
László Babai and Mark E. Watkins.
Connectivity of infinite graphs having a transitive torsion group
action.
Archiv der Math., 34(1):90-96, 1980.
[ bib |
DOI ]
Keywords: automorphisms, groups, vertex-transitive_graphs, symmetry |
| [43] |
László Babai, Pál Erdős, and Stanley M. Selkow.
Random graph isomorphism.
SIAM J. Comput., 9(3):628-635, 1980.
[ bib |
DOI ]
Keywords: algorithms, isomorphism, graph_isomorphism, random |
| [44] |
László Babai.
Almost all Steiner triple systems are asymmetric.
Annals of Discr. Math., 7:37-39, 1980.
Part of “Topics on Steiner Systems” (C.C. Lindner and A. Rosa,
eds.).
[ bib |
DOI ]
Keywords: automorphisms, asymmetry, highly_regular |
| [45] |
László Babai and Aleš Pultr.
Endomorphism monoids and topological subgraphs of graphs.
J. Combin. Theory Ser. B, 28(3):278-283, 1980.
[ bib |
DOI ]
Keywords: automorphisms, semigroups, topological_graph_theory |
| [46] |
László Babai.
Two remarks on the complexity of graph isomorphism testing.
In P.Z. Chinn and D. McCarthy, editors, Proc. West Coast Conf.
on Combinatorics, Graph Th. and Computing, Humboldt State University 1979,
pages 95-99, Winnipeg, 1980. Utilitas Math.
[ bib ]
Keywords: complexity, isomorphism, algorithms, graph_isomorphism |
| [47] |
László Babai.
Finite digraphs with given regular automorphism groups.
Periodica Math. Hung., 11(4):257-270, 1980.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed, GRR |
| [48] |
László Babai.
Isomorphism testing and symmetry of graphs I.
Annals of Discr. Math., 8:101-109, 1980.
Part of “Combinatorics 79” (M. Deza and I.G. Rosenberg, eds.).
[ bib |
DOI ]
Keywords: isomorphism, graph_isomorphism, algorithms, survey |
| [49] |
Michael E. Adams, László Babai, and Jiři Sichler.
Automorphism groups of finite distributive lattices with a given
sublattice of fixed points.
Monatshefte Math., 90(4):259-266, 1980.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed, lattices |
| [50] |
László Babai.
Kospektrale Graphen mit vorgegebenen Automorphismengruppen.
Wissenschaftliche Zeitschr. der Technischen Hochschule Ilmenau,
27(4):31-37, 1981.
[ bib ]
Keywords: automorphisms, prescribed, spectrum |
| [51] |
László Babai.
Some problems on lattice automorphisms.
Studia Sci. Math. Hung., 13:139-142, 1978.
[ bib ]
Keywords: automorphisms, groups, lattices |
| [52] |
László Babai.
On the abstract group of automorphisms.
In H.N.V. Temperley, editor, Proc. 8th British Combinatorial
Conf., volume 52 of Lecture Note, pages 1-40. London Math. Soc.,
Cambridge Univ. Press, 1981.
[ bib |
http ]
Keywords: automorphisms, groups, survey |
| [53] |
László Babai.
On the order of uniprimitive permutation groups.
Ann. of Math., 113(3):553-568, 1981.
[ bib |
http ]
Keywords: groups, isomorphism, asymptotic_group_theory, highly_regular, graph_isomorphism, combinatorics_in_groups, motivated_by, pr |
| [54] |
László Babai.
Moderately exponential bound for graph isomorphism.
In Gécseg, editor, Proc. 1981 International FCT-Conference
(FCT'81), volume 117 of Lecture Notes in Computer Science, pages
34-50. Springer, 1981.
[ bib |
DOI ]
Keywords: isomorphism, graph_isomorphism, groups, algorithmic_group_theory, other_conf |
| [55] |
László Babai and Dwight Duffus.
Dimension and automorphism groups of lattices.
Algebra Universalis, 12(1):279-289, 1981.
[ bib |
DOI ]
Keywords: automorphisms, groups, lattices |
| [56] |
László Babai.
On strong embeddings of categories.
In B. Csákány and E.T. Schmidt, editors, Universal
Algebra (Proc. Conf. Esztergom 1977), volume 29 of Coll. Math. Soc. J.
Bolyai, pages 37-51. Bolyai Society - North-Holland, 1981.
[ bib ]
Keywords: automorphisms, semigroups, categories |
| [57] |
László Babai, Peter J. Cameron, Michel Deza, and Navin M. Singhi.
On sharply edge-transitive permutation groups.
J. Algebra, 73(2):573-585, 1981.
[ bib |
DOI ]
Keywords: automorphisms, groups, vertex-transitive_graphs, permutation_groups, JAlg |
| [58] |
László Babai.
Prímszámok és titkosírás (prime numbers and
cryptography).
Természet Világa, 112(6):250-253, 1981.
In Hungarian.
[ bib ]
Keywords: popular |
| [59] |
László Babai.
On the order of doubly transitive permutation groups.
Inventiones Math., 65(3):473-484, 1982.
[ bib |
DOI ]
Keywords: asymptotic_group_theory, groups, pr, combinatorics_in_groups, random |
| [60] |
László Babai and Chris D. Godsil.
On the automorphism groups of almost all Cayley graphs.
Europ. J. Comb., 3(1):6-15, 1982.
[ bib |
DOI ]
Keywords: automorphisms, groups, Cayley_graphs, GRR |
| [61] |
László Babai and Jaroslav Nešetřil.
High chromatic rigid graphs II.
Annals of Discr. Math., 15:55-61, 1982.
In “Algebraic and Geometric Combinatorics” (E. Mendelsohn ed.). See
item 1978:24.
[ bib |
DOI ]
Keywords: automorphisms, groups, asymmetry, semigroups |
| [62] |
László Babai, Fan R. K. Chung, Pál Erdős, Ronald L. Graham,
and Joel H. Spencer.
On graphs which contain all sparse graphs.
Annals of Discr. Math., 12:21-26, 1982.
In “Theory and Practice of Combinatorics” (A. Rosa, G. Sabidussi,
J. Turgeon eds.).
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics |
| [63] |
László Babai and Pál Erdős.
Representation of group elements as short products.
Annals of Discr. Math., 12:27-30, 1982.
In “Theory and Practice of Combinatorics” (A. Rosa, G. Sabidussi,
J. Turgeon eds.).
[ bib |
DOI ]
Keywords: groups, combinatorics_in_groups, asymptotic_group_theory |
| [64] |
László Babai, Dmitri Yu. Grigor'ev, and David M. Mount.
Isomorphism of graphs with bounded eigenvalue multiplicity.
In Proc. 14th STOC, pages 310-324. ACM Press, 1982.
[ bib |
DOI ]
Keywords: isomorphism, graph_isomorphism, algorithms, spectrum, STOC, STOC_FOCS |
| [65] |
László Babai, Peter J. Cameron, and Péter P. Pálfy.
On the orders of primitive groups with restricted nonabelian
composition factors.
J. Algebra, 79(1):161-168, 1982.
[ bib |
DOI ]
Keywords: groups, asymptotic_group_theory, motivated_by, JAlg |
| [66] |
László Babai, Róbert Freud, and Rezső Kunfalvy.
Prímszámvadászat számítógéppel
(Hunting for prime numbers with a computer).
Természet Világa, 113(5):201-205, 1982.
In Hungarian.
[ bib ]
Keywords: popular |
| [67] |
László Babai and Eugene M. Luks.
Canonical labeling of graphs.
In Proc. 15th STOC, pages 171-183. ACM Press, 1983.
[ bib |
DOI ]
Keywords: graph-isomorphism, algorithms, highly_regular, STOC, STOC_FOCS |
| [68] |
László Babai, William M. Kantor, and Eugene M. Luks.
Computational complexity and the classification of finite simple
groups.
In Proc. 24th FOCS, pages 162-171. IEEE Comp. Soc. Press,
1983.
[ bib |
DOI ]
Keywords: algorithmic_group_theory, isomorphism, graph_isomorphism, asymptotic_group_theory, FOCS, STOC_FOCS |
| [69] |
László Babai.
Permutation Groups, Coherent Configurations and Graph
Isomorphism.
1984.
D.Sc. Thesis, Hungarian Academy of Sciences. In Hungarian.
[ bib ]
Keywords: automorphisms, groups, permutation_groups, highly_regular, graph-isomorphism |
| [70] |
László Babai and Endre Szemerédi.
On the complexity of matrix group problems I.
In Proc. 25th FOCS, pages 229-240. IEEE Comp. Soc. Press,
1984.
[ bib |
DOI ]
Keywords: complexity, algorithmic_group_theory, matrix_groups, asymptotic_group_theory, FOCS, STOC_FOCS |
| [71] |
László Babai.
On Lovász' lattice reduction and the nearest lattice point
problem.
In Proc. 2nd Symp. Theoretical Aspects of Comp. Sci.
(STACS'85), volume 182 of Springer Lecture Notes in Comp. Sci., pages
13-20. Springer, 1985.
See 1986.77.
[ bib |
DOI ]
Keywords: algorithms, lattice_vector, other_conf |
| [72] |
László Babai.
Trading group theory for randomness.
In Proc. 17th STOC, pages 421-429. ACM Press, 1985.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, random, algorithmic_group_theory, STOC, STOC_FOCS |
| [73] |
László Babai.
An anti-Ramsey theorem.
Graphs and Combinatorics, 1(1):23-28, 1985.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics, random, combinatorics_journals |
| [74] |
László Babai.
Arc transitive covering digraphs and their eigenvalues.
J. Graph Theory, 9(3):363-370, 1985.
[ bib |
DOI ]
Keywords: groups, automorphisms, symmetry, vertex-transitive_graphs, spectrum, combinatorics_journals |
| [75] |
László Babai and Vera T. Sós.
Sidon sets in groups and induced subgraphs of Cayley graphs.
Europ. J. Comb., 6(2):101-114, 1985.
[ bib |
DOI ]
Keywords: groups, Cayley_graphs, vertex-transitive_graphs, combinatorics_in_groups, combinatorics_journals, inspired |
| [76] |
Miklós Ajtai, László Babai, Péter Hajnal, János Komlós,
Pavel Pudlák, Vojtěch Rödl, Endre Szemerédi, and György
Turán.
Two lower bounds for branching programs.
In Proc. 18th STOC, pages 30-38. ACM Press, 1986.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, STOC, STOC_FOCS |
| [77] |
László Babai.
On Lovász' lattice reduction and the nearest lattice point
problem.
Combinatorica, 6(1):1-13, 1986.
Full version of 1985.71.
[ bib |
DOI ]
Keywords: algorithms, lattice_vector, combinatorics_journals |
| [78] |
László Babai.
A Las Vegas-NC algorithm for isomorphism of graphs
with bounded multiplicity of eigenvalues.
In Proc. 27th FOCS, pages 303-312. IEEE Comp. Soc. Press,
1986.
[ bib |
DOI ]
Keywords: isomorphism, graph_isomorphism, spectrum, algorithmic_group_theory, algorithms, complexity, random |
| [79] |
László Babai, Péter Frankl, and Janos Simon.
Complexity classes in communication complexity theory.
In Proc. 27th FOCS, pages 337-347. IEEE Comp. Soc. Press,
1986.
[ bib |
DOI ]
Keywords: complexity, communication_complexity, lower_bounds, FOCS, STOC_FOCS |
| [80] |
László Babai.
On the length of subgroup chains in the symmetric group.
Comm. Algebra, 14(9):1729-1736, 1986.
[ bib |
DOI ]
Keywords: groups, asymptotic_group_theory, permutation_groups |
| [81] |
Noga Alon, László Babai, and Alon Itai.
A fast and simple randomized parallel algorithm for the maximal
independent set problem.
J. Algorithms, 7(4):567-583, 1986.
[ bib |
DOI ]
Keywords: algorithms, complexity, codes, lower_bounds, random |
| [82] |
László Babai.
On the non-uniform Fisher inequality.
Discrete Math., 66(3):303-307, 1987.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics, combinatorics_journals |
| [83] |
László Babai, Eugene M. Luks, and Ákos Seress.
Permutation groups in NC.
In Proc. 19th STOC, pages 409-420. ACM Press, 1987.
[ bib |
DOI ]
Keywords: groups, algorithmic_group_theory, algorithms, complexity, STOC, STOC_FOCS |
| [84] |
László Babai and Ákos Seress.
On the degree of transitivity of permutation groups: A short proof.
J. Combin. Theory Ser. A, 45(2):310-315, 1987.
[ bib |
DOI ]
Keywords: groups, asymptotic_group_theory, combinatorics_in_groups, combinatorics_journals |
| [85] |
László Babai and György Turán.
The complexity of defining a relation on a finite graph.
Zeitschrift für Mathematische Logik und Grundlagen der
Mathematik, 33(3):277-288, 1987.
[ bib |
DOI ]
Keywords: complexity |
| [86] |
László Babai, Péter Hajnal, Endre Szemerédi, and György
Turán.
A lower bound for read-once-only branching programs.
J. Comput. System Sci., 35(2):153-162, 1987.
[ bib |
DOI ]
Keywords: complexity, lower_bounds |
| [87] |
László Babai.
Random oracles separate PSPACE from the polynomial-time
hierarchy.
Inform. Process. Lett., 26(1):51-53, 1987.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, random |
| [88] |
László Babai and Ákos Seress.
On the diameter of Cayley graphs of the symmetric group.
J. Combin. Theory Ser. A, 49(1):175-179, 1988.
[ bib |
DOI ]
Keywords: automorphisms, groups, combinatorics_in_groups, asymptotic_group_theory, Cayley_graphs, combinatorics_journals |
| [89] |
László Babai and Shlomo Moran.
Arthur-Merlin games: A randomized proof system and a hierarchy
of complexity classes.
J. Comput. System Sci., 36(2):254-276, 1988.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, special_issue |
| [90] |
László Babai.
A short proof of the non-uniform Ray-Chaudhuri-Wilson
inequality.
Combinatorica, 8(1):133-135, 1988.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics, polynomials, combinatorics_journals |
| [91] |
László Babai, Eugene M. Luks, and Ákos Seress.
Fast management of permutation groups.
In Proc. 29th FOCS, pages 272-282. IEEE Comp. Soc. Press,
1988.
Conference version of 1997:159.
[ bib |
DOI ]
Keywords: groups, algorithmic_group_theory, algorithms, permutation_groups, FOCS, STOC_FOCS |
| [92] |
László Babai, Bettina Just, and Friedhelm Meier auf der Heide.
On the limits of computations with the floor function.
Inform. and Comput., 78(2):99-107, 1988.
[ bib |
DOI ]
Keywords: complexity, lower_bounds |
| [93] |
László Babai, Noam Nisan, and Mario Szegedy.
Multiparty protocols and Logspace-hard pseudorandom sequences.
In Proc. 21st STOC, pages 1-11. ACM Press, 1989.
See 1992.126.
[ bib |
DOI ]
Keywords: complexity, communication_complexity, lower_bounds, STOC, STOC_FOCS |
| [94] |
László Babai.
The probability of generating the symmetric group.
J. Combin. Theory Ser. A, 52(1):148-153, 1989.
[ bib |
DOI ]
Keywords: groups, asymptotic_group_theory, permutation_groups, combinatorics_journals |
| [95] |
László Babai and Shlomo Moran.
Proving properties of interactive proofs by a generalized counting
technique.
Inform. and Comput., 82(2):185-197, 1989.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs |
| [96] |
László Babai and Lajos Rónyai.
Computing irreducible representations of finite groups.
In Proc. 30th FOCS, pages 93-98. IEEE Comp. Soc. Press, 1989.
See 1990.102.
[ bib |
DOI ]
Keywords: algorithmic_group_theory, algorithmic_algebra, algorithms, FOCS, STOC_FOCS |
| [97] |
László Babai, William M. Kantor, and Alex Lubotsky.
Small diameter Cayley graphs for finite simple groups.
Europ. J. Comb., 10(6):507-522, 1989.
[ bib |
DOI ]
Keywords: groups, Cayley_graphs, combinatorics_in_groups, diameter, asymptotic_groups_theory, combinatorics_journals |
| [98] |
László Babai.
E-mail and the unexpected power of interaction.
In Proc. 5th IEEE Conf. on Structure in Complexity Theory
(SCT'90), pages 30-44. IEEE Comp. Soc. Press, 1990.
For Polish translation see item 1995.151.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, popular, other_conf |
| [99] |
László Babai, Lance Fortnow, and Carsten Lund.
Nondeterministic exponential time has two-prover interactive
protocols.
In Proc. 31st FOCS, pages 16-25. IEEE Comp. Soc. Press, 1990.
See item 1991.108.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, property_testing, random, FOCS, STOC_FOCS |
| [100] |
László Babai and Lance Fortnow.
A characterization of #p by arithmetic straight line
programs.
In Proc. 31st FOCS, pages 26-34. IEEE Comp. Soc. Press, 1990.
See item 1991.109.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, FOCS, STOC_FOCS |
| [101] |
László Babai, Gábor Hetyei, William M. Kantor, Alex Lubotsky, and
Ákos Seress.
On the diameter of finite groups.
In Proc. 31st FOCS, pages 857-865. IEEE Comp. Soc. Press,
1990.
[ bib |
DOI ]
Keywords: groups, Cayley_graphs, diameter, combinatorics_in_groups, asymptotic_group_theory |
| [102] |
László Babai and Lajos Rónyai.
Computing irreducible representations of finite groups.
Mathematics of Computation, 55(192):705-722, 1990.
Full version of item 1989.96.
[ bib |
DOI ]
Keywords: algorithmic_group_theory, algorithmic_algebra, algorithms |
| [103] |
László Babai, Pavel Pudlák, Vojtěch Rödl, and Endre
Szemerédi.
Lower bounds to the complexity of symmetric Boolean functions.
Theoret. Comput. Sci., 74(3):313-324, 1990.
[ bib |
DOI ]
Keywords: complexity, lower_bounds |
| [104] |
László Babai, Miklós Simonovits, and Joel H. Spencer.
Extremal subgraphs of random graphs.
J. Graph Theory, 14(5):599-622, 1990.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics, random |
| [105] |
László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy.
Checking computations in polylogarithmic time.
In Proc. 23rd STOC, pages 21-32. ACM Press, 1991.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, codes, random, STOC, STOC_FOCS |
| [106] |
László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, and
Ákos Seress.
Fast Monte-Carlo algorithms for permutation groups.
In Proc. 23rd STOC, pages 90-100. ACM Press, 1991.
Conference version of item 1995:144.
[ bib |
DOI ]
Keywords: algorithmic_group_theory, algorithms, random, STOC, STOC_FOCS |
| [107] |
László Babai.
Local expansion of vertex-transitive graphs and random generation in
finite groups.
In Proc. 23rd STOC, pages 164-174. ACM Press, 1991.
[ bib |
DOI ]
Keywords: groups, symmetry, vertex-transitive_graphs, algorithmic_group_theory, random, Markov_Chains, STOC, STOC_FOCS |
| [108] |
László Babai, Lance Fortnow, and Carsten Lund.
Nondeterministic exponential time has two-prover interactive
protocols.
Comput. Complexity, 1(1):3-40, 1991.
Full version of 1990.99.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, property_testing, random |
| [109] |
László Babai and Lance Fortnow.
Arithmetization: A new method in structural complexity theory.
Comput. Complexity, 1(1):41-66, 1991.
Full version of item 1990.100.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs |
| [110] |
László Babai, Albert J. Goodman, and László Lovász.
Graphs with given automorphism group and few edge orbits.
Europ. J. Comb., 12(3):185-203, 1991.
[ bib |
DOI ]
Keywords: automorphisms, prescribed, groups, combinatorics_journals |
| [111] |
László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson.
BPP has subexponential time simulations unless
EXPTIME has publishable proofs.
In Proc. 6th IEEE Conf. on Structure in Complexity Theory
(SCT'91), pages 213-219, Chicago, 1991. IEEE, IEEE Comp. Soc. Press.
Conference version of 1993:138.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, other_conf |
| [112] |
László Babai, Gene Cooperman, Larry Finkelstein, and Ákos Seress.
Nearly linear time algorithms for permutation groups with a small
base.
In Proc. 2nd Internat. Symp. on Symbolic and Algebraic
Computation (ISAAC'91), pages 200-209, Bonn, 1991. ACM Press.
[ bib |
DOI ]
Keywords: algorithmic_group_theory, algorithms, random |
| [113] |
Noga Alon, László Babai, and Hiroshi Suzuki.
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson
type inequalities.
J. Combin. Theory Ser. A, 58(2):165-180, 1991.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics, polynomials, combinatorics_journals |
| [114] |
László Babai.
Vertex-transitive graphs and vertex-transitive maps.
J. Graph Theory, 15(6):587-627, 1991.
[ bib |
DOI ]
Keywords: automorphisms, vertex-transitive_graphs, symmetry, topological_graph_theory, graph_limit |
| [115] |
László Babai and Katalin Friedl.
Approximate representation theory of finite groups.
In Proc. 32nd FOCS, pages 733-742, Puerto Rico, 1991. IEEE
Comp. Soc. Press.
[ bib |
DOI ]
Keywords: groups, algorithmic_algebra, algorithms, FOCS, STOC_FOCS |
| [116] |
László Babai.
Computational complexity in finite groups.
In Proc. Internat. Congress of Mathematicians, Kyoto 1990,
pages 1479-1490, Kyoto, 1991. Springer.
[ bib |
http ]
Keywords: algorithmic_group_theory, survey |
| [117] |
László Babai.
Deciding finiteness of matrix groups in Las Vegas polynomial
time.
In Proc. 3rd Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'92), pages 33-40, Orlando, FL, 1992. SIAM.
See item 1993:132.
[ bib ]
Keywords: algorithmic_group_theory, algorithms, random, Markov_Chains, SODA |
| [118] |
László Babai.
Bounded round interactive proofs in finite groups.
SIAM J. Discrete Math., 5(1):88-111, 1992.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, algorithmic_group_theory, combinatorics_journals |
| [119] |
László Babai, Robert Beals, and Pál Takácsi-Nagy.
Symmetry and complexity.
In Proc. 24th STOC, pages 438-449, Vancouver B.C., 1992. ACM
Press.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, random, STOC, STOC_FOCS |
| [120] |
László Babai and Mario Szegedy.
Local expansion of symmetrical graphs.
Combin. Probab. Comput., 1(1):1-11, 1992.
[ bib |
DOI ]
Keywords: automorphisms, vertex-transitive_graphs, symmetry, random, combinatorics_journals |
| [121] |
László Babai and Tamás Lengyel.
A convergence criterion for recurrent sequences with application to
the partition lattice.
Analysis, 12:109-119, 1992.
[ bib |
http ]
Keywords: combinatorics, analysis |
| [122] |
László Babai.
Transparent proofs.
FOCUS (MAA Newsletter), 12(3):1-2, June 1992.
[ bib ]
Keywords: complexity, interactive_proofs, popular |
| [123] |
László Babai.
Combinatorial optimization is hard.
FOCUS (MAA Newsletter), 12(4):3,6,18, September 1992.
[ bib ]
Keywords: complexity, interactive_proofs, inapproximability, popular |
| [124] |
László Babai and Péter Frankl.
Linear Algebra Methods in Combinatorics, with Applications to
Geometry and Computer Science.
Univ. of Chicago Dept. Computer Sci., 1992.
Unpublished, preliminary version 2, 216 pages.
[ bib |
http ]
Keywords: combinatorics, extremal_combinatorics, book |
| [125] |
László Babai and Ákos Seress.
On the diameter of permutation groups.
Europ. J. Comb., 13(4):231-243, 1992.
[ bib |
DOI ]
Keywords: groups, Cayley_graphs, combinatorics_in_groups, diameter, inspire, combinatorics_journals |
| [126] |
László Babai, Noam Nisan, and Mario Szegedy.
Multiparty protocols, pseudorandom generators for Logspace, and
time-space trade-offs.
J. Comput. System Sci., 45(2):204-232, 1992.
Special issue. Full version of item 1989.93.
[ bib |
DOI ]
Keywords: complexity, communication_complexity, lower_bounds, special_issue |
| [127] |
László Babai and Gábor L. Hetyei.
On the diameter of random Cayley graphs of the symmetric group.
Combin. Probab. Comput., 1(3):201-208, 1992.
[ bib |
DOI ]
Keywords: groups, Cayley_graphs, combinatorics_in_groups, diameter, random, combinatorics_journals |
| [128] |
László Babai and Vera T. Sós.
Tibor Gallai, 1912-1992.
Combinatorica, 12(4):371-372, 1992.
[ bib |
DOI ]
Keywords: bio, combinatorics_journals |
| [129] |
László Babai.
Transparent (holographic) proofs.
In Proc. 10th Symp. Theoretical Aspects of Comp. Sci.
(STACS'93), volume 665 of Springer Lect. Notes in Comp. Sci., pages
525-534, Würzburg (Germany), 1993. Springer.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, survey |
| [130] |
László Babai, Albert J. Goodman, and László Pyber.
On faithful permutation representations of small degree.
Comm. Algebra, 21(5):1587-1602, 1993.
[ bib |
DOI ]
Keywords: groups, permutation_groups, asymptotic_group_theory |
| [131] |
László Babai and Albert J. Goodman.
Subdirectly reducible groups and edge-minimal graphs with given
automorphism group.
J. London Math. Soc., 47(3):417-432, 1993.
[ bib |
DOI ]
Keywords: automorphisms, groups, prescribed |
| [132] |
László Babai, Robert Beals, and Daniel Rockmore.
Deciding finiteness of matrix groups in deterministic polynomial
time.
In Proc. 4th Internat. Symp. on Symbolic and Algebraic
Computation (ISAAC'93), pages 117-126. ACM Press, 1993.
See item 1992.117.
[ bib |
DOI ]
Keywords: algorithms, algorithmic_group_theory, groups, other_conf |
| [133] |
László Babai, Katalin Friedl, and Marcus Stricker.
Decomposition of *-closed algebras in polynomial time.
In Proc. 4th Internat. Symp. on Symbolic and Algebraic
Computation (ISAAC'93), pages 86-94. ACM Press, 1993.
[ bib |
DOI ]
Keywords: algorithms, algorithmic_algebra, other_conf |
| [134] |
László Babai and Albert J. Goodman.
On the abstract group of automorphisms.
In D. Jungnickel and S. A. Vanstone, editors, “Coding Theory,
Desing Theory, Group Theory”, Proc. of Marshall Hall Conf., Burlington VT
1990, pages 121-143. Wiley, 1993.
[ bib ]
Keywords: automorphisms, groups, prescribed, survey |
| [135] |
László Babai, Eugene M. Luks, and Ákos Seress.
Computing composition series in primitive groups.
In L. Finkelstein and W. M. Kantor, editors, Groups and
Computation, volume 11 of DIMACS Ser. in Discr. Math. and Theor. Comp.
Sci., pages 1-16. Amer. Math. Soc., 1993.
Workshop on groups and computation, Oct 7-10, 1991.
[ bib ]
Keywords: algorithms, groups, algorithmic_group_theory |
| [136] |
Sanjeev Arora, László Babai, Jacques Stern, and Z. (Elizabeth) Sweedyk.
The hardness of approximate optima in lattices, codes, and systems of
linear equations.
In Proc. 34th FOCS, pages 724-733, Palo Alto CA, 1993. IEEE
Comp. Soc. Press.
Conference version of item 1997:160.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, inapproximability, codes, lattice_vector, FOCS, STOC_FOCS |
| [137] |
Robert Beals and László Babai.
Las Vegas algorithms for matrix groups.
In Proc. 34th FOCS, pages 427-436, Palo Alto CA, 1993. IEEE
Comp. Soc. Press.
[ bib |
DOI ]
Keywords: algorithmic_group_theory, algorithms, random, matrix_groups, FOCS, STOC_FOCS |
| [138] |
László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson.
BPP has subexponential time simulations unless
EXPTIME has publishable proofs.
Comput. Complexity, 3(4):307-318, 1993.
Full version of item 1991.111.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs |
| [139] |
László Babai and László Pyber.
Permutation groups without exponentially many orbits on the power
set.
J. Combin. Theory Ser. A, 66(1):160-168, 1994.
[ bib |
DOI ]
Keywords: groups, permutation_groups, asymptotic_group_theory, combinatorics_journals |
| [140] |
László Babai, Haluk Oral, and Kevin T. Phelps.
Eulerian self-dual codes.
SIAM J. Discrete Math., 7(2):325-330, 1994.
[ bib |
DOI ]
Keywords: combinatorics, codes, automorphisms, prescribed, combinatorics_journals |
| [141] |
László Babai.
Transparent proofs and limits to approximation.
In Proc. First European Congress of Mathematics (1992),
volume I, pages 31-91. Birkhäuser Basel, 1994.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, inapproximability, random, survey |
| [142] |
László Babai, Peter Kimmel, and Satyanarayana V. Lokam.
Simultaneous messages vs. communication.
In E. Mayr and C. Puech, editors, Proc. 12th Symp. Theoretical
Aspects of Comp. Sci. (STACS'95), volume 900 of Lect. Notes in Comp.
Sci., pages 361-372, Munich, 1995. Springer.
[ bib |
DOI ]
Keywords: complexity, communication_complexity, lower_bounds, other_conf |
| [143] |
László Babai, Hunter Snevily, and Richard M. Wilson.
A new proof of several inequalities on codes and sets.
J. Combin. Theory Ser. A, 71(1):146-153, 1995.
[ bib |
DOI ]
Keywords: combinatorics, extremal_combinatorics, codes, combinatorics_journals |
| [144] |
László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, and
Ákos Seress.
Fast Monte Carlo algorithms for permutation groups.
J. Comput. System Sci., 50(2):296-308, 1995.
Special issue; full version of item 1991.106.
[ bib |
DOI ]
Keywords: groups, algorithmic_group_theory, algorithms, random, special_issue |
| [145] |
László Babai.
Automorphism groups, isomorphism, reconstruction.
In R. L. Graham, M. Grötschel, and L. Lovász, editors,
Handbook of Combinatorics, chapter 27, pages 1447-1540. North-Holland -
Elsevier, 1995.
[ bib ]
Keywords: automorphisms, groups, symmetry, isomorphism, graph_isomorphism, survey |
| [146] |
László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, and
Eugene M. Luks.
Multiplicative equations over commuting matrices.
In Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'96), pages 498-507. SIAM, 1996.
[ bib ]
Keywords: algorithmic_algebra, semigroups, algorithms, SODA |
| [147] |
László Babai, Anna Gál, János Kollár, Lajos Rónyai,
Tibor Szabó, and Avi Wigderson.
Extremal bipartite graphs and superpolynomial lower bounds for
monotone span programs.
In Proc. 28th STOC, pages 603-611. ACM Press, 1996.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, combinatorics, extremal_combinatorics, STOC, STOC_FOCS |
| [148] |
László Babai.
In and out of Hungary: Paul Erdős, his friends, and
times.
In D. Miklós, V. T. Sós, and T. Szőnyi, editors,
Combinatorics: Paul Erdős Is Eighty, volume 2 of Bolyai
Society Mathematical Studies, pages 7-95. J. Bolyai Mathematical Society,
Budapest, 1996.
[ bib ]
Keywords: bio, erdos |
| [149] |
László Babai.
We stare in disbelief ... (untitled letter on Paul
Erdős's passing).
Combinatorica, 16(4):452, 1996.
[ bib |
DOI ]
Keywords: bio, erdos, combinatorics_journals |
| [150] |
László Babai.
Paul Erdős (1913-1996).
SIGACT News, 27(4):62-65, 1996.
[ bib |
DOI ]
Keywords: bio, erdos |
| [151] |
László Babai.
Poczta komputerowa i niezwykla moc interakcji.
Wiadomości Matematyczne, XXXI:55-80, 1995.
Polish translation of item 1990.98. Appeared Sep. 1996.
[ bib ]
Keywords: complexity, interactive_proofs, popular |
| [152] |
László Babai.
The growth rate of vertex-transitive planar graphs.
In Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'97), pages 564-573, New Orleans LA, 1997. ACM-SIAM, SIAM.
[ bib ]
Keywords: automorphisms, vertex-transitive_graphs, symmetry, topological_graph_theory, combinatorics, SODA |
| [153] |
László Babai.
Randomization in group algorithms: Conceptual questions.
In L. Finkelstein and W. M. Kantor, editors, “Groups and
Computation II”, volume 28 of DIMACS Ser. in Discr. Math. and Theor.
Comp. Sci., pages 1-16. Amer. Math. Soc., 1997.
Workshop on groups and computation, June 7-10, 1995.
[ bib ]
Keywords: groups, algorithmic_group_theory, algorithms, random |
| [154] |
László Babai.
Paul Erdős and his influence on the theory of computing.
SIAM News, 30(1):3, 1997.
[ bib ]
Keywords: bio, erdos, combinatorics, algorithms, complexity |
| [155] |
László Babai.
Paul Erdős (1913-1996): His influence on the theory of
computing.
In Proc. 29th STOC, pages 383-401. ACM Press, 1997.
[ bib |
DOI ]
Keywords: bio, erdos, survey, combinatorics, algorithms, complexity |
| [156] |
László Babai and Peter Kimmel.
Randomized simultaneous messages: Solution of a problem of Yao in
communication complexity.
In Proc. 12th IEEE Conf. on Computational Complexity (CCC'97),
pages 239-246. IEEE Comp. Soc. Press, 1997.
[ bib |
DOI ]
Keywords: complexity, communication_complexity, lower_bounds, random, other_conf |
| [157] |
László Babai, Albert J. Goodman, William M. Kantor, Eugene M. Luks, and
Péter P. Pálfy.
Short presentations for finite groups.
J. Algebra, 194(1):79-112, 1997.
[ bib |
DOI ]
Keywords: groups, asymptotic_group_theory, motivated_by, JAlg |
| [158] |
László Babai, Albert J. Goodman, and László Pyber.
Groups without faithful transitive permutation representations of
small degree.
J. Algebra, 195(1):1-29, 1997.
[ bib |
DOI ]
Keywords: groups, permutation_groups, asymptotic_group_theory, JAlg |
| [159] |
László Babai, Eugene M. Luks, and Ákos Seress.
Fast management of permutation groups I.
SIAM J. Comput., 26(5):1310-1342, 1997.
Full version of 1988.91.
[ bib |
DOI ]
Keywords: groups, algorithmic_group_theory, algorithms, permutation_groups |
| [160] |
Sanjeev Arora, László Babai, Jacques Stern, and Z. (Elizabeth) Sweedyk.
The hardness of approximate optima in lattices, codes, and systems of
linear equations.
J. Comput. System Sci., 54(2):317-331, 1997.
Full version of 1993.136.
[ bib |
DOI ]
Keywords: complexity, interactive_proofs, inapproximability, codes, lattice_vector, spec_issue |
| [161] |
László Babai.
Communication complexity.
In I. Prívara and P. Ružička, editors, Proc. 22nd
Internat. Symp. on Math. Foundations of Computer Science (MFCS'97), volume
1295 of Lecture Notes in Computer Science, pages 5-18. Springer, 1997.
[ bib |
DOI ]
Keywords: complexity, communication_complexity, lower_bounds, survey |
| [162] |
László Babai (organizer), Carl Pomerance, and Péter Vértesi.
The mathematics of Paul Erdős.
Notices Amer. Math. Soc., 45(1):19-31, January 1998.
[ bib |
.pdf ]
Keywords: bio, erdos |
| [163] |
László Babai.
Finite and transfinite combinatorics.
Notices Amer. Math. Soc., 45(1):23-28, January 1998.
Part of item 1998.162.
[ bib |
.pdf ]
Keywords: bio, erdos |
| [164] |
László Babai and Joel H. Spencer.
Paul Erdős (1913-1996).
Notices Amer. Math. Soc., 45(1):64-73, January 1998.
[ bib |
.pdf ]
Keywords: bio, erdos |
| [165] |
László Babai.
Paul Erdős just left town.
Notices Amer. Math. Soc., 45(1):66-73, January 1998.
Part of item 1998.164.
[ bib |
.pdf ]
Keywords: bio, erdos |
| [166] |
László Babai.
The forbidden sidetrip.
In C. S. Calude, editor, People & Ideas in Theoretical
Computer Science, pages 1-31. Springer, 1998.
[ bib ]
Keywords: autobio |
| [167] |
László Babai, Thomas Hayes, and Peter Kimmel.
The cost of the missing bit: Communication complexity with help.
In Proc. 30th STOC, pages 673-682. ACM Press, 1998.
Conference version of item 2001:177.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, communication_complexity, STOC, STOC_FOCS |
| [168] |
László Babai.
Magyarországon és a világban: Erdős Pál,
barátai, és kora.
Természet Világa, 129(3):31-36, 1998.
Hungarian translation of parts of item 1996.148.
[ bib ]
Keywords: bio, erdos |
| [169] |
László Babai and Robert Beals.
A polynomial-time theory of black box groups I.
In C.M. Campbell, E.F. Robertson, N. Ruskuc, and G. C. Smith,
editors, Groups St Andrews 1997 in Bath, I, London Math. Soc.
Lect. Notes, pages 30-64. Cambr. U. Press, 1999.
[ bib |
.pdf ]
Keywords: groups, algorithmic_group_theory, matrix_groups, asymptotic_group_theory |
| [170] |
László Babai, Anna Gál, and Avi Wigderson.
Superpolynomial lower bounds for monotone span programs.
Combinatorica, 19(3):301-319, 1999.
Expanded version of part of item 2001.147.
[ bib |
DOI |
.pdf ]
Keywords: complexity, lower_bounds, combinatorics_journals |
| [171] |
László Babai and Sophie Laplante.
Stronger separations for random-self-reducibility, rounds, and
advice.
In Proc. 14th IEEE Conf. on Computational Complexity (CCC'99),
pages 98-104. IEEE Comp. Soc., IEEE Comp. Soc. Press, 1999.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, other_conf |
| [172] |
László Babai and Igor Pak.
Strong bias of group generators: An obstacle to the “product
replacement algorithm.”.
In Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'00), pages 627-635, San Francisco CA, 2000. ACM-SIAM, SIAM.
Conference version of 2004:181.
[ bib ]
Keywords: groups, algorithmic_group_theory, algorithms, asymptotic_group_theory, SODA |
| [173] |
László Babai and Peter J. Cameron.
Automorphisms and enumeration of switching classes of tournaments.
Electronic J. of Combinatorics, 7:R38 (24 pp.), 2000.
[ bib |
http ]
Keywords: groups, automorphisms, combinatorics, combinatorics_journals, random |
| [174] |
László Babai and Aner Shalev.
Recognizing simplicity of black-box groups and the frequency of
p-singular elements in affine groups.
In W. M. Kantor and Ákos Seress, editors, Groups and
Computation III. Proc. 1999 Workshop at the Ohio State University, pages
39-62, Berlin-New York, 2001. Ohio State University Mathematical Research
Institute Publications, deGruyter.
[ bib |
.pdf ]
Keywords: groups, algorithmic_group_theory, asymptotic_group_theory |
| [175] |
Lajos Rónyai, László Babai, and Murali K. Ganapathy.
On the number of zero-patterns of a sequence of polynomials.
J. Amer. Math. Soc., 14(3):717-735, 2001.
[ bib |
DOI |
.pdf ]
Keywords: combinatorics, extremal_combinatorics, polynomials, pr |
| [176] |
László Babai, Péter Frankl, Samuel Kutin, and Daniel
Stefankovič.
Set systems with restricted intersections modulo prime powers.
J. Combin. Theory Ser. A, 95(1):39-73, 2001.
[ bib |
DOI |
.pdf ]
Keywords: combinatorics, extremal_combinatorics, combinatorics_journals |
| [177] |
László Babai, Thomas Hayes, and Peter Kimmel.
The cost of the missing bit: Communication complexity with help.
Combinatorica, 21(4):455-488, 2001.
Expanded version of item 1998.167.
[ bib |
DOI |
.pdf ]
Keywords: complexity, lower_bounds, communication_complexity, combinatorics_journals |
| [178] |
László Babai, William M. Kantor, Péter P. Pálfy, and Ákos
Seress.
Black-box recognition of finite simple groups of Lie type by
statistics of element orders.
J. Group Theory, 5(4):383-401, 2002.
[ bib |
DOI |
.pdf ]
Keywords: groups, algorithmic_group_theory, asymptotic_group_theory, motivated_by |
| [179] |
László Babai, Amir Shpilka, and Daniel Štefankovič.
Locally testable cyclic codes.
In Proc. 44th FOCS, pages 116-125. IEEE Comp. Soc. Press,
2003.
Conference version of item 2005:185.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, codes, FOCS, STOC_FOCS |
| [180] |
László Babai, Robert Beals, and Ákos Seress.
On the diameter of the symmetric group: Polynomial bounds.
In Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'04), pages 1108-1112. ACM-SIAM, SIAM, 2004.
[ bib ]
Keywords: algorithmic group theory, algorithms, combinatorics, diameter, inspire |
| [181] |
László Babai and Igor Pak.
Strong bias of group generators: An obstacle to the “product
replacement algorithm”.
J. Algorithms, 50(2):215-231, 2004.
Journal version of item 2000.172.
[ bib |
DOI |
.pdf ]
Keywords: algorithmic group theory, algorithms |
| [182] |
László Babai and Daniel Štefankovič.
Simultaneous Diophantine approximation with excluded primes.
In Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'04), pages 1123-1129. ACM-SIAM, SIAM, 2004.
[ bib |
.pdf ]
Keywords: algorithms, lattice_vector, SODA |
| [183] |
László Babai, Anna Gál, Peter Kimmel, and Satyanarayana V. Lokam.
Communication complexity of simultaneous messages.
SIAM J. Comput., 33(1):137-166, 2004.
Greatly expanded version of 1995.142.
[ bib |
DOI |
.pdf ]
Keywords: complexity, communication_complexity, lower_bounds |
| [184] |
László Babai and Thomas Hayes.
Near-independence of permutations and an almost sure polynomial bound
on the diameter of the symmetric group.
In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'05), pages 1057-1066. ACM-SIAM, SIAM, 2005.
[ bib |
.pdf ]
Keywords: algorithmic group theory, algorithms, combinatorics, diameter |
| [185] |
László Babai, Amir Shpilka, and Daniel Štefankovič.
Locally testable cyclic codes.
IEEE Trans. Inform. Theory, 51(8):2849-2858, 2005.
Journal version of 2003.179.
[ bib |
DOI |
.pdf ]
Keywords: complexity, lower_bounds, codes |
| [186] |
László Babai.
On the diameter of Eulerian orientations of graphs.
In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'06), pages 822-831. ACM-SIAM, ACM Press, 2006.
[ bib |
DOI |
.pdf ]
Keywords: algorithms |
| [187] |
László Babai.
Guest Editor's Foreword to the Special Issue dedicated to the
40th ACM Symposium on Theory of Computing.
SIAM J. Comput., 35(4):ix-x, 2006.
[ bib |
DOI ]
Keywords: foreword |
| [188] |
László Babai and Thomas Hayes.
The probability of generating the symmetric group when one of the
generators is random.
Publ. Math. Debrecen, 69(3):271-280, 2006.
[ bib |
.pdf ]
Keywords: groups |
| [189] |
László Babai and Igor Gorodezky.
Sandpile transience on the grid is polynomially bounded.
In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'07), pages 627-636. ACM-SIAM, SIAM, 2007.
[ bib |
.pdf ]
Keywords: algorithms, combinatorics, sandpile |
| [190] |
Miklós Abért and László Babai.
Finite groups of uniform logarithmic diameter.
Israel J. Math, 158(1):193-203, 2007.
[ bib |
DOI |
.pdf ]
Keywords: groups, asymptotic_group_theory, diameter |
| [191] |
László Babai, Nikolai Nikolov, and László Pyber.
Product growth and mixing in finite groups.
In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'08), pages 248-257. ACM-SIAM, SIAM, 2008.
Full paper in preparation.
[ bib |
.pdf ]
Keywords: groups, algorithms, combinatorics |
| [192] |
László Babai and Paolo Codenotti.
Isomorphism of hypergraphs of low rank in moderately exponential
time.
In Proc. 49th FOCS, pages 667-676. IEEE Comp. Soc. Press,
2008.
NSF Grant CCF-0830370.
[ bib |
DOI |
.pdf ]
Keywords: algorithms, isomorphism, graph_isomorphism, FOCS, STOC_FOCS |
| [193] |
László Babai, Péter P. Pálfy, and Jan Saxl.
On the number of p-regular elements in finite simple groups.
LMS Journal of Computation and Mathematics, 12:82-119, 2009.
NSF Grants CCR-9732205 and CCF-0830370.
[ bib |
DOI |
http ]
Keywords: groups, asymptotic_group_theory, statistical_group_theory, matrix_groups, motivated_by |
| [194] |
László Babai, Robert Beals, and Ákos Seress.
Polynomial-time theory of matrix groups.
In Proc. 41st STOC, pages 55-64. ACM Press, 2009.
NSF Grant CCF-0830370.
[ bib |
DOI |
.pdf ]
Keywords: groups, algorithmic_group_theory, algorithms, matrix_groups, random, STOC, STOC_FOCS |
| [195] |
László Babai and Barry Guiduli.
Spectral extrema for graphs: the Zarankiewicz problem.
Electronic J. of Combinatorics, 16(1):R123 (8pp), September
2009.
[ bib |
http ]
Keywords: combinatorics, extremal_combinatorics, spectrum, combinatorics_journals |
| [196] |
László Babai and Pedro Felzenszwalb.
Computing rank-convolutions with a mask.
ACM Trans. Algorithms, 6(1):20:1-20:13, 2009.
[ bib |
DOI |
.pdf ]
Keywords: algorithms, algorithmic_algebra, image_processing |
| [197] |
László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik.
Evasiveness and the distribution of prime numbers.
In Proc. 27th Ann. Symp. on Theoretical Aspects of Comp. Sci.
(STACS 2010), pages 71-82. Schloss Dagstuhl Online Publ., 2010.
NSF Grant CCF-0830370.
[ bib |
DOI ]
Keywords: complexity, lower_bounds, groups, permutation_groups, topology, other_conf |
| [198] |
László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, and
Xiaoming Sun.
Weights of exact threshold functions.
In Proc. 35th Internat. Symp. on Math. Foundations of Computer
Science (MFCS'10), pages 66-77. Springer, 2010.
[ bib |
DOI |
.pdf ]
Keywords: complexity, lower_bounds, other_conf |
| [199] |
László Babai, Paolo Codenotti, Joshua Grochow, and Youming Qiao.
Code equivalence and group isomorphism.
In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA'11), pages 1395-1408. ACM-SIAM, SIAM, 2011.
NSF Grant CCF-0830370.
[ bib |
.pdf ]
Keywords: groups, isomorphism, group_isomorphism, algorithms, algorithmic_group_theory, codes, SODA |
| [200] |
László Babai.
Finite groups and complexity theory: From Leningrad to Saint
Petersburg via Las Vegas.
In A. Kulikov and N. Vereshchagin, editors, Proc. 6th Internat.
Computer Science Symp. in Russia (CSR'11), volume 6651 of LNCS, pages
162-180. Springer, 2011.
[ bib |
DOI ]
Keywords: autobio, survey, groups, algorithms, complexity, isomorphism, graph_isomorphism, algorithmic_group_theory, other_conf |
| [201] |
László Babai and Youming Qiao.
Polynomial-time isomorphism test for groups with abelian Sylow
towers.
In Proc. 29th Symp. Theoretical Aspects of Comp. Sci.
(STACS'12), pages 453-464. Schloss Dagstuhl Online Publ., 2012.
[ bib |
DOI ]
Keywords: groups, isomorphism, group_isomorphism, algorithms, algorithmic_group_theory, other_conf |
| [202] |
László Babai, Paolo Codenotti, and Youming Qiao.
Polynomial-time isomorphism test for groups with no abelian normal
subgroups (extended abstract).
In Proc. 39th Internat. Colloq. on Automata, Languages and
Programming (ICALP'12), pages 51-62. Springer, 2012.
[ bib |
DOI ]
Keywords: groups, isomorphism, group_isomorphism, algorithms, algorithmic_group_theory, asymptotic_group_theory, permutation_groups, codes, other_conf |
| [203] |
László Babai and John Wilmes.
Quasipolynomial-time canonical form for Steiner designs.
In Proc. 45th STOC, pages 261-270. ACM Press, 2013.
[ bib |
DOI ]
Keywords: algorithms, isomorphism, graph_isomorphism, automorphisms, highly_regular, combinatorics, random, STOC, STOC_FOCS |
| [204] |
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes.
Faster canonical forms for strongly regular graphs (extended
abstract).
In Proc. 54th FOCS. IEEE Comp. Soc. Press, 2013.
[ bib ]
Keywords: groups, algorithms, isomorphism, graph_isomorphism, automorphisms, highly_regular, combinatorics, random, FOCS, STOC_FOCS |
This file was generated by bibtex2html 1.91.