László Babai
#2,852
Most Influential Person Now
Hungarian mathematician and computer scientist
László Babai's AcademicInfluence.com Rankings
László Babaimathematics Degrees
Mathematics
#227
World Rank
#497
Historical Rank
Complexity Theory
#2
World Rank
#2
Historical Rank
Group Theory
#12
World Rank
#16
Historical Rank
Graph Theory
#41
World Rank
#48
Historical Rank
Download Badge
Computer Science Mathematics
László Babai's Degrees
- PhD Mathematics Eötvös Loránd University
Why Is László Babai Influential?
(Suggest an Edit or Addition)According to Wikipedia, László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.
László Babai's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- On Lovász’ lattice reduction and the nearest lattice point problem (1986) (981)
- Trading group theory for randomness (1985) (788)
- A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem (1985) (768)
- Checking computations in polylogarithmic time (1991) (625)
- Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes (1988) (595)
- Graph Isomorphism in Quasipolynomial Time (2015) (565)
- Non-deterministic exponential time has two-prover interactive protocols (2005) (486)
- The hardness of approximate optima in lattices, codes, and systems of linear equations (1993) (484)
- Canonical labeling of graphs (1983) (421)
- BPP has subexponential time simulations unlessEXPTIME has publishable proofs (1991) (329)
- Complexity classes in communication complexity theory (1986) (320)
- Non-deterministic exponential time has two-prover interactive protocols (1990) (319)
- Random Graph Isomorphism (1980) (299)
- Automorphism groups, isomorphism, reconstruction (1996) (288)
- Graph isomorphism in quasipolynomial time [extended abstract] (2016) (283)
- Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs (1992) (270)
- On the Complexity of Matrix Group Problems I (1984) (230)
- Local expansion of vertex-transitive graphs and random generation in finite groups (1991) (208)
- Spectra of Cayley graphs (1979) (202)
- Isomorphism problem for a class of point-symmetric structures (1977) (190)
- Canonical labelling of graphs in linear average time (1979) (190)
- Isomorphism of graphs with bounded eigenvalue multiplicity (1982) (186)
- On the Order of Uniprimitive Permutation Groups (1981) (172)
- Computational complexity and the classification of finite simple groups (1983) (150)
- Multiparty protocols and logspace-hard pseudorandom sequences (1989) (123)
- Monte-Carlo algorithms in graph isomorphism testing (2006) (114)
- Permutation groups in NC (1987) (112)
- Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs (1985) (110)
- Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems (1991) (110)
- On the orders of primitive groups with restricted nonabelian composition factors (1982) (98)
- Moderately Exponential Bound for Graph Isomorphism (1981) (89)
- Complexity classes in communication complexity theory (preliminary version) (1986) (89)
- Fast Monte Carlo algorithms for permutation groups (1991) (88)
- On the Complexity of Canonical Labeling of Strongly Regular Graphs (1980) (85)
- Small-diameter Cayley Graphs for Finite Simple Groups (1989) (84)
- Randomized simultaneous messages: solution of a problem of Yao in communication complexity (1997) (83)
- Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy (1987) (82)
- Multiplicative equations over commuting matrices (1996) (81)
- Superpolynomial Lower Bounds for Monotone Span Programs (1996) (80)
- Product growth and mixing in finite groups (2008) (79)
- Two lower bounds for branching programs (1986) (77)
- On the order of doubly transitive permutation groups (1982) (75)
- Bounds on the diameter of Cayley graphs of the symmetric group (1988) (72)
- Communication Complexity of Simultaneous Messages (2003) (69)
- On the diameter of permutation groups (1992) (67)
- Finite digraphs with given regular automorphism groups (1980) (66)
- Groups St Andrews 1997 in Bath, I: A polynomial-time theory of black box groups I (1999) (61)
- Code equivalence and group isomorphism (2011) (61)
- Isomorphisms of Cayley graphs. II (1979) (61)
- On the Automorphism Groups of almost all Cayley Graphs (1982) (60)
- Short Presentations for Finite Groups (1992) (60)
- On the diameter of finite groups (1990) (60)
- On the length of subgroup chains in the symmetric group (1986) (59)
- Fast management of permutation groups (1988) (57)
- Vertex-transitive graphs and vertex-transitive maps (1991) (55)
- Spectral Extrema for Graphs: The Zarankiewicz Problem (2009) (55)
- The Cost of the Missing Bit: Communication Complexity with Help (1998) (54)
- Local Expansion of Symmetrical Graphs (1992) (53)
- Randomization in group algorithms: Conceptual questions (1995) (52)
- Asymmetric trees with two prescribed degrees (1977) (52)
- On the Number of p -Regular Elements in Finite Simple Groups (2009) (52)
- On the Minimum Order of Graphs with Given Group (1974) (51)
- On graphs which contain all sparse graphs (1982) (51)
- On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version) (1985) (50)
- Computing irreducible representations of finite groups (1989) (49)
- Bounded Round Interactive Proofs in Finite Groups (1992) (49)
- Nearly linear time algorithms for permutation groups with a small base (1991) (49)
- E-mail and the unexpected power of interaction (1990) (48)
- Black-box recognition of finite simple groups of Lie type by statistics of element orders (2002) (48)
- The probability of generating the symmetric group (1989) (47)
- Las Vegas algorithms for matrix groups (1993) (46)
- Polynomial-time theory of matrix groups (2009) (45)
- The growth rate of vertex-transitive planar graphs (1997) (45)
- Simultaneous Messages vs. Communication (1995) (42)
- Representation of Group Elements as Short Products (1982) (42)
- On the number of zero-patterns of a sequence of polynomials (2001) (42)
- Lower Bounds to the Complexity of Symmetric Boolean Functions (1990) (40)
- Arithmetization: A new method in structural complexity theory (1991) (40)
- Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004) (38)
- GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM (2019) (37)
- Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs (1996) (37)
- Some applications of graph contractions (1977) (36)
- Deciding finiteness of matrix groups in deterministic polynomial time (1993) (36)
- Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time (2008) (35)
- Transparent Proofs and Limits to Approximation (1994) (35)
- Strong bias of group generators: an obstacle to the “product replacement algorithm” (2000) (33)
- Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract) (2012) (33)
- The Mathematics of Paul Erdős I (2013) (32)
- Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group (2005) (32)
- On the diameter of the symmetric group: polynomial bounds (2004) (31)
- On the diameter of Eulerian orientations of graphs (2006) (31)
- Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers (2012) (30)
- Almost All Steiner Triple Systems Are Asymmetric (1980) (29)
- Automorphism groups of graphs and edge-contraction (1974) (29)
- Automorphism groups of planar graphs I (1972) (29)
- Groups without Faithful Transitive Permutation Representations of Small Degree (1997) (28)
- Long cycles in vertex-transitive graphs (1979) (28)
- Tournaments with given regular group (1978) (27)
- On the degree of transitivity of permutation groups: A short proof (1987) (27)
- Faster Canonical Forms for Strongly Regular Graphs (2013) (27)
- Automorphisms and Enumeration of Switching Classes of Tournaments (2000) (26)
- A Lower Bound for Read-Once-Only Branching Programs (1987) (26)
- Symmetry and complexity (1992) (26)
- Extremal subgraphs of random graphs (1990) (26)
- Dimension and automorphism groups of lattices (1981) (26)
- Locally testable cyclic codes (2005) (25)
- Set Systems with Restricted Intersections modulo Prime Powers (2001) (23)
- Infinite digraphs with given regular automorphism groups (1978) (23)
- On Set Intersections (1980) (21)
- Recognizing simplicity of black-box groups and the frequency of p-singular elements in affine groups (2008) (21)
- An anti-Ramsey theorem (1985) (20)
- On the automorphism groups of strongly regular graphs I (2014) (20)
- Theory of Computing (2015) (20)
- Quasipolynomial-time canonical form for steiner designs (2013) (20)
- Connectivity of infinite graphs having a transitive torsion group action (1980) (19)
- On the Diameter of Random Cayley Graphs of the Symmetric Group (1992) (19)
- Approximate representation theory of finite groups (1991) (18)
- A New Proof of Several Inequalities on Codes and Sets (1995) (18)
- Canonical form for graphs in quasipolynomial time: preliminary report (2019) (18)
- Symmetry groups of vertex-transitive polytopes (1977) (18)
- Transparent (Holographic) Proofs (1993) (18)
- On the Limits of Computations with the Floor Function (1988) (17)
- Endomorphism monoids and topological subgraphs of graphs (1980) (17)
- Permutation Groups without Exponentially Many Orbits on the Power Set (1991) (17)
- A Las Vegas - NC algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues (1986) (16)
- Groups of graphs on given surfaces (1973) (16)
- Arc transitive covering digraphs and their eigenvalues (1985) (16)
- Computational Complexity in Finite Groups (1991) (15)
- Vector representable matroids of given rank with given automorphism group (1978) (15)
- Isomorphism testing and symmetric of graphs (1980) (15)
- Weights of exact threshold functions (2010) (14)
- BPP and the polynomial time hierarchy in communication complexity (1986) (14)
- Sandpile transience on the grid is polynomially bounded (2007) (14)
- On a conjecture of M. E. Watkins on graphical regular representations of finite groups (1978) (14)
- The Graph Isomorphism Problem (Dagstuhl Seminar 15511) (2015) (14)
- Testing isomorphism of combinatorial and algebraic structures (2011) (14)
- On faithful permutation representations of small degree (1993) (13)
- On slightly superlinear transparent proofs (1993) (13)
- Evasiveness and the Distribution of Prime Numbers (2010) (13)
- On the automorphism groups of strongly regular graphs II (2015) (12)
- Deciding finiteness of matrix groups in Las Vegas polynomial time (1992) (12)
- Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) (1989) (12)
- A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality (1988) (12)
- A Structure Theory of the Sandpile Monoid for Directed Graphs (2010) (12)
- A characterization of Hash P by arithmetic straight line programs (1990) (12)
- Property Testing of Equivalence under a Permutation Group Action (2008) (11)
- Chromatic number and subgraphs of cayley graphs (1978) (11)
- On groups of polyhedral graphs (1973) (10)
- On the Nonuniform Fisher Inequality (1987) (10)
- A CONVERGENCE CRITERION FOR RECURRENT SEQUENCES WITH APPLICATION TO THE PARTITION LATTICE (1992) (10)
- Proportions of r‐regular elements in finite classical groups (2012) (10)
- Most primitive groups are full automorphism groups of edge-transitive hypergraphs (2014) (9)
- Decomposition of *-closed algebras in polynomial time (1993) (9)
- Tournaments with given (infinite) automorphism group (1979) (9)
- A Characterization of #P by Straight Line Programs of Polynomials, with Applications to Interactive Proofs and Toda''s Theorem (1990) (8)
- Subdirectly Reducible Groups and Edge‐Minimal Graphs with Given Automorphism Group (1993) (7)
- Finite groups of uniform logarithmic diameter (2005) (7)
- Asymptotic Delsarte cliques in distance-regular graphs (2015) (7)
- High Chromatic Rigid Graphs II (1982) (7)
- Automorphism group and category of cospectral graphs (1978) (7)
- Locally testable cyclic codes (2003) (7)
- Coset Intersection in Moderately Exponential Time (2013) (7)
- Stronger separations for random-self-reducibility, rounds, and advice (1999) (7)
- Proving Properties of Interactive Proofs by a Generalized Counting Technique (1989) (6)
- On Sharply Edge-Transitive Permutation Groups (1981) (6)
- Computing rank-convolutions with a mask (2009) (6)
- Sense preserving groups of polyhedral graphs (1975) (6)
- Algorithms for simple curves on surfaces, string graphs, and crossing numbers (2005) (6)
- The Complexity of Defining a Relation on a Finite Graph (1987) (5)
- Hamiltonian Cubic Graphs and Centralizers of Involutions (1979) (5)
- Computing Composition Series in Primitive Groups (1991) (4)
- Simultaneous diophantine approximation with excluded primes (2004) (4)
- Infinite quasigroups with given regular automorphism groups (1978) (3)
- Automorphism groups of finite distributive lattices with a given sublattice of fixed points (1980) (3)
- Entropy Versus Pairwise Independence (2013) (3)
- Graphs with Given Automorphism Group and Few Edge Orbits (1991) (3)
- Near-representations of finite groups (2003) (3)
- A remark on contraction of graphs with given group (1974) (3)
- Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed (2021) (3)
- Paul Erdös (1913-996): his influence on the theory of computing (1997) (3)
- List-decoding homomorphism codes with arbitrary codomains (2018) (2)
- Element order versus minimal degree in permutation groups: an old lemma with new applications (2014) (2)
- Fixing the UPCC case of Split-or-Johnson (2017) (2)
- Communication Complexity (1997) (2)
- Matrix rigidity depends on the target field (2021) (2)
- Eulerian Self-Dual Codes (1994) (2)
- On the degrees of non-split extensions by an alternating group (2017) (2)
- Adaptive inference for graphical models (2012) (1)
- J un 2 01 8 List-decoding homomorphism codes with arbitrary codomains (2018) (1)
- Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas (2011) (1)
- A Structure Theory of the Sandpile Monoid for Digraphs ( EXTENDED ABSTRACT ) (2005) (1)
- Faster Canonical Forms For Strongly Regular Graphs ( Extended Abstract ) (2013) (1)
- On the collineation groups of infinite projective and affine planes (1977) (1)
- Tibor Gallai, 1912–1992 (1992) (0)
- Weakly Growing Context-sensitive Grammars Chicago Journal of Theoretical Computer Science (1996) (0)
- Editors’ foreword (1987) (0)
- A Las-Vegas-NC algorithm for finding pointwise set-stabilizers in permutation groups with restricted composition factors (1985) (0)
- Invited Talks Symmetry , Hadwiger number , pointwise limit of graphs (2008) (0)
- Paley graphs and Paley tournaments (2021) (0)
- Computing the Composition Factors of Primitive Groups (1992) (0)
- A Characterization of \sharp P Arithmetic Straight Line Programs (1990) (0)
- Asymptotic Delsarte cliques in distance-regular graphs (2015) (0)
- Linear Algebraic Groups (2020) (0)
- Company REPRESENTATION OF GROUP ELEMENTS AS SHORT PRODUCTS (2004) (0)
- Multiplicative equations over commuting matrices (Extended Abstract) (1994) (0)
- Discrete Mathematics : The Abelian Sandpile Model (2010) (0)
- Publications in Communication Complexity Theory (2013) (0)
- Algebraic methods in computational complexity: arithmetic circuits, communication complexity, and interactive proof systems (1996) (0)
- There are no zero-hard problems in multiparty communication complexity (2013) (0)
- Primitive coherent configurations : On the order of uniprimitive permutation groups (2014) (0)
- Special Issue Dedicated To The Thirty-Sixth Annual ACM Symposium On Theory Of Computing (STOC 2004) (2006) (0)
- Finite Probability Spaces Lecture Notes (2002) (0)
- Tournaments with given regular groups (1978) (0)
- Discover Linear Algebra Incomplete Preliminary Draft Date : July 7 , 2016 (2016) (0)
- Editors’ foreword (1995) (0)
- Master ’ s Paper [ ROUGH DRAFT ] : 2 Dimensional Min-Filters with Polygons (2007) (0)
- On the Automorphism Groups of Strongly Regular Graphs ( Extended Abstract ) (2013) (0)
- Pspace-hard Functions Checkable Debate Systems and Approximation Algorithms for Pspace (2007) (0)
- THE MICROTOPONYMY OF THE WORLD OF SEVEN KINGDOMS IN THE NOVEL BY G.R.R. MARTIN “A GAME OF THE THRONES” (2020) (0)
- List of my favorite publications (2014) (0)
- Graph Theory : CMSC 27530 / 37530 Lecture 14 Lecture by (2019) (0)
This paper list is powered by the following services:
Other Resources About László Babai
What Schools Are Affiliated With László Babai?
László Babai is affiliated with the following schools:
