# zbMATH — the first resource for mathematics

## Babai, László

Compute Distance To:
 Author ID: babai.laszlo Published as: Babai, L.; Babai, Laszlo; Babai, Lászlo; Babai, László Homepage: http://people.cs.uchicago.edu/~laci/ External Links: MGP · Wikidata · dblp · GND
 Documents Indexed: 168 Publications since 1969, including 1 Book Biographic References: 1 Publication
all top 5

#### Co-Authors

 68 single-authored 10 Seress, Ákos 5 Beals, Robert M. 5 Frankl, Péter 5 Goodman, Albert J. 5 Kimmel, Peter G. 5 Luks, Eugene M. 4 Cameron, Peter Jephson 4 Fortnow, Lance J. 4 Hayes, Thomas P. 4 Imrich, Wilfried 4 Pálfy, Péter Pál 4 Pyber, László 3 Gál, Anna 3 Kantor, William M. 3 Lovász, László 3 Qiao, Youming 3 Rónyai, Lajos 3 Spencer, Joel H. 3 Štefankovič, Daniel 3 Wigderson, Avi 2 Alon, Noga M. 2 Codenotti, Paolo 2 Cooperman, Gene 2 Erdős, Pál 2 Finkelstein, Larry A. 2 Kollár, János 2 Lokam, Satyanarayana V. 2 Lund, Carsten 2 Moran, Shlomo 2 Nešetřil, Jaroslav 2 Nisan, Noam 2 Pak, Igor 2 Sós, Vera Turán 2 Szegedy, Mario 2 Szemerédi, Endre 2 Turán, Gyorgy 2 Wilmes, John 1 Abért, Miklós 1 Adams, Michael E. 1 Arora, Sanjeev 1 Banerjee, Anandam 1 Cai, Jin-Yi 1 Chung Graham, Fan-Rong King 1 Deza, Michel Marie 1 Duffus, Dwight 1 Felzenszwalb, Pedro F. 1 Friedl, Katalin 1 Ganapathy, Murali K. 1 Godsil, Christopher David 1 Gorodezky, Igor 1 Graham, Ronald Lewis 1 Grochow, Joshua A. 1 Guest, Simon D. 1 Guiduli, Barry 1 Hajnal, Péter 1 Hansen, Kristoffer Arnsfelt 1 Hetyei, Gábor 1 Itai, Alon 1 Ivanyos, Gábor 1 Just, Bettina 1 Kulkarni, Raghav 1 Kutin, Samuel A. 1 Lengyel, Tamás 1 Lubotzky, Alexander 1 Máté, Attila 1 Meyer auf der Heide, Friedhelm 1 Naik, Vipul 1 Nikolov, Nikolay Valeriev 1 Oral, Haluk 1 Pastijn, Francis J. 1 Phelps, Kevin T. 1 Podol’skiĭ, Vladimir Vladimirovich 1 Pomerance, Carl Bernard 1 Praeger, Cheryl Elisabeth 1 Pudlák, Pavel 1 Pultr, Aleš 1 Rockmore, Daniel N. 1 Rodl, Vojtech 1 Sabidussi, Gert 1 Saxl, Jan 1 Selkow, Stanley M. 1 Shalev, Aner 1 Shpilka, Amir 1 Sichler, Jiří Jan 1 Simonovits, Miklós 1 Singhi, Navin Madhavprasad 1 Snevily, Hunter S. 1 Stern, Jacques 1 Stricker, Markus Andreas 1 Sun, Xiaoming 1 Suzuki, Hiroyuki 1 Sweedyk, Z. 1 Szabó, Tibor 1 Vértesi, Péter 1 Watkins, Mark E. 1 Wilson, Richard Michael 1 Wilson, Robert Arnott
all top 5

#### Serials

 8 Journal of Combinatorial Theory. Series A 6 Acta Mathematica Academiae Scientiarum Hungaricae 6 Discrete Mathematics 6 Journal of Algebra 5 Journal of Computer and System Sciences 5 Journal of Graph Theory 5 SIAM Journal on Computing 5 European Journal of Combinatorics 5 Combinatorica 4 Computational Complexity 3 Journal of Combinatorial Theory. Series B 2 Communications in Algebra 2 Periodica Mathematica Hungarica 2 Algebra Universalis 2 Journal of the London Mathematical Society. Second Series 2 Monatshefte für Mathematik 2 Studia Scientiarum Mathematicarum Hungarica 2 Journal of Algorithms 2 Information and Computation 2 SIAM Journal on Discrete Mathematics 2 Notices of the American Mathematical Society 2 Combinatorics, Probability and Computing 2 The Electronic Journal of Combinatorics 1 IEEE Transactions on Information Theory 1 Information Processing Letters 1 Israel Journal of Mathematics 1 Wissenschaftliche Zeitschrift der Technischen Hochschule Ilmenau 1 Mathematics of Computation 1 Archiv der Mathematik 1 Canadian Journal of Mathematics 1 Canadian Mathematical Bulletin 1 Compositio Mathematica 1 Geometriae Dedicata 1 Inventiones Mathematicae 1 Journal of Geometry 1 Matematikai Lapok 1 Publicationes Mathematicae 1 Simon Stevin 1 Theoretical Computer Science 1 Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1 Roczniki Polskiego Towarzystwa Matematycznego. Seria II. Wiadomości Matematyczne 1 Analysis 1 Graphs and Combinatorics 1 Journal of the American Mathematical Society 1 Aequationes Mathematicae 1 Journal of Algebraic Combinatorics 1 Journal of Group Theory 1 Annals of Mathematics. Second Series 1 LMS Journal of Computation and Mathematics 1 ACM Transactions on Algorithms
