László Babai

136 papers A* 45A 9B 6Misc 1Journal 69Unranked 6

Year	Rank	Type	Title / Venue / Authors
2021	A	`conf`	Matrix Rigidity Depends on the Target Field. CCC László Babai, Bohdan Kivva
2019	A*	`conf`	Canonical form for graphs in quasipolynomial time: preliminary report. STOC László Babai
2018	—	`conf`	List-Decoding Homomorphism Codes with Arbitrary Codomains. APPROX-RANDOM László Babai, Timothy J. F. Black, Angela Wuu
2018	J	`jnl`	List-decoding homomorphism codes with arbitrary codomains. CoRR László Babai, Timothy J. F. Black, Angela Wuu
2016	A*	`conf`	Graph isomorphism in quasipolynomial time [extended abstract]. STOC László Babai
2015	J	`jnl`	Asymptotic Delsarte cliques in distance-regular graphs. CoRR László Babai, John Wilmes
2015	J	`jnl`	Graph Isomorphism in Quasipolynomial Time. CoRR László Babai
2015	J	`jnl`	The Graph Isomorphism Problem (Dagstuhl Seminar 15511). Dagstuhl Reports László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán
2014	A	`conf`	On the automorphism groups of strongly regular graphs I. ITCS László Babai
2013	A*	`conf`	Faster Canonical Forms for Strongly Regular Graphs. FOCS László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes
2013	J	`jnl`	Proportions of J. Lond. Math. Soc. László Babai, Simon Guest, Cheryl E. Praeger, Robert A. Wilson
2013	A*	`conf`	Quasipolynomial-time canonical form for steiner designs. STOC László Babai, John Wilmes
2012	—	`conf`	Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract). ICALP (1) László Babai, Paolo Codenotti, Youming Qiao
2012	A	`conf`	Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. STACS László Babai, Youming Qiao
2011	A*	`conf`	Code Equivalence and Group Isomorphism. SODA László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao
2011	Misc	`conf`	Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas. CSR László Babai
2010	J	`jnl`	Evasiveness and the Distribution of Prime Numbers CoRR László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik
2010	A	`conf`	Evasiveness and the Distribution of Prime Numbers. STACS László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik
2010	B	`conf`	Weights of Exact Threshold Functions. MFCS László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun
2009	J	`jnl`	Computing rank-convolutions with a mask. ACM Trans. Algorithms László Babai, Pedro F. Felzenszwalb
2009	J	`jnl`	On the Number of LMS J. Comput. Math. László Babai, Péter P. Pálfy, Jan Saxl
2009	A*	`conf`	Polynomial-time theory of matrix groups. STOC László Babai, Robert Beals, Ákos Seress
2009	J	`jnl`	Spectral Extrema for Graphs: The Zarankiewicz Problem. Electron. J. Comb. László Babai, Barry Guiduli
2008	A*	`conf`	Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS László Babai, Paolo Codenotti
2008	A*	`conf`	Product growth and mixing in finite groups. SODA László Babai, Nikolay Nikolov, László Pyber
2008	J	`jnl`	Property Testing of Equivalence under a Permutation Group Action. Electron. Colloquium Comput. Complex. Sourav Chakraborty, László Babai
2007	A*	`conf`	Sandpile transience on the grid is polynomially bounded. SODA László Babai, Igor Gorodezky
2006	J	`jnl`	Automorphism groups of graphs and edge-contraction. Discret. Math. László Babai
2006	A*	`conf`	On the diameter of Eulerian orientations of graphs. SODA László Babai
2006	J	`jnl`	Special Issue Dedicated To The Thirty-Sixth Annual ACM Symposium On Theory Of Computing (STOC 2004). SIAM J. Comput. László Babai
2005	J	`jnl`	Locally testable cyclic codes. IEEE Trans. Inf. Theory László Babai, Amir Shpilka, Daniel Stefankovic
2005	A*	`conf`	Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. SODA László Babai, Thomas P. Hayes
2004	A*	`conf`	On the diameter of the symmetric group: polynomial bounds. SODA László Babai, Robert Beals, Ákos Seress
2004	A*	`ed.`	Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004 STOC László Babai
2004	A*	`conf`	Simultaneous diophantine approximation with excluded primes. SODA László Babai, Daniel Stefankovic
2004	J	`jnl`	Strong bias of group generators: an obstacle to the "product replacement algorithm". J. Algorithms László Babai, Igor Pak
2003	J	`jnl`	Communication Complexity of Simultaneous Messages. SIAM J. Comput. László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam
2003	A*	`conf`	Locally Testable Cyclic Codes. FOCS László Babai, Amir Shpilka, Daniel Stefankovic
2001	J	`jnl`	Set Systems with Restricted Intersections modulo Prime Powers. J. Comb. Theory A László Babai, Peter Frankl, Samuel Kutin, Daniel Stefankovic
2001	J	`jnl`	The Cost of the Missing Bit: Communication Complexity with Help. Comb. László Babai, Thomas P. Hayes, Peter G. Kimmel
2000	J	`jnl`	Automorphisms and Enumeration of Switching Classes of Tournaments. Electron. J. Comb. László Babai, Peter J. Cameron
2000	A*	`conf`	Strong bias of group generators: an obstacle to the "product replacement algorithm". SODA László Babai, Igor Pak
1999	A	`conf`	Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. CCC László Babai, Sophie Laplante
1999	J	`jnl`	Superpolynomial Lower Bounds for Monotone Span Programs. Comb. László Babai, Anna Gál, Avi Wigderson
1998	A*	`conf`	The Cost of the Missing Bit: Communication Complexity with Help. STOC László Babai, Thomas P. Hayes, Peter G. Kimmel
1997	B	`conf`	Communication Complexity. MFCS László Babai
1997	J	`jnl`	Fast Management of Permutation Groups I. SIAM J. Comput. László Babai, Eugene M. Luks, Ákos Seress
1997	A*	`conf`	Paul Erdös (1913-1996): His Influence on the Theory of Computing. STOC László Babai
1997	A	`conf`	Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. CCC László Babai, Peter G. Kimmel
1997	A*	`conf`	The Growth Rate of Vertex-Transitive Planar Graphs. SODA László Babai
1997	J	`jnl`	The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. J. Comput. Syst. Sci. Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk
1996	A*	`conf`	Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. STOC László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson
1996	A*	`conf`	Multiplicative Equations over Commuting Matrices. SODA László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, Eugene M. Luks
1995	J	`jnl`	A New Proof of Several Inequalities on Codes and Sets. J. Comb. Theory A László Babai
1995	J	`jnl`	Fast Monte Carlo Algorithms for Permutation Groups. J. Comput. Syst. Sci. László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress
1995	—	`conf`	Randomization in group algorithms: Conceptual questions. Groups and Computation László Babai
1995	A	`conf`	Simultaneous Messages vs. Communication. STACS László Babai, Peter G. Kimmel, Satyanarayana V. Lokam
1994	J	`jnl`	Eulerian Self-Dual Codes. SIAM J. Discret. Math. László Babai, Haluk Oral, Kevin T. Phelps
1994	J	`jnl`	Permutation Groups without Exponentially Many Orbits on the Power Set. J. Comb. Theory A László Babai, László Pyber
1993	J	`jnl`	BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Comput. Complex. László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson
1993	B	`conf`	Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time. ISSAC László Babai, Robert Beals, Daniel N. Rockmore
1993	B	`conf`	Decomposition of *-closed Algebras in Polynomial Time. ISSAC László Babai, Katalin Friedl, Markus Stricker
1993	A*	`conf`	Las Vegas algorithms for matrix groups FOCS Robert Beals, László Babai
1993	A*	`conf`	The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations FOCS Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk
1993	A	`conf`	Transparent (Holographic) Proofs. STACS László Babai
1992	J	`jnl`	Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. László Babai, Lance Fortnow, Carsten Lund
1992	J	`jnl`	Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discret. Math. László Babai
1992	A*	`conf`	Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time. SODA László Babai
1992	J	`jnl`	Local Expansion of Ssymmetrical Graphs. Comb. Probab. Comput. László Babai, Mario Szegedy
1992	J	`jnl`	Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. J. Comput. Syst. Sci. László Babai, Noam Nisan, Mario Szegedy
1992	J	`jnl`	On the Diameter of Random Cayley Graphs of the Symmetric Group. Comb. Probab. Comput. László Babai, Gábor Hetyei
1992	J	`jnl`	On the diameter of permutation groups. Eur. J. Comb. László Babai, Ákos Seress
1992	A*	`conf`	Symmetry and Complexity STOC László Babai, Robert Beals, Pál Takácsi-Nagy
1991	A*	`conf`	Approximate Representation Theory of Finite Groups FOCS László Babai, Katalin Friedl
1991	J	`jnl`	Arithmetization: A New Method in Structural Complexity Theory. Comput. Complex. László Babai, Lance Fortnow
1991	—	`conf`	BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. SCT László Babai, Noam Nisan
1991	A*	`conf`	Checking Computations in Polylogarithmic Time STOC László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
1991	—	`conf`	Computing Composition Series in Primitive Groups. Groups And Computation László Babai, Eugene M. Luks, Ákos Seress
1991	A*	`conf`	Fast Monte Carlo Algorithms for Permutation Groups STOC László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress
1991	J	`jnl`	Graphs with Given Automorphism Group and Few Edge Orbits. Eur. J. Comb. László Babai, Albert J. Goodman, László Lovász
1991	A*	`conf`	Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups STOC László Babai
1991	J	`jnl`	Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. J. Comb. Theory A Noga Alon, László Babai, Hiroshi Suzuki
1991	B	`conf`	Nearly Linear Time Algorithms for Permutation Groups with a Small Base. ISSAC László Babai, Gene Cooperman, Larry Finkelstein, Ákos Seress
1991	J	`jnl`	Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. László Babai, Lance Fortnow, Carsten Lund
1991	J	`jnl`	Vertex-transitive graphs and vertex-transitive maps. J. Graph Theory László Babai
1990	A*	`conf`	A Characterization of \sharp P Arithmetic Straight Line Programs FOCS László Babai, Lance Fortnow
1990	—	`conf`	E-mail and the Unexpected Power of Interaction. SCT László Babai
1990	J	`jnl`	Extremal subgraphs of random graphs. J. Graph Theory László Babai, Miklós Simonovits, Joel Spencer
1990	J	`jnl`	Lower Bounds to the Complexity of Symmetric Boolean Functions. Theor. Comput. Sci. László Babai, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi
1990	A*	`conf`	Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols FOCS László Babai, Lance Fortnow, Carsten Lund
1990	A*	`conf`	On the Diameter of Finite Groups FOCS László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress
1989	A*	`conf`	Computing Irreducible Representations of Finite Groups FOCS László Babai, Lajos Rónyai
1989	A*	`conf`	Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) STOC László Babai, Noam Nisan, Mario Szegedy
1989	J	`jnl`	Proving Properties of Interactive Proofs by a Generalized Counting Technique Inf. Comput. László Babai, Shlomo Moran
1989	J	`jnl`	Small-diameter Cayley Graphs for Finite Simple Groups. Eur. J. Comb. László Babai, William M. Kantor, A. Lubotsky
1989	J	`jnl`	The probability of generating the symmetric group. J. Comb. Theory A László Babai
1988	J	`jnl`	A short proof of the non-uniform Ray Chauhuri - Wilson inequality. Comb. László Babai
1988	J	`jnl`	Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes. J. Comput. Syst. Sci. László Babai, Shlomo Moran
1988	A*	`conf`	Fast Management of Permutation Groups FOCS László Babai, Eugene M. Luks, Ákos Seress
1988	J	`jnl`	On the Limits of Computations with the Floor Function Inf. Comput. László Babai, Bettina Just, Friedhelm Meyer auf der Heide
1988	J	`jnl`	On the diameter of cayley graphs of the symmetric group. J. Comb. Theory A László Babai, Ákos Seress
1987	J	`jnl`	A Lower Bound for Read-Once-Only Branching Programs. J. Comput. Syst. Sci. László Babai, Péter Hajnal, Endre Szemerédi, György Turán
1987	J	`jnl`	On the Nonuniform Fisher Inequality. Discret. Math. László Babai
1987	J	`jnl`	On the degree of transitivity of permutation groups: A short proof. J. Comb. Theory A László Babai, Ákos Seress
1987	A*	`conf`	Permutation Groups in NC STOC László Babai, Eugene M. Luks, Ákos Seress
1987	J	`jnl`	Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy. Inf. Process. Lett. László Babai
1987	J	`jnl`	The Complexity of Defining a Relation on a Finite Graph. Math. Log. Q. László Babai, György Turán
1986	J	`jnl`	A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms Noga Alon, László Babai, Alon Itai
1986	A*	`conf`	A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues FOCS László Babai
1986	A*	`conf`	Complexity classes in communication complexity theory (preliminary version) FOCS László Babai, Peter Frankl, Janos Simon
1986	J	`jnl`	On Lovász' lattice reduction and the nearest lattice point problem. Comb. László Babai
1986	A*	`conf`	Two lower bounds for branching programs STOC 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
1985	J	`jnl`	An anti-Ramsey theorem. Graphs Comb. László Babai
1985	J	`jnl`	Arc transitive covering digraphs and their eigenvalues. J. Graph Theory László Babai
1985	A	`conf`	On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version). STACS László Babai
1985	J	`jnl`	Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs. Eur. J. Comb. László Babai, Vera T. Sós
1985	A*	`conf`	Trading Group Theory for Randomness STOC László Babai
1984	A*	`conf`	On the Complexity of Matrix Group Problems I FOCS László Babai, Endre Szemerédi
1983	A*	`conf`	Canonical Labeling of Graphs STOC László Babai, Eugene M. Luks
1983	A*	`conf`	Computational Complexity and the Classification of Finite Simple Groups FOCS László Babai, William M. Kantor, Eugene M. Luks
1982	A*	`conf`	Isomorphism of Graphs with Bounded Eigenvalue Multiplicity STOC László Babai, D. Yu. Grigoryev, David M. Mount
1982	J	`jnl`	On the Automorphism Groups of almost all Cayley Graphs. Eur. J. Comb. László Babai, Chris D. Godsil
1981	B	`conf`	Moderately Exponential Bound for Graph Isomorphism. FCT László Babai
1980	J	`jnl`	Endomorphism monoids and topological subgraphs of graphs. J. Comb. Theory B László Babai, Ales Pultr
1980	J	`jnl`	On Set Intersections. J. Comb. Theory A László Babai, Peter Frankl
1980	J	`jnl`	On the Complexity of Canonical Labeling of Strongly Regular Graphs. SIAM J. Comput. László Babai
1980	J	`jnl`	Random Graph Isomorphism. SIAM J. Comput. László Babai, Paul Erdös, Stanley M. Selkow
1979	A*	`conf`	Canonical Labelling of Graphs in Linear Average Time FOCS László Babai, Ludek Kucera
1979	J	`jnl`	Long cycles in vertex-transitive graphs. J. Graph Theory László Babai
1979	J	`jnl`	Spectra of Cayley graphs. J. Comb. Theory B László Babai
1978	J	`jnl`	Infinite digraphs with given regular automorphism groups. J. Comb. Theory B László Babai
1978	J	`jnl`	Vector representable matroids of given rank with given automorphism group. Discret. Math. László Babai
1977	J	`jnl`	Some applications of graph contractions. J. Graph Theory László Babai
1974	J	`jnl`	Automorphism groups of graphs and edge-contraction. Discret. Math. László Babai
1973	J	`jnl`	On groups of polyhedral graphs. Discret. Math. László Babai, Wilfried Imrich
1972	J	`jnl`	Automorphism groups of planar graphs I. Discret. Math. László Babai