László Babai

According to our database1, László Babai authored at least 126 papers between 1972 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Canonical form for graphs in quasipolynomial time: preliminary report.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018
List-Decoding Homomorphism Codes with Arbitrary Codomains.
Proceedings of the Approximation, 2018

2016
Graph isomorphism in quasipolynomial time [extended abstract].
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015
The Graph Isomorphism Problem (Dagstuhl Seminar 15511).
Dagstuhl Reports, 2015

2014
On the automorphism groups of strongly regular graphs I.
Proceedings of the Innovations in Theoretical Computer Science, 2014

2013
Proportions of r-regular elements in finite classical groups.
J. London Math. Society, 2013

Quasipolynomial-time canonical form for steiner designs.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Faster Canonical Forms for Strongly Regular Graphs.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers.
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).
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Code Equivalence and Group Isomorphism.
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.
Proceedings of the Computer Science - Theory and Applications, 2011

2010
Evasiveness and the Distribution of Prime Numbers.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Weights of Exact Threshold Functions.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009
Computing rank-convolutions with a mask.
ACM Trans. Algorithms, 2009

Spectral Extrema for Graphs: The Zarankiewicz Problem.
Electr. J. Comb., 2009

Polynomial-time theory of matrix groups.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008
Property Testing of Equivalence under a Permutation Group Action.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Product growth and mixing in finite groups.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Sandpile transience on the grid is polynomially bounded.
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).
SIAM J. Comput., 2006

Automorphism groups of graphs and edge-contraction.
Discrete Mathematics, 2006

On the diameter of Eulerian orientations of graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Simultaneous diophantine approximation with excluded primes.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On the diameter of the symmetric group: polynomial bounds.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003
Communication Complexity of Simultaneous Messages.
SIAM J. Comput., 2003

Locally Testable Cyclic Codes.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001
Set Systems with Restricted Intersections modulo Prime Powers.
J. Comb. Theory, Ser. A, 2001

2000
Automorphisms and Enumeration of Switching Classes of Tournaments.
Electr. J. Comb., 2000

Strong bias of group generators: an obstacle to the "product replacement algorithm".
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Superpolynomial Lower Bounds for Monotone Span Programs.
Combinatorica, 1999

Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
The Cost of the Missing Bit: Communication Complexity with Help.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997
Fast Management of Permutation Groups I.
SIAM J. Comput., 1997

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations.
J. Comput. Syst. Sci., 1997

Paul Erdös (1913-1996): His Influence on the Theory of Computing.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Growth Rate of Vertex-Transitive Planar Graphs.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Communication Complexity.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Multiplicative Equations over Commuting Matrices.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995
A New Proof of Several Inequalities on Codes and Sets.
J. Comb. Theory, Ser. A, 1995

Fast Monte Carlo Algorithms for Permutation Groups.
J. Comput. Syst. Sci., 1995

Simultaneous Messages vs. Communication.
STACS, 1995

Randomization in group algorithms: Conceptual questions.
Proceedings of the Groups and Computation, 1995

1994
Eulerian Self-Dual Codes.
SIAM J. Discrete Math., 1994

Permutation Groups without Exponentially Many Orbits on the Power Set.
J. Comb. Theory, Ser. A, 1994

1993
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
Computational Complexity, 1993

Transparent (Holographic) Proofs.
Proceedings of the STACS 93, 1993

Decomposition of *-closed Algebras in Polynomial Time.
Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, 1993

Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time.
Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, 1993

Las Vegas algorithms for matrix groups
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
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Bounded Round Interactive Proofs in Finite Groups.
SIAM J. Discrete Math., 1992

Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs.
J. Comput. Syst. Sci., 1992

On the diameter of permutation groups.
Eur. J. Comb., 1992

Local Expansion of Ssymmetrical Graphs.
Combinatorics, Probability & Computing, 1992

On the Diameter of Random Cayley Graphs of the Symmetric Group.
Combinatorics, Probability & Computing, 1992

Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity, 1992

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

Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991
Vertex-transitive graphs and vertex-transitive maps.
Journal of Graph Theory, 1991

Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.
J. Comb. Theory, Ser. A, 1991