all top 5

#### Fields

 90 Combinatorics (05-XX) 76 Group theory and generalizations (20-XX) 65 Computer science (68-XX) 10 Number theory (11-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 7 Probability theory and stochastic processes (60-XX) 6 Mathematical logic and foundations (03-XX) 6 Information and communication theory, circuits (94-XX) 5 History and biography (01-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 3 Geometry (51-XX) 2 Category theory; homological algebra (18-XX) 2 General topology (54-XX) 2 Manifolds and cell complexes (57-XX) 2 Operations research, mathematical programming (90-XX) 1 General and overarching topics; collections (00-XX) 1 General algebraic systems (08-XX) 1 Field theory and polynomials (12-XX) 1 Real functions (26-XX) 1 Measure and integration (28-XX) 1 Sequences, series, summability (40-XX) 1 Approximations and expansions (41-XX) 1 Convex and discrete geometry (52-XX) 1 Algebraic topology (55-XX) 1 Numerical analysis (65-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX)

#### Citations contained in zbMATH

149 Publications have been cited 2,110 times in 1,606 Documents Cited by Year
A fast and simple randomized parallel algorithm for the maximal independent set problem. Zbl 0631.68063
Alon, Noga; Babai, László; Itai, Alon
1986
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
1991
On Lovász’ lattice reduction and the nearest lattice point problem. Zbl 0593.68030
Babai, L.
1986
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029
Babai, László; Moran, Shlomo
1988
Isomorphism problem for a class of point-symmetric structures. Zbl 0378.05035
Babai, L.
1977
Automorphism groups, isomorphism, reconstruction. Zbl 0846.05042
Babai, László
1995
The hardness of approximate optima in lattices, codes, and systems of linear equations. Zbl 0877.68067
Arora, Sanjeev; Babai, László; Stern, Jacques; Sweedyk, Z.
1997
Spectra of Cayley graphs. Zbl 0338.05110
Babai, Laszlo
1979
On the order of uniprimitive permutation groups. Zbl 0485.20002
Babai, Laszlo
1981
Graph isomorphism in quasipolynomial time (extended abstract). Zbl 1376.68058
Babai, László
2016
$$BPP$$ has subexponential time simulations unless $$EXPTIME$$ has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
1993
Random graph isomorphism. Zbl 0454.05038
Babai, Laszlo; Erdős, Paul; Selkow, Stanley M.
1980
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. Zbl 0751.05009
Alon, N.; Babai, L.; Suzuki, H.
1991
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs. Zbl 0769.68040
Babai, László; Nisan, Noam; Szegedy, Márió
1992
Finite digraphs with given regular automorphism groups. Zbl 0452.05030
Babai, L.
1980
Small-diameter Cayley graphs for finite simple groups. Zbl 0702.05042
Babai, L.; Kantor, W. M.; Lubotzky, A.
1989
Sidon sets in groups and induced subgraphs of Cayley graphs. Zbl 0573.05032
Babai, László; Sós, Vera T.
1985
On the diameter of permutation groups. Zbl 0783.20001
Babai, László; Seress, Ákos
1992
Product growth and mixing in finite groups. Zbl 1192.60016
Babai, László; Nikolov, Nikolay; Pyber, László
2008
On the orders of primitive groups with restricted nonabelian composition factors. Zbl 0493.20001
Babai, L.; Cameron, P. J.; Palfy, P. P.
1982
On the complexity of canonical labeling of strongly regular graphs. Zbl 0446.68052
Babai, Laszlo
1980
Short presentations for finite groups. Zbl 0896.20025
Babai, L.; Goodman, A. J.; Kantor, W. M.; Luks, E. M.; Pálfy, P. P.
1997
Extremal subgraphs of random graphs. Zbl 0738.05048
Babai, László; Simonovits, Miklós; Spencer, Joel
1990
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
1991
The probability of generating the symmetric group. Zbl 0685.60012
Babai, László
1989
On the automorphism groups of almost all Cayley graphs. Zbl 0483.05033
Babai, Laszlo; Godsil, Chris D.
1982
On the order of doubly transitive permutation groups. Zbl 0478.20002
Babai, Laszlo
1982
On the number of $$p$$-regular elements in finite simple groups. Zbl 1225.20013
Babai, László; Pálfy, Péter P.; Saxl, Jan
2009
On the diameter of Cayley graphs of the symmetric group. Zbl 0649.20002
Babai, Lászlo; Seress, Ákos
1988
Asymmetric trees with two prescribed degrees. Zbl 0344.05127
Babai, L.
1977
On the minimum order of graphs with given group. Zbl 0311.05120
Babai, Laszlo
1974
Black-box recognition of finite simple groups of Lie type by statistics of element orders. Zbl 1015.20013
Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos
2002
A polynomial-time theory of black box groups. I. Zbl 0942.20032
Babai, László; Beals, Robert
1999
Isomorphisms of Cayley graphs. I. Zbl 0404.05029
Babai, L.; Frankl, P.
1978
Tournaments with given regular group. Zbl 0422.05034
Babai, L.; Imrich, W.
1979
Random oracles separate PSPACE from the polynomial-time hierarchy. Zbl 0654.68052
Babai, László
1987
On the length of subgroup chains in the symmetric group. Zbl 0604.20004
Babai, László
1986
An anti-Ramsey theorem. Zbl 0581.05040
Babai, László
1985
Some applications of graph contractions. Zbl 0381.05029
Babai, Laszlo
1977
Polynomial-time theory of matrix groups. Zbl 1304.68065
Babai, László; Beals, Robert; Seress, Ákos
2009
Superpolynomial lower bounds for monotone span programs. Zbl 0990.68077
Babai, László; Gál, Anna; Wigderson, Avi
1999
Fast Monte Carlo algorithms for permutation groups. Zbl 0834.20002
Babai, László; Cooperman, Gene; Finkelstein, Larry; Luks, Eugene; Seress, Ákos
1995
On graphs which contain all sparse graphs. Zbl 0495.05035
Babai, Laszlo; Chung, F. R. K.; Erdős, Paul; Graham, Ronald L.; Spencer, J. H.
1982
On the abstract group of automorphisms. Zbl 0467.05031
Babai, Laszlo
1981
On the number of zero-patterns of a sequence of polynomials. Zbl 0978.12001
Rónyai, Lajos; Babai, László; Ganapathy, Murali K.
2001
Multiplicative equations over commuting matrices. Zbl 0865.15012
Babai, László; Beals, Robert; Cai, Jin-yi; Ivanyos, Gábor; Luks, Eugene M.
1996
Vertex-transitive graphs and vertex-transitive maps. Zbl 0743.05020
Babai, László
1991
Computing irreducible representations of finite groups. Zbl 0760.20002
Babai, László; Rónyai, Lajos
1990
Recognizing simplicity of black-box groups and the frequency of $$p$$-singular elements in affine groups. Zbl 1052.20031
Babai, László; Shalev, Aner
2001
Randomization in group algorithms: Conceptual questions. Zbl 0871.68107
Babai, László
1997
Deciding finiteness of matrix groups in deterministic polynomial time. Zbl 0925.20001
Babai, László; Beals, Robert; Rockmore, Daniel
1993
Local expansion of symmetrical graphs. Zbl 0792.05064
Babai, László; Szegedy, Mario
1992
Isomorphisms of Cayley graphs. II. Zbl 0449.05029
Babai, L.; Frankl, P.
1979
Spectral extrema for graphs: the Zarankiewicz problem. Zbl 1186.05079
Babai, László; Guiduli, Barry
2009
On the diameter of Eulerian orientations of graphs. Zbl 1192.05084
Babai, László
2006
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. Zbl 1297.68080
Babai, László; Hayes, Thomas P.
2005
On the diameter of the symmetric group: polynomial bounds. Zbl 1318.20002
Babai, László; Beals, Robert; Seress, Ákos
2004
Communication complexity of simultaneous messages. Zbl 1069.68051
Babai, László; Gál, Anna; Kimmel, Peter G.; Lokam, Satyanarayana V.
2003
Bounded round interactive proofs in finite groups. Zbl 0741.68047
Babai, László
1992
Dimension and automorphism groups of lattices. Zbl 0495.06002
Babai, L.; Duffus, D.
1981
Almost all Steiner triple systems are asymmetric. Zbl 0462.05013
Babai, Laszlo
1980
Infinite digraphs with given regular automorphism groups. Zbl 0392.05032
Babai, Laszlo
1978
Automorphism groups of graphs and edge-contraction. Zbl 0274.05108
Babai, László
1974
Locally testable cyclic codes. Zbl 1284.94156
Babai, László; Shpilka, Amir; Štefankovič, Daniel
2005
A new proof of several inequalities on codes and sets. Zbl 0826.05053
Babai, Laszlo; Snevily, Hunter; Wilson, Richard M.
1995
Permutation groups without exponentially many orbits on the power set. Zbl 0803.20001
Babai, László; Pyber, László
1994
On set intersections. Zbl 0432.05002
Babai, Laszlo
1980
Connectivity of infinite graphs having a transitive torsion group action. Zbl 0416.05056
Babai, Laszlo; Watkins, Mark E.
1980
Long cycles in vertex-transitive graphs. Zbl 0414.05032
Babai, Laszlo
1979
Automorphisms and enumeration of switching classes of tournaments. Zbl 0956.05050
Babai, L.; Cameron, P. J.
2000
Groups without faithful transitive permutation representations of small degree. Zbl 0886.20020
Babai, László; Goodman, Albert J.; Pyber, László
1997
A lower bound for read-once-only branching programs. Zbl 0652.68062
Babai, László; Hajnal, Péter; Szemerédi, Endre; Turán, György
1987
Arc transitive covering digraphs and their eigenvalues. Zbl 0583.05030
Babai, L.
1985
Moderately exponential bound for graph isomorphism. Zbl 0462.68040
Babai, Laszlo
1981
Vector representable matroids of given rank with given automorphism group. Zbl 0395.05023
Babai, Laszlo
1978
Code equivalence and group isomorphism. Zbl 1382.20037
Babai, László; Codenotti, Paolo; Grochow, Joshua A.; Qiao, Youming
2011
Strong bias of group generators: an obstacle to the “product replacement algorithm”. Zbl 1005.20055
Babai, László; Pak, Igor
2000
The growth rate of vertex-transitive planar graphs. Zbl 1321.05059
Babai, László
1997
A convergence criterion for recurrent sequences with application to the partition lattice. Zbl 0755.40002
Babai, László; Lengyel, Tamás
1992
Lower bounds to the complexity of symmetric Boolean functions. Zbl 0701.68044
Babai, L.; Pudlák, P.; Rödl, Vojtěch; Szemeredi, E.
1990
A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality. Zbl 0693.05003
Babai, L.
1988
On the degree of transitivity of permutation groups: A short proof. Zbl 0616.20002
Babai, László; Seress, Ákos
1987
Symmetry groups of vertex-transitive polytopes. Zbl 0388.05025
Babai, L.
1977
The cost of the missing bit: Communication complexity with help. Zbl 0996.68057
Babai, László; Hayes, Thomas P.; Kimmel, Peter G.
2001
Set systems with restricted intersections modulo prime powers. Zbl 0971.05107
Babai, László; Frankl, Péter; Kutin, Samuel; Štefanković, Daniel
2001
Randomized simultaneous messages: Solution of a problem of Gao in communication complexity. Zbl 0995.68052
Babai, Laszlo; Kimmel, Peter G.
1997
On the diameter of random Cayley graphs of the symmetric group. Zbl 0793.05064
Babai, L.; Hetyei, G. L.
1992
Endomorphism monoids and topological subgraphs of graphs. Zbl 0437.05029
Babai, Laszlo; Pultr, Ales
1980
High chromatic rigid graphs I. Zbl 0407.05038
Babai, Laszlo; Nešetřil, Jaroslav
1978
Groups of graphs on given surfaces. Zbl 0261.05115
Babai, L.
1973
Proportions of $$r$$-regular elements in finite classical groups. Zbl 1281.20058
Babai, László; Guest, Simon; Praeger, Cheryl E.; Wilson, Robert A.
2013
Polynomial-time isomorphism test for groups with abelian Sylow towers. Zbl 1248.20001
Babai, László; Qiao, Youming
2012
Fast management of permutation groups. I. Zbl 0885.68090
Babai, László; Luks, Eugene M.; Seress, Ákos
1997
Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs. Zbl 0915.05076
Babai, László; Gál, Anna; Kollár, János; Rónyai, Lajos; Szabó, Tibor; Wigderson, Avi
1996
Simultaneous messages vs. communication. Zbl 1379.68125
Babai, László; Kimmel, Peter G.; Lokam, Satyanarayana V.
1995
On a conjecture of M. E. Watkins on graphical regular representations of finite groups. Zbl 0401.20004
Babai, Laszlo
1978
Permutation groups and almost regular graphs. Zbl 0274.05110
Babai, L.; Lovász, László
1974
Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract). Zbl 1272.68475
Babai, László; Codenotti, Paolo; Qiao, Youming
2012
Weights of exact threshold functions. Zbl 1287.94129
Babai, László; Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.; Sun, Xiaoming
2010
The cost of the missing bit: Communication complexity with help. Zbl 1052.68623
Babai, László; Hayes, Thomas P.; Kimmel, Peter G.
1998
Graph isomorphism in quasipolynomial time (extended abstract). Zbl 1376.68058
Babai, László
2016
Asymptotic Delsarte cliques in distance-regular graphs. Zbl 1339.05083
Babai, László; Wilmes, John
2016
Most primitive groups are full automorphism groups of edge-transitive hypergraphs. Zbl 1321.20001
Babai, László; Cameron, Peter J.
2015
On the automorphism groups of strongly regular graphs. II. Zbl 1350.20003
Babai, László
2015
On the automorphism groups of strongly regular graphs. I. Zbl 1365.05202
Babai, László
2014
Proportions of $$r$$-regular elements in finite classical groups. Zbl 1281.20058
Babai, László; Guest, Simon; Praeger, Cheryl E.; Wilson, Robert A.
2013
Quasipolynomial-time canonical form for Steiner designs. Zbl 1293.05028
Babai, László; Wilmes, John
2013
Polynomial-time isomorphism test for groups with abelian Sylow towers. Zbl 1248.20001
Babai, László; Qiao, Youming
2012
Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract). Zbl 1272.68475
Babai, László; Codenotti, Paolo; Qiao, Youming
2012
Code equivalence and group isomorphism. Zbl 1382.20037
Babai, László; Codenotti, Paolo; Grochow, Joshua A.; Qiao, Youming
2011
Weights of exact threshold functions. Zbl 1287.94129
Babai, László; Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.; Sun, Xiaoming
2010
Evasiveness and the distribution of prime numbers. Zbl 1230.68098
Babai, László; Banerjee, Anandam; Kulkarni, Raghav; Naik, Vipul
2010
On the number of $$p$$-regular elements in finite simple groups. Zbl 1225.20013
Babai, László; Pálfy, Péter P.; Saxl, Jan
2009
Polynomial-time theory of matrix groups. Zbl 1304.68065
Babai, László; Beals, Robert; Seress, Ákos
2009
Spectral extrema for graphs: the Zarankiewicz problem. Zbl 1186.05079
Babai, László; Guiduli, Barry
2009
Computing rank-convolutions with a mask. Zbl 1298.94022
Babai, László; Felzenszwalb, Pedro F.
2009
Product growth and mixing in finite groups. Zbl 1192.60016
Babai, László; Nikolov, Nikolay; Pyber, László
2008
Sandpile transience on the grid is polynomially bounded. Zbl 1302.82065
Babai, László; Gorodezky, Igor
2007
Finite groups of uniform logarithmic diameter. Zbl 1145.20022
Abért, Miklós; Babai, László
2007
On the diameter of Eulerian orientations of graphs. Zbl 1192.05084
Babai, László
2006
The probability of generating the symmetric group when one of the generators is random. Zbl 1123.20003
Babai, László; Hayes, Thomas P.
2006
Automorphism groups of graphs and edge-contraction. (Reprint). Zbl 1093.05028
Babai, László
2006
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. Zbl 1297.68080
Babai, László; Hayes, Thomas P.
2005
Locally testable cyclic codes. Zbl 1284.94156
Babai, László; Shpilka, Amir; Štefankovič, Daniel
2005
On the diameter of the symmetric group: polynomial bounds. Zbl 1318.20002
Babai, László; Beals, Robert; Seress, Ákos
2004
Strong bias of group generators: an obstacle to the “product replacement algorithm”. Zbl 1075.68103
Babai, László; Pak, Igor
2004
Communication complexity of simultaneous messages. Zbl 1069.68051
Babai, László; Gál, Anna; Kimmel, Peter G.; Lokam, Satyanarayana V.
2003
Black-box recognition of finite simple groups of Lie type by statistics of element orders. Zbl 1015.20013
Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos
2002
On the number of zero-patterns of a sequence of polynomials. Zbl 0978.12001
Rónyai, Lajos; Babai, László; Ganapathy, Murali K.
2001
Recognizing simplicity of black-box groups and the frequency of $$p$$-singular elements in affine groups. Zbl 1052.20031
Babai, László; Shalev, Aner
2001
The cost of the missing bit: Communication complexity with help. Zbl 0996.68057
Babai, László; Hayes, Thomas P.; Kimmel, Peter G.
2001
Set systems with restricted intersections modulo prime powers. Zbl 0971.05107
Babai, László; Frankl, Péter; Kutin, Samuel; Štefanković, Daniel
2001
Automorphisms and enumeration of switching classes of tournaments. Zbl 0956.05050
Babai, L.; Cameron, P. J.
2000
Strong bias of group generators: an obstacle to the “product replacement algorithm”. Zbl 1005.20055
Babai, László; Pak, Igor
2000
A polynomial-time theory of black box groups. I. Zbl 0942.20032
Babai, László; Beals, Robert
1999
Superpolynomial lower bounds for monotone span programs. Zbl 0990.68077
Babai, László; Gál, Anna; Wigderson, Avi
1999
The forbidden sidetrip. Zbl 0932.01038
Babai, László
1999
The cost of the missing bit: Communication complexity with help. Zbl 1052.68623
Babai, László; Hayes, Thomas P.; Kimmel, Peter G.
1998
The hardness of approximate optima in lattices, codes, and systems of linear equations. Zbl 0877.68067
Arora, Sanjeev; Babai, László; Stern, Jacques; Sweedyk, Z.
1997
Short presentations for finite groups. Zbl 0896.20025
Babai, L.; Goodman, A. J.; Kantor, W. M.; Luks, E. M.; Pálfy, P. P.
1997
Randomization in group algorithms: Conceptual questions. Zbl 0871.68107
Babai, László
1997
Groups without faithful transitive permutation representations of small degree. Zbl 0886.20020
Babai, László; Goodman, Albert J.; Pyber, László
1997
The growth rate of vertex-transitive planar graphs. Zbl 1321.05059
Babai, László
1997
Randomized simultaneous messages: Solution of a problem of Gao in communication complexity. Zbl 0995.68052
Babai, Laszlo; Kimmel, Peter G.
1997
Fast management of permutation groups. I. Zbl 0885.68090
Babai, László; Luks, Eugene M.; Seress, Ákos
1997
Communication complexity. Zbl 0941.68088
Babai, László
1997
Multiplicative equations over commuting matrices. Zbl 0865.15012
Babai, László; Beals, Robert; Cai, Jin-yi; Ivanyos, Gábor; Luks, Eugene M.
1996
Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs. Zbl 0915.05076
Babai, László; Gál, Anna; Kollár, János; Rónyai, Lajos; Szabó, Tibor; Wigderson, Avi
1996
In and out of Hungary: Paul Erdős, his friends, and times. Zbl 0849.01024
Babai, Laszlo
1996
Automorphism groups, isomorphism, reconstruction. Zbl 0846.05042
Babai, László
1995
Fast Monte Carlo algorithms for permutation groups. Zbl 0834.20002
Babai, László; Cooperman, Gene; Finkelstein, Larry; Luks, Eugene; Seress, Ákos
1995
A new proof of several inequalities on codes and sets. Zbl 0826.05053
Babai, Laszlo; Snevily, Hunter; Wilson, Richard M.
1995
Simultaneous messages vs. communication. Zbl 1379.68125
Babai, László; Kimmel, Peter G.; Lokam, Satyanarayana V.
1995
E-mail and the unexpected power of interaction. Zbl 0906.68072
Babai, László
1995
Permutation groups without exponentially many orbits on the power set. Zbl 0803.20001
Babai, László; Pyber, László
1994
Eulerian self-dual codes. Zbl 0792.94006
Babai, L.; Oral, H.; Phelps, K. T.
1994
Transparent proofs and limits to approximation. Zbl 0826.68108
Babai, László
1994
$$BPP$$ has subexponential time simulations unless $$EXPTIME$$ has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
1993
Deciding finiteness of matrix groups in deterministic polynomial time. Zbl 0925.20001
Babai, László; Beals, Robert; Rockmore, Daniel
1993
Subdirectly reducible groups and edge-minimal graphs with given automorphism group. Zbl 0791.20012
Babai, László; Goodman, Albert J.
1993
Decomposition of *-closed algebras in polynomial time. Zbl 0927.68121
Babai, László; Friedl, Katalin; Stricker, Markus
1993
On faithful permutation representations of small degree. Zbl 0797.20003
Babai, László; Goodman, Albert J.; Pyber, László
1993
Transparent (holographic) proofs. Zbl 0790.68043
Babai, László
1993
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs. Zbl 0769.68040
Babai, László; Nisan, Noam; Szegedy, Márió
1992
On the diameter of permutation groups. Zbl 0783.20001
Babai, László; Seress, Ákos
1992
Local expansion of symmetrical graphs. Zbl 0792.05064
Babai, László; Szegedy, Mario
1992
Bounded round interactive proofs in finite groups. Zbl 0741.68047
Babai, László
1992
A convergence criterion for recurrent sequences with application to the partition lattice. Zbl 0755.40002
Babai, László; Lengyel, Tamás
1992
On the diameter of random Cayley graphs of the symmetric group. Zbl 0793.05064
Babai, L.; Hetyei, G. L.
1992
Deciding finiteness of matrix groups in Las Vegas polynomial time. Zbl 0828.20032
Babai, László
1992
Addendum to: Non-deterministic exponential time has two-prower interactive protocols. Zbl 0796.68096
Babai, L.; Fortnow, L.; Lund, C.
1992
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
1991
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. Zbl 0751.05009
Alon, N.; Babai, L.; Suzuki, H.
1991
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
1991
Vertex-transitive graphs and vertex-transitive maps. Zbl 0743.05020
Babai, László
1991
Computational complexity in finite groups. Zbl 0747.68030
Babai, László
1991
Nearly linear time algorithms for permutation groups with a small base. Zbl 0925.20011
Babai, László; Cooperman, Gene; Finkelstein, Larry; Seress, Ákos
1991
Extremal subgraphs of random graphs. Zbl 0738.05048
Babai, László; Simonovits, Miklós; Spencer, Joel
1990
Computing irreducible representations of finite groups. Zbl 0760.20002
Babai, László; Rónyai, Lajos
1990
Lower bounds to the complexity of symmetric Boolean functions. Zbl 0701.68044
Babai, L.; Pudlák, P.; Rödl, Vojtěch; Szemeredi, E.
1990
Small-diameter Cayley graphs for finite simple groups. Zbl 0702.05042
Babai, L.; Kantor, W. M.; Lubotzky, A.
1989
The probability of generating the symmetric group. Zbl 0685.60012
Babai, László
1989
Proving properties of interactive proofs by a generalized counting technique. Zbl 0684.68068
Babai, László; Moran, Shlomo
1989
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029
Babai, László; Moran, Shlomo
1988
On the diameter of Cayley graphs of the symmetric group. Zbl 0649.20002
Babai, Lászlo; Seress, Ákos
1988
A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality. Zbl 0693.05003
Babai, L.
1988
On the limits of computations with the floor function. Zbl 0659.68051
Babai, László; Just, Bettina; Meyer auf der Heide, Friedhelm
1988
Random oracles separate PSPACE from the polynomial-time hierarchy. Zbl 0654.68052
Babai, László
1987
A lower bound for read-once-only branching programs. Zbl 0652.68062
Babai, László; Hajnal, Péter; Szemerédi, Endre; Turán, György
1987
On the degree of transitivity of permutation groups: A short proof. Zbl 0616.20002
Babai, László; Seress, Ákos
1987
On the nonuniform Fisher inequality. Zbl 0652.05043
Babai, László
1987
The complexity of defining a relation on a finite graph. Zbl 0638.03043
Babai, L.; Turán, Gy.
1987
A fast and simple randomized parallel algorithm for the maximal independent set problem. Zbl 0631.68063
Alon, Noga; Babai, László; Itai, Alon
1986
On Lovász’ lattice reduction and the nearest lattice point problem. Zbl 0593.68030
Babai, L.
1986
On the length of subgroup chains in the symmetric group. Zbl 0604.20004
Babai, László
1986
Sidon sets in groups and induced subgraphs of Cayley graphs. Zbl 0573.05032
Babai, László; Sós, Vera T.
1985
An anti-Ramsey theorem. Zbl 0581.05040
Babai, László
1985
Arc transitive covering digraphs and their eigenvalues. Zbl 0583.05030
Babai, L.
1985
On the orders of primitive groups with restricted nonabelian composition factors. Zbl 0493.20001
Babai, L.; Cameron, P. J.; Palfy, P. P.
1982
On the automorphism groups of almost all Cayley graphs. Zbl 0483.05033
Babai, Laszlo; Godsil, Chris D.
1982
...and 49 more Documents
all top 5

