László Babai

According to our database, László Babai authored at least 127 papers between 1972 and 2021.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of one.

2021

Matrix Rigidity Depends on the Target Field.

László Babai, Bohdan Kivva

Proceedings of the 36th Computational Complexity Conference, 2021

2019

Canonical form for graphs in quasipolynomial time: preliminary report.

László Babai

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

List-Decoding Homomorphism Codes with Arbitrary Codomains.

László Babai, Timothy J. F. Black, Angela Wuu

Proceedings of the Approximation, 2018

2016

Graph isomorphism in quasipolynomial time [extended abstract].

László Babai

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

The Graph Isomorphism Problem (Dagstuhl Seminar 15511).

László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán

Dagstuhl Reports, 2015

Asymptotic Delsarte cliques in distance-regular graphs.

László Babai, John Wilmes

CoRR, 2015

Graph Isomorphism in Quasipolynomial Time.

László Babai

CoRR, 2015

2014

On the automorphism groups of strongly regular graphs I.

László Babai

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Proportions of <i>r</i>-regular elements in finite classical groups.

László Babai, Simon Guest, Cheryl E. Praeger, Robert A. Wilson

J. Lond. Math. Soc., 2013

Quasipolynomial-time canonical form for steiner designs.

László Babai, John Wilmes

Proceedings of the Symposium on Theory of Computing Conference, 2013

Faster Canonical Forms for Strongly Regular Graphs.

László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers.

László Babai, Youming Qiao

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract).

László Babai, Paolo Codenotti, Youming Qiao

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Code Equivalence and Group Isomorphism.

László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas.

László Babai

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Evasiveness and the Distribution of Prime Numbers.

László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Weights of Exact Threshold Functions.

László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

Computing rank-convolutions with a mask.

László Babai, Pedro F. Felzenszwalb

ACM Trans. Algorithms, 2009

On the Number of<i>p</i>-Regular Elements in Finite Simple Groups.

László Babai, Péter P. Pálfy, Jan Saxl

LMS J. Comput. Math., 2009

Spectral Extrema for Graphs: The Zarankiewicz Problem.

László Babai, Barry Guiduli

Electron. J. Comb., 2009

Polynomial-time theory of matrix groups.

László Babai, Robert Beals, Ákos Seress

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Property Testing of Equivalence under a Permutation Group Action.

Sourav Chakraborty, László Babai

Electron. Colloquium Comput. Complex., 2008

Product growth and mixing in finite groups.

László Babai, Nikolay Nikolov, László Pyber

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time.

László Babai, Paolo Codenotti

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Sandpile transience on the grid is polynomially bounded.

László Babai, Igor Gorodezky

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Special Issue Dedicated To The Thirty-Sixth Annual ACM Symposium On Theory Of Computing (STOC 2004).

László Babai

SIAM J. Comput., 2006

Automorphism groups of graphs and edge-contraction.

László Babai

Discret. Math., 2006

On the diameter of Eulerian orientations of graphs.

László Babai

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Locally testable cyclic codes.

László Babai, Amir Shpilka, Daniel Stefankovic

IEEE Trans. Inf. Theory, 2005

Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group.

László Babai, Thomas P. Hayes

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Strong bias of group generators: an obstacle to the "product replacement algorithm".

László Babai, Igor Pak

J. Algorithms, 2004

Simultaneous diophantine approximation with excluded primes.

László Babai, Daniel Stefankovic

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On the diameter of the symmetric group: polynomial bounds.

László Babai, Robert Beals, Ákos Seress

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

Communication Complexity of Simultaneous Messages.

László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam

SIAM J. Comput., 2003

2001

Set Systems with Restricted Intersections modulo Prime Powers.

László Babai, Peter Frankl, Samuel Kutin, Daniel Stefankovic

J. Comb. Theory, Ser. A, 2001

The Cost of the Missing Bit: Communication Complexity with Help.

László Babai, Thomas P. Hayes, Peter G. Kimmel

Comb., 2001

2000

Automorphisms and Enumeration of Switching Classes of Tournaments.

László Babai, Peter J. Cameron

Electron. J. Comb., 2000

1999

Superpolynomial Lower Bounds for Monotone Span Programs.

László Babai, Anna Gál, Avi Wigderson

Comb., 1999

Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.

László Babai, Sophie Laplante

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1997

Fast Management of Permutation Groups I.