Graphs with Given Automorphism Group and Few Edge Orbits.
Eur. J. Comb., 1991

Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity, 1991

Arithmetization: A New Method in Structural Complexity Theory.
Computational Complexity, 1991

Checking Computations in Polylogarithmic Time
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Fast Monte Carlo Algorithms for Permutation Groups
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Nearly Linear Time Algorithms for Permutation Groups with a Small Base.
Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, 1991

Approximate Representation Theory of Finite Groups
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Computing Composition Series in Primitive Groups.
Proceedings of the Groups And Computation, 1991

BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs.
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.
Theor. Comput. Sci., 1990

Extremal subgraphs of random graphs.
Journal of Graph Theory, 1990

On the Diameter of Finite Groups
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Characterization of \sharp P Arithmetic Straight Line Programs
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

E-mail and the Unexpected Power of Interaction.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Proving Properties of Interactive Proofs by a Generalized Counting Technique
Inf. Comput., August, 1989

The probability of generating the symmetric group.
J. Comb. Theory, Ser. A, 1989

Small-diameter Cayley Graphs for Finite Simple Groups.
Eur. J. Comb., 1989

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Computing Irreducible Representations of Finite Groups
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
Inf. Comput., August, 1988

On the diameter of cayley graphs of the symmetric group.
J. Comb. Theory, Ser. A, 1988

Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.
J. Comput. Syst. Sci., 1988

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

Fast Management of Permutation Groups
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
The Complexity of Defining a Relation on a Finite Graph.
Math. Log. Q., 1987

On the degree of transitivity of permutation groups: A short proof.
J. Comb. Theory, Ser. A, 1987

A Lower Bound for Read-Once-Only Branching Programs.
J. Comput. Syst. Sci., 1987

Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy.
Inf. Process. Lett., 1987

On the Nonuniform Fisher Inequality.
Discrete Mathematics, 1987

Permutation Groups in NC
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.
J. Algorithms, 1986

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

Two lower bounds for branching programs
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Complexity classes in communication complexity theory (preliminary version)
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
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Arc transitive covering digraphs and their eigenvalues.
Journal of Graph Theory, 1985

An anti-Ramsey theorem.
Graphs and Combinatorics, 1985

Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs.
Eur. J. Comb., 1985

Trading Group Theory for Randomness
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).
Proceedings of the STACS 85, 1985

1984
On the Complexity of Matrix Group Problems I
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

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

Computational Complexity and the Classification of Finite Simple Groups
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
On the Automorphism Groups of almost all Cayley Graphs.
Eur. J. Comb., 1982

Isomorphism of Graphs with Bounded Eigenvalue Multiplicity
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981
Moderately Exponential Bound for Graph Isomorphism.
Proceedings of the Fundamentals of Computation Theory, 1981

1980
Random Graph Isomorphism.
SIAM J. Comput., 1980

On the Complexity of Canonical Labeling of Strongly Regular Graphs.
SIAM J. Comput., 1980

Endomorphism monoids and topological subgraphs of graphs.
J. Comb. Theory, Ser. B, 1980

On Set Intersections.
J. Comb. Theory, Ser. A, 1980

1979
Long cycles in vertex-transitive graphs.
Journal of Graph Theory, 1979

Spectra of Cayley graphs.
J. Comb. Theory, Ser. B, 1979

Canonical Labelling of Graphs in Linear Average Time
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Infinite digraphs with given regular automorphism groups.
J. Comb. Theory, Ser. B, 1978

Vector representable matroids of given rank with given automorphism group.
Discrete Mathematics, 1978

1977
Some applications of graph contractions.
Journal of Graph Theory, 1977

1974
Automorphism groups of graphs and edge-contraction.
Discrete Mathematics, 1974

1973
On groups of polyhedral graphs.
Discrete Mathematics, 1973

1972
Automorphism groups of planar graphs I.
Discrete Mathematics, 1972


  Loading...