#### Cited by 2,096 Authors

 51 Babai, László 26 Alon, Noga M. 21 Spiga, Pablo 20 Shalev, Aner 19 Cai, Jin-Yi 18 Li, Caiheng 17 Kantor, William M. 16 Praeger, Cheryl Elisabeth 15 Dobson, Edward 14 Feng, Yanquan 14 Fortnow, Lance J. 14 Goldreich, Oded 14 O’Brien, Eamonn A. 14 Pyber, László 13 Arvind, Vikraman 13 Frankl, Péter 13 Nešetřil, Jaroslav 13 Seress, Ákos 12 Cameron, Peter Jephson 12 Liebeck, Martin Walter 11 Grech, Mariusz 11 Imrich, Wilfried 11 Ponomarenko, Ilya Nikolaevich 10 Leedham-Green, Charles R. 10 Lubotzky, Alexander 10 Muzychuk, Mikhail E. 10 Wigderson, Avi 10 Xu, Mingyao 9 Kisielewicz, Andrzej Piotr 9 Köbler, Johannes 9 Rodl, Vojtech 9 Rubinfeld, Ronitt 9 Seifter, Norbert 8 Allender, Eric W. 8 Furedi, Zoltan 8 Godsil, Christopher David 8 Guralnick, Robert Michael 8 Huang, Qiongxiang 8 Liu, Jiuqiang 8 Maróti, Attila 8 Meng, Jixiang 7 Balogh, József 7 Burness, Timothy C. 7 Håstad, Johan Torkel 7 Kovács, István 7 Pálfy, Péter Pál 7 Raĭgorodskiĭ, Andreĭ Mikhaĭlovich 7 Saks, Michael E. 7 Srinivasan, Aravind 7 Sudan, Madhu 7 Vinodchandran, N. Variyam 7 Viola, Emanuele 7 Wong, Kok Bin 7 Zuckerman, David 6 Beimel, Amos 6 Ben-Sasson, Eli 6 Das, Bireswar 6 Detinko, Alla S. 6 Feige, Uriel 6 Flannery, Dane Laurence 6 Helfgott, Harald Andrés 6 Hemaspaandra, Lane A. 6 Kassabov, Martin 6 Kohayakawa, Yoshiharu 6 Ku, Cheng Yeaw 6 Morris, Joy 6 Nikolov, Nikolay Valeriev 6 Rónyai, Lajos 6 Shaltiel, Ronen 6 Vidick, Thomas 5 Abdollahi, Alireza 5 Ferber, Asaf 5 Gál, Anna 5 Georgakopoulos, Agelos 5 Gill, Nick 5 Holt, Derek F. 5 Hwang, Kyung-Won 5 Impagliazzo, Russell 5 Lau, Terry Shue Chien 5 Lucchini, Andrea 5 Meagher, Karen 5 Morris, Robert D. 5 Nguyen, Phong Q. 5 Niemeyer, Alice C. 5 Robson, John Michael 5 Samotij, Wojciech 5 Torán, Jacobo 5 Tucker, Thomas W. 5 Zemmari, Akka 4 Applebaum, Benny 4 Bäärnhielm, Henrik 4 Behrendt, Gerhard 4 Bollig, Beate 4 Breuillard, Emmanuel 4 Bshouty, Nader H. 4 Buhrman, Harry 4 Chen, Wenbin 4 Chiesa, Alessandro 4 Conder, Marston D. E. 4 Condon, Anne E. ...and 1,996 more Authors
