Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
László Babai
2010 – today
- 2013
[c58]László Babai, John Wilmes: Quasipolynomial-time canonical form for steiner designs. STOC 2013: 261-270- 2012
- [c57]László Babai, Paolo Codenotti, Youming Qiao: Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract). ICALP (1) 2012: 51-62
- [c56]László Babai, Youming Qiao: Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. STACS 2012: 453-464
- 2011
- [c55]László Babai: Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas. CSR 2011: 162-180
- [c54]László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao: Code Equivalence and Group Isomorphism. SODA 2011: 1395-1408
- 2010
- [c53]László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun: Weights of Exact Threshold Functions. MFCS 2010: 66-77
- [c52]László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik: Evasiveness and the Distribution of Prime Numbers. STACS 2010: 71-82
- [i2]László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik: Evasiveness and the Distribution of Prime Numbers. CoRR abs/1001.4829 (2010)
2000 – 2009
- 2009
- [j48]László Babai, Barry Guiduli: Spectral Extrema for Graphs: The Zarankiewicz Problem. Electr. J. Comb. 16(1) (2009)
- [j47]László Babai, Pedro F. Felzenszwalb: Computing rank-convolutions with a mask. ACM Transactions on Algorithms 6(1) (2009)
- [c51]
- 2008
- [c50]László Babai, Paolo Codenotti: Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS 2008: 667-676
- [c49]László Babai, Nikolay Nikolov, László Pyber: Product growth and mixing in finite groups. SODA 2008: 248-257
- [i1]Sourav Chakraborty, László Babai: Property Testing of Equivalence under a Permutation Group Action. Electronic Colloquium on Computational Complexity (ECCC) 15(040) (2008)
- 2007
- [c48]László Babai, Igor Gorodezky: Sandpile transience on the grid is polynomially bounded. SODA 2007: 627-636
- 2006
- [j46]László Babai: Automorphism groups of graphs and edge-contraction. Discrete Mathematics 306(10-11): 918-922 (2006)
- [j45]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)
- [c47]
- 2005
- [j44]László Babai, Amir Shpilka, Daniel Stefankovic: Locally testable cyclic codes. IEEE Transactions on Information Theory 51(8): 2849-2858 (2005)
- [c46]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
- 2004
- [j43]László Babai, Igor Pak: Strong bias of group generators: an obstacle to the "product replacement algorithm". J. Algorithms 50(2): 215-231 (2004)
- [c45]László Babai, Robert Beals, Ákos Seress: On the diameter of the symmetric group: polynomial bounds. SODA 2004: 1108-1112
- [c44]László Babai, Daniel Stefankovic: Simultaneous diophantine approximation with excluded primes. SODA 2004: 1123-1129
- [e1]László Babai (Ed.): Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. ACM 2004, ISBN 1-58113-852-0
- 2003
- [j42]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)
- [c43]
- 2001
- [j41]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)
- [j40]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
- [j39]László Babai, Peter J. Cameron: Automorphisms and Enumeration of Switching Classes of Tournaments. Electr. J. Comb. 7 (2000)
- [c42]
1990 – 1999
- 1999
- [j38]László Babai, Anna Gál, Avi Wigderson: Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica 19(3): 301-319 (1999)
- [c41]László Babai, Sophie Laplante: Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. IEEE Conference on Computational Complexity 1999: 98-104
- 1998
- [c40]László Babai, Thomas P. Hayes, Peter G. Kimmel: The Cost of the Missing Bit: Communication Complexity with Help. STOC 1998: 673-682
- 1997
- [j37]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)
- [j36]László Babai, Eugene M. Luks, Ákos Seress: Fast Management of Permutation Groups I. SIAM J. Comput. 26(5): 1310-1342 (1997)
- [c39]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
- [c38]
- [c37]
- [c36]
- 1996
- [c35]László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks: Multiplicative Equations over Commuting Matrices. SODA 1996: 498-507
- [c34]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
- [j35]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)
- [j34]László Babai: A New Proof of Several Inequalities on Codes and Sets. J. Comb. Theory, Ser. A 71(1): 146-153 (1995)
- [c33]László Babai, Peter G. Kimmel, Satyanarayana V. Lokam: Simultaneous Messages vs. Communication. STACS 1995: 361-372
- 1994
- [j33]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)
- [j32]László Babai, Haluk Oral, Kevin T. Phelps: Eulerian Self-Dual Codes. SIAM J. Discrete Math. 7(2): 325-330 (1994)
- 1993
- [j31]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)
- [c32]
- [c31]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
- [c30]László Babai, Katalin Friedl, Markus Stricker: Decomposition of *-closed Algebras in Polynomial Time. ISSAC 1993: 86-94
- [c29]László Babai, Robert Beals, Daniel N. Rockmore: Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time. ISSAC 1993: 117-126
- [c28]
- 1992
- [j30]László Babai, Lance Fortnow, Carsten Lund: Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 2: 374 (1992)
- [j29]László Babai, Mario Szegedy: Local Expansion of Ssymmetrical Graphs. Combinatorics, Probability & Computing 1: 1-11 (1992)
- [j28]László Babai, Gábor Hetyei: On the Diameter of Random Cayley Graphs of the Symmetric Group. Combinatorics, Probability & Computing 1: 201-208 (1992)
- [j27]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)
- [j26]László Babai: Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discrete Math. 5(1): 88-111 (1992)
- [c27]
- [c26]
- 1991
- [j25]László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1: 3-40 (1991)
- [j24]László Babai, Lance Fortnow: Arithmetization: A New Method in Structural Complexity Theory. Computational Complexity 1: 41-66 (1991)
- [j23]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)
- [j22]László Babai: Vertex-transitive graphs and vertex-transitive maps. Journal of Graph Theory 15(6): 587-627 (1991)
- [c25]László Babai, Noam Nisan: BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. Structure in Complexity Theory Conference 1991: 213-219
- [c24]László Babai, Katalin Friedl: Approximate Representation Theory of Finite Groups. FOCS 1991: 733-742
- [c23]László Babai, Gene Cooperman, Larry Finkelstein, Ákos Seress: Nearly Linear Time Algorithms for Permutation Groups with a Small Base. ISSAC 1991: 200-209
- [c22]László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time. STOC 1991: 21-31
- [c21]László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress: Fast Monte Carlo Algorithms for Permutation Groups. STOC 1991: 90-100
- [c20]László Babai: Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups. STOC 1991: 164-174
- 1990
- [j21]László Babai, Miklós Simonovits, Joel Spencer: Extremal subgraphs of random graphs. Journal of Graph Theory 14(5): 599-622 (1990)
- [j20]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)
- [c19]László Babai: E-mail and the Unexpected Power of Interaction. Structure in Complexity Theory Conference 1990: 30-44
- [c18]László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. FOCS 1990: 16-25
- [c17]László Babai, Lance Fortnow: A Characterization of \sharp P Arithmetic Straight Line Programs. FOCS 1990: 26-34
- [c16]László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress: On the Diameter of Finite Groups. FOCS 1990: 857-865
1980 – 1989
- 1989
- [j19]László Babai, Shlomo Moran: Proving Properties of Interactive Proofs by a Generalized Counting Technique. Inf. Comput. 82(2): 185-197 (1989)
- [j18]László Babai: The probability of generating the symmetric group. J. Comb. Theory, Ser. A 52(1): 148-153 (1989)
- [c15]László Babai, Lajos Rónyai: Computing Irreducible Representations of Finite Groups. FOCS 1989: 93-98
- [c14]László Babai, Noam Nisan, Mario Szegedy: Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract). STOC 1989: 1-11
- 1988
- [j17]László Babai: A short proof of the non-uniform Ray Chauhuri - Wilson inequality. Combinatorica 8(1): 133-135 (1988)
- [j16]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)
- [j15]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)
- [j14]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)
- [c13]László Babai, Eugene M. Luks, Ákos Seress: Fast Management of Permutation Groups. FOCS 1988: 272-282
- 1987
- [j13]
- [j12]László Babai: Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy. Inf. Process. Lett. 26(1): 51-53 (1987)
- [j11]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)
- [j10]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)
- [c12]
- 1986
- [j9]László Babai: On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica 6(1): 1-13 (1986)
- [j8]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)
- [c11]László Babai: A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues. FOCS 1986: 303-312
- [c10]László Babai, Peter Frankl, Janos Simon: Complexity classes in communication complexity theory (preliminary version). FOCS 1986: 337-347
- [c9]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
- 1985
- [j7]
- [c8]László Babai: On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version). STACS 1985: 13-20
- [c7]
- 1984
- [c6]
- 1983
- [c5]László Babai, William M. Kantor, Eugene M. Luks: Computational Complexity and the Classification of Finite Simple Groups. FOCS 1983: 162-171
- [c4]
- 1982
- [c3]László Babai, D. Yu. Grigoryev, David M. Mount: Isomorphism of Graphs with Bounded Eigenvalue Multiplicity. STOC 1982: 310-324
- 1981
- [c2]
- 1980
- [j6]
- [j5]László Babai, Ales Pultr: Endomorphism monoids and topological subgraphs of graphs. J. Comb. Theory, Ser. B 28(3): 278-283 (1980)
- [j4]László Babai: On the Complexity of Canonical Labeling of Strongly Regular Graphs. SIAM J. Comput. 9(1): 212-216 (1980)
- [j3]László Babai, Paul Erdös, Stanley M. Selkow: Random Graph Isomorphism. SIAM J. Comput. 9(3): 628-635 (1980)
1970 – 1979
- 1979
- [j2]
- [c1]
- 1978
- [j1]László Babai: Infinite digraphs with given regular automorphism groups. J. Comb. Theory, Ser. B 25(1): 26-46 (1978)
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-05-28 02:37 CEST by the dblp team