László Babai

ORCID

Publication Activity (10 Years)

Years Active: 1972-2021
Publications (10 Years): 8

Top Venues

Publications

László Babai, Bohdan Kivva
Matrix Rigidity Depends on the Target Field. Computational Complexity Conference (2021)
László Babai
Canonical form for graphs in quasipolynomial time: preliminary report. STOC (2019)
László Babai, Timothy J. F. Black, Angela Wuu
List-decoding homomorphism codes with arbitrary codomains. CoRR (2018)
László Babai, Timothy J. F. Black, Angela Wuu
List-Decoding Homomorphism Codes with Arbitrary Codomains. APPROX-RANDOM (2018)
László Babai
Graph isomorphism in quasipolynomial time [extended abstract]. STOC (2016)
László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán
The Graph Isomorphism Problem (Dagstuhl Seminar 15511). Dagstuhl Reports 5 (12) (2015)
László Babai, John Wilmes
Asymptotic Delsarte cliques in distance-regular graphs. CoRR (2015)
László Babai
Graph Isomorphism in Quasipolynomial Time. CoRR (2015)
László Babai
On the automorphism groups of strongly regular graphs I. ITCS (2014)
László Babai, Simon Guest, Cheryl E. Praeger, Robert A. Wilson
-regular elements in finite classical groups. J. Lond. Math. Soc. 88 (1) (2013)
László Babai, John Wilmes
Quasipolynomial-time canonical form for steiner designs. STOC (2013)
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes
Faster Canonical Forms for Strongly Regular Graphs. FOCS (2013)
László Babai, Paolo Codenotti, Youming Qiao
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract). ICALP (1) (2012)
László Babai, Youming Qiao
Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. STACS (2012)
László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao
Code Equivalence and Group Isomorphism. SODA (2011)
László Babai
Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas. CSR (2011)
László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik
Evasiveness and the Distribution of Prime Numbers CoRR (2010)
László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik
Evasiveness and the Distribution of Prime Numbers. STACS (2010)
László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun
Weights of Exact Threshold Functions. MFCS (2010)
László Babai, Barry Guiduli
Spectral Extrema for Graphs: The Zarankiewicz Problem. Electron. J. Comb. 16 (1) (2009)
László Babai, Robert Beals, Ákos Seress
Polynomial-time theory of matrix groups. STOC (2009)
László Babai, Pedro F. Felzenszwalb
Computing rank-convolutions with a mask. ACM Trans. Algorithms 6 (1) (2009)
László Babai, Paolo Codenotti
Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS (2008)
László Babai, Nikolay Nikolov, László Pyber
Product growth and mixing in finite groups. SODA (2008)
Sourav Chakraborty, László Babai
Property Testing of Equivalence under a Permutation Group Action. Electron. Colloquium Comput. Complex. 15 (040) (2008)
László Babai, Igor Gorodezky
Sandpile transience on the grid is polynomially bounded. SODA (2007)
László Babai
On the diameter of Eulerian orientations of graphs. SODA (2006)
László Babai
Automorphism groups of graphs and edge-contraction. Discret. Math. 306 (10-11) (2006)
László Babai
Special Issue Dedicated To The Thirty-Sixth Annual ACM Symposium On Theory Of Computing (STOC 2004). SIAM J. Comput. 35 (4) (2006)
László Babai, Amir Shpilka, Daniel Stefankovic
Locally testable cyclic codes. IEEE Trans. Inf. Theory 51 (8) (2005)
László Babai, Thomas P. Hayes
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. SODA (2005)
László Babai, Igor Pak
Strong bias of group generators: an obstacle to the "product replacement algorithm". J. Algorithms 50 (2) (2004)
László Babai, Daniel Stefankovic
Simultaneous diophantine approximation with excluded primes. SODA (2004)
László Babai, Robert Beals, Ákos Seress
On the diameter of the symmetric group: polynomial bounds. SODA (2004)
László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam
Communication Complexity of Simultaneous Messages. SIAM J. Comput. 33 (1) (2003)
László Babai, Amir Shpilka, Daniel Stefankovic
Locally Testable Cyclic Codes. FOCS (2003)
László Babai, Peter Frankl, Samuel Kutin, Daniel Stefankovic
Set Systems with Restricted Intersections modulo Prime Powers. J. Comb. Theory, Ser. A 95 (1) (2001)
László Babai, Thomas P. Hayes, Peter G. Kimmel
The Cost of the Missing Bit: Communication Complexity with Help. Comb. 21 (4) (2001)
László Babai, Peter J. Cameron
Automorphisms and Enumeration of Switching Classes of Tournaments. Electron. J. Comb. 7 (2000)
László Babai, Igor Pak
Strong bias of group generators: an obstacle to the "product replacement algorithm". SODA (2000)
László Babai, Sophie Laplante
Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. Computational Complexity Conference (1999)
László Babai, Anna Gál, Avi Wigderson
Superpolynomial Lower Bounds for Monotone Span Programs. Comb. 19 (3) (1999)
László Babai, Thomas P. Hayes, Peter G. Kimmel
The Cost of the Missing Bit: Communication Complexity with Help. STOC (1998)
László Babai, Peter G. Kimmel
Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. Computational Complexity Conference (1997)
László Babai, Eugene M. Luks, Ákos Seress
Fast Management of Permutation Groups I. SIAM J. Comput. 26 (5) (1997)
László Babai
Communication Complexity. MFCS (1997)
László Babai
The Growth Rate of Vertex-Transitive Planar Graphs. SODA (1997)
László Babai
Paul Erdös (1913-1996): His Influence on the Theory of Computing. STOC (1997)
Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. J. Comput. Syst. Sci. 54 (2) (1997)
László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks
Multiplicative Equations over Commuting Matrices. SODA (1996)
László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. STOC (1996)
László Babai, Peter G. Kimmel, Satyanarayana V. Lokam
Simultaneous Messages vs. Communication. STACS (1995)
László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress
Fast Monte Carlo Algorithms for Permutation Groups. J. Comput. Syst. Sci. 50 (2) (1995)
László Babai
Randomization in group algorithms: Conceptual questions. Groups and Computation (1995)
László Babai
A New Proof of Several Inequalities on Codes and Sets. J. Comb. Theory, Ser. A 71 (1) (1995)
László Babai, Haluk Oral, Kevin T. Phelps
Eulerian Self-Dual Codes. SIAM J. Discret. Math. 7 (2) (1994)
László Babai, László Pyber
Permutation Groups without Exponentially Many Orbits on the Power Set. J. Comb. Theory, Ser. A 66 (1) (1994)
László Babai
Transparent (Holographic) Proofs. STACS (1993)
László Babai, Katalin Friedl, Markus Stricker
Decomposition of *-closed Algebras in Polynomial Time. ISSAC (1993)
Robert Beals, László Babai
Las Vegas algorithms for matrix groups FOCS (1993)
Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk
The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations FOCS (1993)
László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Comput. Complex. 3 (1993)
László Babai, Robert Beals, Daniel N. Rockmore
Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time. ISSAC (1993)
László Babai, Robert Beals, Pál Takácsi-Nagy
Symmetry and Complexity STOC (1992)
László Babai, Mario Szegedy
Local Expansion of Ssymmetrical Graphs. Comb. Probab. Comput. 1 (1992)
László Babai, Gábor Hetyei
On the Diameter of Random Cayley Graphs of the Symmetric Group. Comb. Probab. Comput. 1 (1992)
László Babai
Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time. SODA (1992)
László Babai
Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discret. Math. 5 (1) (1992)
László Babai, Lance Fortnow, Carsten Lund
Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. 2 (1992)
László Babai, Noam Nisan, Mario Szegedy
Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. J. Comput. Syst. Sci. 45 (2) (1992)
László Babai, Ákos Seress
On the diameter of permutation groups. Eur. J. Comb. 13 (4) (1992)
László Babai, Eugene M. Luks, Ákos Seress
Computing Composition Series in Primitive Groups. Groups And Computation (1991)
László Babai, Lance Fortnow, Carsten Lund
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. 1 (1991)
Noga Alon, László Babai, Hiroshi Suzuki
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. J. Comb. Theory, Ser. A 58 (2) (1991)
László Babai
Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups STOC (1991)
László Babai, Albert J. Goodman, László Lovász
Graphs with Given Automorphism Group and Few Edge Orbits. Eur. J. Comb. 12 (3) (1991)
László Babai, Lance Fortnow
Arithmetization: A New Method in Structural Complexity Theory. Comput. Complex. 1 (1991)
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
Checking Computations in Polylogarithmic Time STOC (1991)
László Babai, Katalin Friedl
Approximate Representation Theory of Finite Groups FOCS (1991)
László Babai, Noam Nisan
BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. Computational Complexity Conference (1991)
László Babai
Vertex-transitive graphs and vertex-transitive maps. J. Graph Theory 15 (6) (1991)
László Babai, Gene Cooperman, Larry Finkelstein, Ákos Seress
Nearly Linear Time Algorithms for Permutation Groups with a Small Base. ISSAC (1991)
László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress
Fast Monte Carlo Algorithms for Permutation Groups STOC (1991)
László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress
On the Diameter of Finite Groups FOCS (1990)
László Babai, Lance Fortnow, Carsten Lund
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols FOCS (1990)
László Babai, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi
Lower Bounds to the Complexity of Symmetric Boolean Functions. Theor. Comput. Sci. 74 (3) (1990)
László Babai, Lance Fortnow
A Characterization of \sharp P Arithmetic Straight Line Programs FOCS (1990)
László Babai
E-mail and the Unexpected Power of Interaction. Computational Complexity Conference (1990)
László Babai, Miklós Simonovits, Joel Spencer
Extremal subgraphs of random graphs. J. Graph Theory 14 (5) (1990)
László Babai, Noam Nisan, Mario Szegedy
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) STOC (1989)
László Babai, William M. Kantor, A. Lubotsky
Small-diameter Cayley Graphs for Finite Simple Groups. Eur. J. Comb. 10 (6) (1989)
László Babai, Lajos Rónyai
Computing Irreducible Representations of Finite Groups FOCS (1989)
László Babai, Shlomo Moran
Proving Properties of Interactive Proofs by a Generalized Counting Technique Inf. Comput. 82 (2) (1989)
László Babai
The probability of generating the symmetric group. J. Comb. Theory, Ser. A 52 (1) (1989)
László Babai, Shlomo Moran
Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes. J. Comput. Syst. Sci. 36 (2) (1988)
László Babai
A short proof of the non-uniform Ray Chauhuri - Wilson inequality. Comb. 8 (1) (1988)
László Babai, Bettina Just, Friedhelm Meyer auf der Heide
On the Limits of Computations with the Floor Function Inf. Comput. 78 (2) (1988)
László Babai, Ákos Seress
On the diameter of cayley graphs of the symmetric group. J. Comb. Theory, Ser. A 49 (1) (1988)
László Babai, Eugene M. Luks, Ákos Seress
Fast Management of Permutation Groups FOCS (1988)
László Babai, Péter Hajnal, Endre Szemerédi, György Turán
A Lower Bound for Read-Once-Only Branching Programs. J. Comput. Syst. Sci. 35 (2) (1987)

László Babai.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

László Babai