all top 5

#### Cited in 242 Serials

 124 Discrete Mathematics 91 Theoretical Computer Science 71 Journal of Computer and System Sciences 69 Journal of Algebra 57 European Journal of Combinatorics 50 Journal of Combinatorial Theory. Series A 50 Computational Complexity 41 Information Processing Letters 39 Combinatorica 32 Journal of Combinatorial Theory. Series B 31 Journal of Algebraic Combinatorics 24 Algorithmica 23 Linear Algebra and its Applications 22 Information and Computation 21 Israel Journal of Mathematics 21 Designs, Codes and Cryptography 20 Discrete Applied Mathematics 20 SIAM Journal on Computing 20 Journal of Symbolic Computation 20 Distributed Computing 18 Transactions of the American Mathematical Society 18 Combinatorics, Probability and Computing 18 Theory of Computing Systems 17 Journal of Mathematical Sciences (New York) 16 Graphs and Combinatorics 15 Random Structures & Algorithms 14 Journal of Cryptology 12 Archiv der Mathematik 11 Mathematics of Computation 11 Advances in Mathematics 11 Journal of Graph Theory 11 The Electronic Journal of Combinatorics 10 Communications in Algebra 10 SIAM Journal on Discrete Mathematics 10 Journal of Group Theory 9 Bulletin of the Australian Mathematical Society 9 Journal of Combinatorial Optimization 8 Journal of Pure and Applied Algebra 8 Journal of the American Mathematical Society 8 Journal of Algebra and its Applications 7 Mathematical Systems Theory 7 Monatshefte für Mathematik 7 Journal of Combinatorial Designs 6 Acta Mathematica Academiae Scientiarum Hungaricae 6 Journal of Soviet Mathematics 6 Advances in Applied Mathematics 6 Annals of Pure and Applied Logic 6 Order 6 International Journal of Foundations of Computer Science 6 Mathematical Programming. Series A. Series B 6 Journal of the European Mathematical Society (JEMS) 5 Duke Mathematical Journal 5 Inventiones Mathematicae 5 Proceedings of the American Mathematical Society 5 Discrete & Computational Geometry 5 International Journal of Algebra and Computation 5 Geometric and Functional Analysis. GAFA 5 Bulletin of the American Mathematical Society. New Series 5 Applicable Algebra in Engineering, Communication and Computing 5 Groups, Geometry, and Dynamics 4 Mathematical Proceedings of the Cambridge Philosophical Society 4 Algebra Universalis 4 Mathematische Annalen 4 Journal of Complexity 4 Science in China. Series A 4 Aequationes Mathematicae 4 The Bulletin of Symbolic Logic 4 Acta Mathematica Sinica. English Series 4 RAIRO. Theoretical Informatics and Applications 4 Quantum Information Processing 4 Discrete Optimization 4 Journal of Mathematical Cryptology 3 Linear and Multilinear Algebra 3 Periodica Mathematica Hungarica 3 Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 3 The Annals of Probability 3 Applied Mathematics and Computation 3 Journal of Number Theory 3 The Journal of Symbolic Logic 3 Proceedings of the Edinburgh Mathematical Society. Series II 3 Semigroup Forum 3 Journal of Global Optimization 3 RAIRO. Informatique Théorique et Applications 3 Journal of the ACM 3 Annals of Mathematics. Second Series 3 Journal of the Australian Mathematical Society 3 Discrete Mathematics, Algorithms and Applications 3 Forum of Mathematics, Sigma 2 Acta Informatica 2 Communications in Mathematical Physics 2 Journal d’Analyse Mathématique 2 Journal of Geometry and Physics 2 Beiträge zur Algebra und Geometrie 2 Journal of Computational and Applied Mathematics 2 Manuscripta Mathematica 2 Mathematische Nachrichten 2 Mathematische Zeitschrift 2 Numerical Functional Analysis and Optimization 2 Siberian Mathematical Journal 2 SIAM Journal on Algebraic and Discrete Methods ...and 142 more Serials