László Babai, Eugene M. Luks, Ákos Seress

SIAM J. Comput., 1997

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations.

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk

J. Comput. Syst. Sci., 1997

Paul Erdös (1913-1996): His Influence on the Theory of Computing.

László Babai

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Growth Rate of Vertex-Transitive Planar Graphs.

László Babai

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Communication Complexity.

László Babai

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity.

László Babai, Peter G. Kimmel

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.

László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Multiplicative Equations over Commuting Matrices.

László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995

A New Proof of Several Inequalities on Codes and Sets.

László Babai

J. Comb. Theory, Ser. A, 1995

Fast Monte Carlo Algorithms for Permutation Groups.

László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress

J. Comput. Syst. Sci., 1995

Simultaneous Messages vs. Communication.

László Babai, Peter G. Kimmel, Satyanarayana V. Lokam

Proceedings of the STACS 95, 1995

Randomization in group algorithms: Conceptual questions.

László Babai

Proceedings of the Groups and Computation, 1995

1994

Eulerian Self-Dual Codes.

László Babai, Haluk Oral, Kevin T. Phelps

SIAM J. Discret. Math., 1994

Permutation Groups without Exponentially Many Orbits on the Power Set.

László Babai, László Pyber

J. Comb. Theory, Ser. A, 1994

1993

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.

László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson

Comput. Complex., 1993

Transparent (Holographic) Proofs.

László Babai

Proceedings of the STACS 93, 1993

Decomposition of *-closed Algebras in Polynomial Time.

László Babai, Katalin Friedl, Markus Stricker

Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, 1993

Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time.

László Babai, Robert Beals, Daniel N. Rockmore

Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, 1993

Las Vegas algorithms for matrix groups

Robert Beals, László Babai

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Bounded Round Interactive Proofs in Finite Groups.

László Babai

SIAM J. Discret. Math., 1992

Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs.

László Babai, Noam Nisan, Mario Szegedy

J. Comput. Syst. Sci., 1992

On the diameter of permutation groups.

László Babai, Ákos Seress

Eur. J. Comb., 1992

Local Expansion of Ssymmetrical Graphs.

László Babai, Mario Szegedy

Comb. Probab. Comput., 1992

On the Diameter of Random Cayley Graphs of the Symmetric Group.

László Babai, Gábor Hetyei

Comb. Probab. Comput., 1992

Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.

László Babai, Lance Fortnow, Carsten Lund

Comput. Complex., 1992

Symmetry and Complexity

László Babai, Robert Beals, Pál Takácsi-Nagy

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time.

László Babai

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

Vertex-transitive graphs and vertex-transitive maps.

László Babai

J. Graph Theory, 1991

Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.

Noga Alon, László Babai, Hiroshi Suzuki

J. Comb. Theory, Ser. A, 1991

Graphs with Given Automorphism Group and Few Edge Orbits.

László Babai, Albert J. Goodman, László Lovász

Eur. J. Comb., 1991

Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.

László Babai, Lance Fortnow, Carsten Lund

Comput. Complex., 1991

Arithmetization: A New Method in Structural Complexity Theory.

László Babai, Lance Fortnow

Comput. Complex., 1991

Checking Computations in Polylogarithmic Time

László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups

László Babai

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Nearly Linear Time Algorithms for Permutation Groups with a Small Base.

László Babai, Gene Cooperman, Larry Finkelstein, Ákos Seress

Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, 1991

Approximate Representation Theory of Finite Groups

László Babai, Katalin Friedl

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Computing Composition Series in Primitive Groups.

László Babai, Eugene M. Luks, Ákos Seress

Proceedings of the Groups And Computation, 1991

BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs.

László Babai, Noam Nisan

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Lower Bounds to the Complexity of Symmetric Boolean Functions.

László Babai, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi

Theor. Comput. Sci., 1990

Extremal subgraphs of random graphs.

László Babai, Miklós Simonovits, Joel Spencer

J. Graph Theory, 1990

On the Diameter of Finite Groups

László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Characterization of \sharp P Arithmetic Straight Line Programs

László Babai, Lance Fortnow

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

E-mail and the Unexpected Power of Interaction.

László Babai

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Proving Properties of Interactive Proofs by a Generalized Counting Technique

László Babai, Shlomo Moran

Inf. Comput., August, 1989

The probability of generating the symmetric group.

László Babai

J. Comb. Theory, Ser. A, 1989

