| 2008 |
|---|
| 95 | EE | László Babai,
Paolo Codenotti:
Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time.
FOCS 2008: 667-676 |
| 94 | EE | László Babai,
Nikolay Nikolov,
László Pyber:
Product growth and mixing in finite groups.
SODA 2008: 248-257 |
| 93 | EE | Sourav Chakraborty,
László Babai:
Property Testing of Equivalence under a Permutation Group Action.
Electronic Colloquium on Computational Complexity (ECCC) 15(040): (2008) |
| 2007 |
|---|
| 92 | EE | László Babai,
Igor Gorodezky:
Sandpile transience on the grid is polynomially bounded.
SODA 2007: 627-636 |
| 2006 |
|---|
| 91 | EE | László Babai:
On the diameter of Eulerian orientations of graphs.
SODA 2006: 822-831 |
| 90 | EE | László Babai:
Automorphism groups of graphs and edge-contraction.
Discrete Mathematics 306(10-11): 918-922 (2006) |
| 89 | EE | 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) |
| 2005 |
|---|
| 88 | EE | 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: 1057-1066 |
| 87 | EE | László Babai,
Amir Shpilka,
Daniel Stefankovic:
Locally testable cyclic codes.
IEEE Transactions on Information Theory 51(8): 2849-2858 (2005) |
| 2004 |
|---|
| 86 | | László Babai:
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004
ACM 2004 |
| 85 | EE | László Babai,
Robert Beals,
Ákos Seress:
On the diameter of the symmetric group: polynomial bounds.
SODA 2004: 1108-1112 |
| 84 | EE | László Babai,
Daniel Stefankovic:
Simultaneous diophantine approximation with excluded primes.
SODA 2004: 1123-1129 |
| 83 | EE | László Babai,
Igor Pak:
Strong bias of group generators: an obstacle to the "product replacement algorithm".
J. Algorithms 50(2): 215-231 (2004) |
| 2003 |
|---|
| 82 | EE | László Babai,
Amir Shpilka,
Daniel Stefankovic:
Locally Testable Cyclic Codes.
FOCS 2003: 116-125 |
| 81 | EE | László Babai,
Anna Gál,
Peter G. Kimmel,
Satyanarayana V. Lokam:
Communication Complexity of Simultaneous Messages.
SIAM J. Comput. 33(1): 137-166 (2003) |
| 2001 |
|---|
| 80 | EE | László Babai,
Thomas P. Hayes,
Peter G. Kimmel:
The Cost of the Missing Bit: Communication Complexity with Help.
Combinatorica 21(4): 455-488 (2001) |
| 79 | EE | László Babai,
Peter Frankl,
Samuel Kutin,
Daniel Stefankovic:
Set Systems with Restricted Intersections modulo Prime Powers.
J. Comb. Theory, Ser. A 95(1): 39-73 (2001) |
| 2000 |
|---|
| 78 | EE | László Babai,
Igor Pak:
Strong bias of group generators: an obstacle to the ``product replacement algorithm''.
SODA 2000: 627-635 |
| 77 | EE | László Babai,
Peter J. Cameron:
Automorphisms and Enumeration of Switching Classes of Tournaments.
Electr. J. Comb. 7: (2000) |
| 1999 |
|---|
| 76 | EE | László Babai,
Sophie Laplante:
Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.
IEEE Conference on Computational Complexity 1999: 98-104 |
| 75 | EE | László Babai,
Anna Gál,
Avi Wigderson:
Superpolynomial Lower Bounds for Monotone Span Programs.
Combinatorica 19(3): 301-319 (1999) |
| 1998 |
|---|
| 74 | EE | László Babai,
Thomas P. Hayes,
Peter G. Kimmel:
The Cost of the Missing Bit: Communication Complexity with Help.
STOC 1998: 673-682 |
| 1997 |
|---|
| 73 | EE | László Babai,
Peter G. Kimmel:
Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity.
IEEE Conference on Computational Complexity 1997: 239-246 |
| 72 | | László Babai:
Communication Complexity.
MFCS 1997: 5-18 |
| 71 | | László Babai:
The Growth Rate of Vertex-Transitive Planar Graphs.
SODA 1997: 564-573 |
| 70 | EE | László Babai:
Paul Erdös (1913-1996): His Influence on the Theory of Computing.
STOC 1997: 383-401 |
| 69 | | 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): 317-331 (1997) |
| 68 | | László Babai,
Eugene M. Luks,
Ákos Seress:
Fast Management of Permutation Groups I.
SIAM J. Comput. 26(5): 1310-1342 (1997) |
| 1996 |
|---|
| 67 | | László Babai,
Robert Beals,
Jin-yi Cai,
Gábor Ivanyos,
Eugene M. Luks:
Multiplicative Equations over Commuting Matrices.
SODA 1996: 498-507 |
| 66 | EE | 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: 603-611 |
| 1995 |
|---|
| 65 | | László Babai,
Peter G. Kimmel,
Satyanarayana V. Lokam:
Simultaneous Messages vs. Communication.
STACS 1995: 361-372 |
| 64 | | László Babai:
A New Proof of Several Inequalities on Codes and Sets.
J. Comb. Theory, Ser. A 71(1): 146-153 (1995) |
| 63 | | 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): 296-308 (1995) |
| 1994 |
|---|
| 62 | | László Babai,
László Pyber:
Permutation Groups without Exponentially Many Orbits on the Power Set.
J. Comb. Theory, Ser. A 66(1): 160-168 (1994) |
| 61 | EE | László Babai,
Haluk Oral,
Kevin T. Phelps:
Eulerian Self-Dual Codes.
SIAM J. Discrete Math. 7(2): 325-330 (1994) |
| 1993 |
|---|
| 60 | | Robert Beals,
László Babai:
Las Vegas algorithms for matrix groups
FOCS 1993: 427-436 |
| 59 | | Sanjeev Arora,
László Babai,
Jacques Stern,
Z. Sweedyk:
The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations
FOCS 1993: 724-733 |
| 58 | EE | László Babai,
Robert Beals,
Daniel N. Rockmore:
Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time.
ISSAC 1993: 117-126 |
| 57 | EE | László Babai,
Katalin Friedl,
Markus Stricker:
Decomposition of *-closed Algebras in Polynomial Time.
ISSAC 1993: 86-94 |
| 56 | | László Babai:
Transparent (Holographic) Proofs.
STACS 1993: 525-534 |
| 55 | | László Babai,
Lance Fortnow,
Noam Nisan,
Avi Wigderson:
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
Computational Complexity 3: 307-318 (1993) |
| 1992 |
|---|
| 54 | EE | László Babai:
Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time.
SODA 1992: 33-40 |
| 53 | | László Babai,
Robert Beals,
Pál Takácsi-Nagy:
Symmetry and Complexity
STOC 1992: 438-449 |
| 52 | | László Babai,
Mario Szegedy:
Local Expansion of Ssymmetrical Graphs.
Combinatorics, Probability & Computing 1: 1-11 (1992) |
| 51 | | László Babai,
Gábor Hetyei:
On the Diameter of Random Cayley Graphs of the Symmetric Group.
Combinatorics, Probability & Computing 1: 201-208 (1992) |
| 50 | | László Babai,
Lance Fortnow,
Carsten Lund:
Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity 2: 374 (1992) |
| 49 | | László Babai,
Noam Nisan,
Mario Szegedy:
Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs.
J. Comput. Syst. Sci. 45(2): 204-232 (1992) |
| 48 | | László Babai:
Bounded Round Interactive Proofs in Finite Groups.
SIAM J. Discrete Math. 5(1): 88-111 (1992) |
| 1991 |
|---|
| 47 | | László Babai,
Katalin Friedl:
Approximate Representation Theory of Finite Groups
FOCS 1991: 733-742 |
| 46 | EE | László Babai,
Gene Cooperman,
Larry Finkelstein,
Ákos Seress:
Nearly Linear Time Algorithms for Permutation Groups with a Small Base.
ISSAC 1991: 200-209 |
| 45 | | László Babai:
Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups
STOC 1991: 164-174 |
| 44 | | László Babai,
Lance Fortnow,
Leonid A. Levin,
Mario Szegedy:
Checking Computations in Polylogarithmic Time
STOC 1991: 21-31 |
| 43 | | László Babai,
Gene Cooperman,
Larry Finkelstein,
Eugene M. Luks,
Ákos Seress:
Fast Monte Carlo Algorithms for Permutation Groups
STOC 1991: 90-100 |
| 42 | | László Babai,
Noam Nisan:
BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs.
Structure in Complexity Theory Conference 1991: 213-219 |
| 41 | | László Babai,
Lance Fortnow,
Carsten Lund:
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity 1: 3-40 (1991) |
| 40 | | László Babai,
Lance Fortnow:
Arithmetization: A New Method in Structural Complexity Theory.
Computational Complexity 1: 41-66 (1991) |
| 39 | EE | Noga Alon,
László Babai,
H. Suzuki:
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.
J. Comb. Theory, Ser. A 58(2): 165-180 (1991) |
| 1990 |
|---|
| 38 | | László Babai,
Lance Fortnow,
Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
FOCS 1990: 16-25 |
| 37 | | László Babai,
Lance Fortnow:
A Characterization of \sharp P Arithmetic Straight Line Programs
FOCS 1990: 26-34 |
| 36 | | László Babai,
Gábor Hetyei,
William M. Kantor,
Alexander Lubotzky,
Ákos Seress:
On the Diameter of Finite Groups
FOCS 1990: 857-865 |
| 35 | | László Babai:
E-mail and the Unexpected Power of Interaction.
Structure in Complexity Theory Conference 1990: 30-44 |
| 34 | | 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): 313-323 (1990) |
| 1989 |
|---|
| 33 | | László Babai,
Lajos Rónyai:
Computing Irreducible Representations of Finite Groups
FOCS 1989: 93-98 |
| 32 | | László Babai,
Noam Nisan,
Mario Szegedy:
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)
STOC 1989: 1-11 |
| 31 | | László Babai,
Shlomo Moran:
Proving Properties of Interactive Proofs by a Generalized Counting Technique
Inf. Comput. 82(2): 185-197 (1989) |
| 30 | EE | László Babai:
The probability of generating the symmetric group.
J. Comb. Theory, Ser. A 52(1): 148-153 (1989) |
| 1988 |
|---|
| 29 | | László Babai,
Eugene M. Luks,
Ákos Seress:
Fast Management of Permutation Groups
FOCS 1988: 272-282 |
| 28 | | László Babai:
A short proof of the non-uniform Ray Chauhuri - Wilson inequality.
Combinatorica 8(1): 133-135 (1988) |
| 27 | | László Babai,
Bettina Just,
Friedhelm Meyer auf der Heide:
On the Limits of Computations with the Floor Function
Inf. Comput. 78(2): 99-107 (1988) |
| 26 | EE | László Babai,
Ákos Seress:
On the diameter of cayley graphs of the symmetric group.
J. Comb. Theory, Ser. A 49(1): 175-179 (1988) |
| 25 | | László Babai,
Shlomo Moran:
Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.
J. Comput. Syst. Sci. 36(2): 254-276 (1988) |
| 1987 |
|---|
| 24 | | László Babai,
Eugene M. Luks,
Ákos Seress:
Permutation Groups in NC
STOC 1987: 409-420 |
| 23 | EE | László Babai:
On the Nonuniform Fisher Inequality.
Discrete Mathematics 66(3): 303-307 (1987) |
| 22 | | László Babai:
Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy.
Inf. Process. Lett. 26(1): 51-53 (1987) |
| 21 | EE | László Babai,
Ákos Seress:
On the degree of transitivity of permutation groups: A short proof.
J. Comb. Theory, Ser. A 45(2): 310-315 (1987) |
| 20 | | 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): 153-162 (1987) |
| 1986 |
|---|
| 19 | | László Babai:
A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues
FOCS 1986: 303-312 |
| 18 | | László Babai,
Peter Frankl,
Janos Simon:
Complexity classes in communication complexity theory (preliminary version)
FOCS 1986: 337-347 |
| 17 | | 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:
Two lower bounds for branching programs
STOC 1986: 30-38 |
| 16 | | László Babai:
On Lovász' lattice reduction and the nearest lattice point problem.
Combinatorica 6(1): 1-13 (1986) |
| 15 | | Noga Alon,
László Babai,
Alon Itai:
A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.
J. Algorithms 7(4): 567-583 (1986) |
| 1985 |
|---|
| 14 | | László Babai:
On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version).
STACS 1985: 13-20 |
| 13 | | László Babai:
Trading Group Theory for Randomness
STOC 1985: 421-429 |
| 1984 |
|---|
| 12 | | László Babai,
Endre Szemerédi:
On the Complexity of Matrix Group Problems I
FOCS 1984: 229-240 |
| 1983 |
|---|
| 11 | | László Babai,
William M. Kantor,
Eugene M. Luks:
Computational Complexity and the Classification of Finite Simple Groups
FOCS 1983: 162-171 |
| 10 | | László Babai,
Eugene M. Luks:
Canonical Labeling of Graphs
STOC 1983: 171-183 |
| 1982 |
|---|
| 9 | | László Babai,
D. Yu. Grigoryev,
David M. Mount:
Isomorphism of Graphs with Bounded Eigenvalue Multiplicity
STOC 1982: 310-324 |
| 1981 |
|---|
| 8 | | László Babai:
Moderately Exponential Bound for Graph Isomorphism.
FCT 1981: 34-50 |
| 1980 |
|---|
| 7 | | László Babai,
Peter Frankl:
On Set Intersections.
J. Comb. Theory, Ser. A 28(1): 103-105 (1980) |
| 6 | EE | László Babai,
Ales Pultr:
Endomorphism monoids and topological subgraphs of graphs.
J. Comb. Theory, Ser. B 28(3): 278-283 (1980) |
| 5 | | László Babai:
On the Complexity of Canonical Labeling of Strongly Regular Graphs.
SIAM J. Comput. 9(1): 212-216 (1980) |
| 4 | | László Babai,
Paul Erdös,
Stanley M. Selkow:
Random Graph Isomorphism.
SIAM J. Comput. 9(3): 628-635 (1980) |
| 1979 |
|---|
| 3 | | László Babai,
Ludek Kucera:
Canonical Labelling of Graphs in Linear Average Time
FOCS 1979: 39-46 |
| 2 | EE | László Babai:
Spectra of Cayley graphs.
J. Comb. Theory, Ser. B 27(2): 180-189 (1979) |
| 1978 |
|---|
| 1 | EE | László Babai:
Infinite digraphs with given regular automorphism groups.
J. Comb. Theory, Ser. B 25(1): 26-46 (1978) |
