The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

László Babai: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  92. Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. [Citation Graph (, )][DBLP]


  93. Weights of Exact Threshold Functions. [Citation Graph (, )][DBLP]


  94. Product growth and mixing in finite groups. [Citation Graph (, )][DBLP]


  95. Evasiveness and the Distribution of Prime Numbers. [Citation Graph (, )][DBLP]


  96. Polynomial-time theory of matrix groups. [Citation Graph (, )][DBLP]


  97. Evasiveness and the Distribution of Prime Numbers [Citation Graph (, )][DBLP]


  98. Property Testing of Equivalence under a Permutation Group Action. [Citation Graph (, )][DBLP]


Search in 0.005secs, Finished in 0.008secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002