Small-diameter Cayley Graphs for Finite Simple Groups.

László Babai, William M. Kantor, A. Lubotsky

Eur. J. Comb., 1989

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)

László Babai, Noam Nisan, Mario Szegedy

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Computing Irreducible Representations of Finite Groups

László Babai, Lajos Rónyai

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

On the Limits of Computations with the Floor Function

László Babai, Bettina Just, Friedhelm Meyer auf der Heide

Inf. Comput., August, 1988

On the diameter of cayley graphs of the symmetric group.

László Babai, Ákos Seress

J. Comb. Theory, Ser. A, 1988

Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.

László Babai, Shlomo Moran

J. Comput. Syst. Sci., 1988

A short proof of the non-uniform Ray Chauhuri - Wilson inequality.

László Babai

Comb., 1988

Fast Management of Permutation Groups

László Babai, Eugene M. Luks, Ákos Seress

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

The Complexity of Defining a Relation on a Finite Graph.

László Babai, György Turán

Math. Log. Q., 1987

On the degree of transitivity of permutation groups: A short proof.

László Babai, Ákos Seress

J. Comb. Theory, Ser. A, 1987

A Lower Bound for Read-Once-Only Branching Programs.

László Babai, Péter Hajnal, Endre Szemerédi, György Turán

J. Comput. Syst. Sci., 1987

Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy.

László Babai

Inf. Process. Lett., 1987

On the Nonuniform Fisher Inequality.

László Babai

Discret. Math., 1987

Permutation Groups in NC

László Babai, Eugene M. Luks, Ákos Seress

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.

Noga Alon, László Babai, Alon Itai

J. Algorithms, 1986

On Lovász' lattice reduction and the nearest lattice point problem.

László Babai

Comb., 1986

Two lower bounds for branching programs

Miklós Ajtai, László Babai, Péter Hajnal, János Komlós, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi, György Turán

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Complexity classes in communication complexity theory (preliminary version)

László Babai, Peter Frankl, Janos Simon

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues

László Babai

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Arc transitive covering digraphs and their eigenvalues.

László Babai

J. Graph Theory, 1985

An anti-Ramsey theorem.

László Babai

Graphs Comb., 1985

Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs.

László Babai, Vera T. Sós

Eur. J. Comb., 1985

Trading Group Theory for Randomness

László Babai

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version).

László Babai

Proceedings of the STACS 85, 1985

1984

On the Complexity of Matrix Group Problems I

László Babai, Endre Szemerédi

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Canonical Labeling of Graphs

László Babai, Eugene M. Luks

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Computational Complexity and the Classification of Finite Simple Groups

László Babai, William M. Kantor, Eugene M. Luks

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

On the Automorphism Groups of almost all Cayley Graphs.

László Babai, Chris D. Godsil

Eur. J. Comb., 1982

Isomorphism of Graphs with Bounded Eigenvalue Multiplicity

László Babai, D. Yu. Grigoryev, David M. Mount

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981

Moderately Exponential Bound for Graph Isomorphism.

László Babai

Proceedings of the Fundamentals of Computation Theory, 1981

1980

Random Graph Isomorphism.

László Babai, Paul Erdös, Stanley M. Selkow

SIAM J. Comput., 1980

On the Complexity of Canonical Labeling of Strongly Regular Graphs.

László Babai

SIAM J. Comput., 1980

Endomorphism monoids and topological subgraphs of graphs.

László Babai, Ales Pultr

J. Comb. Theory, Ser. B, 1980

On Set Intersections.

László Babai, Peter Frankl

J. Comb. Theory, Ser. A, 1980

1979

Long cycles in vertex-transitive graphs.

László Babai

J. Graph Theory, 1979

Spectra of Cayley graphs.

László Babai

J. Comb. Theory, Ser. B, 1979

Canonical Labelling of Graphs in Linear Average Time

László Babai, Ludek Kucera

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

Infinite digraphs with given regular automorphism groups.

László Babai

J. Comb. Theory, Ser. B, 1978

Vector representable matroids of given rank with given automorphism group.

László Babai

Discret. Math., 1978

1977

Some applications of graph contractions.

László Babai

J. Graph Theory, 1977

1973

On groups of polyhedral graphs.

László Babai, Wilfried Imrich

Discret. Math., 1973

1972

Automorphism groups of planar graphs I.

László Babai

Discret. Math., 1972