all top 5

#### Cited in 51 Fields

 746 Combinatorics (05-XX) 625 Computer science (68-XX) 451 Group theory and generalizations (20-XX) 165 Information and communication theory, circuits (94-XX) 121 Number theory (11-XX) 70 Mathematical logic and foundations (03-XX) 48 Operations research, mathematical programming (90-XX) 42 Probability theory and stochastic processes (60-XX) 35 Quantum theory (81-XX) 29 Linear and multilinear algebra; matrix theory (15-XX) 28 Convex and discrete geometry (52-XX) 27 Geometry (51-XX) 23 Order, lattices, ordered algebraic structures (06-XX) 22 Numerical analysis (65-XX) 20 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Manifolds and cell complexes (57-XX) 13 Algebraic geometry (14-XX) 12 Associative rings and algebras (16-XX) 10 Topological groups, Lie groups (22-XX) 10 Statistics (62-XX) 10 Statistical mechanics, structure of matter (82-XX) 9 Field theory and polynomials (12-XX) 7 General algebraic systems (08-XX) 6 History and biography (01-XX) 6 Commutative algebra (13-XX) 6 Biology and other natural sciences (92-XX) 5 Category theory; homological algebra (18-XX) 5 Functional analysis (46-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Abstract harmonic analysis (43-XX) 3 Nonassociative rings and algebras (17-XX) 3 Measure and integration (28-XX) 3 Difference and functional equations (39-XX) 3 Harmonic analysis on Euclidean spaces (42-XX) 3 Differential geometry (53-XX) 3 Global analysis, analysis on manifolds (58-XX) 3 Systems theory; control (93-XX) 2 General and overarching topics; collections (00-XX) 2 Special functions (33-XX) 2 Ordinary differential equations (34-XX) 2 General topology (54-XX) 2 Geophysics (86-XX) 1 $$K$$-theory (19-XX) 1 Real functions (26-XX) 1 Functions of a complex variable (30-XX) 1 Potential theory (31-XX) 1 Partial differential equations (35-XX) 1 Sequences, series, summability (40-XX) 1 Approximations and expansions (41-XX) 1 Operator theory (47-XX) 1 Algebraic topology (55-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.