dblp.uni-trier.dewww.uni-trier.de

László Babai Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
96EELászló Babai, Robert Beals, Ákos Seress: Polynomial-time theory of matrix groups. STOC 2009: 55-64
2008
95EELászló Babai, Paolo Codenotti: Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS 2008: 667-676
94EELászló Babai, Nikolay Nikolov, László Pyber: Product growth and mixing in finite groups. SODA 2008: 248-257
93EESourav Chakraborty, László Babai: Property Testing of Equivalence under a Permutation Group Action. Electronic Colloquium on Computational Complexity (ECCC) 15(040): (2008)
2007
92EELászló Babai, Igor Gorodezky: Sandpile transience on the grid is polynomially bounded. SODA 2007: 627-636
2006
91EELászló Babai: On the diameter of Eulerian orientations of graphs. SODA 2006: 822-831
90EELászló Babai: Automorphism groups of graphs and edge-contraction. Discrete Mathematics 306(10-11): 918-922 (2006)
89EELá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
88EELá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
87EELá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
85EELászló Babai, Robert Beals, Ákos Seress: On the diameter of the symmetric group: polynomial bounds. SODA 2004: 1108-1112
84EELászló Babai, Daniel Stefankovic: Simultaneous diophantine approximation with excluded primes. SODA 2004: 1123-1129
83EELászló Babai, Igor Pak: Strong bias of group generators: an obstacle to the "product replacement algorithm". J. Algorithms 50(2): 215-231 (2004)
2003
82EELászló Babai, Amir Shpilka, Daniel Stefankovic: Locally Testable Cyclic Codes. FOCS 2003: 116-125
81EELá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
80EELászló Babai, Thomas P. Hayes, Peter G. Kimmel: The Cost of the Missing Bit: Communication Complexity with Help. Combinatorica 21(4): 455-488 (2001)
79EELá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
78EELászló Babai, Igor Pak: Strong bias of group generators: an obstacle to the ``product replacement algorithm''. SODA 2000: 627-635
77EELászló Babai, Peter J. Cameron: Automorphisms and Enumeration of Switching Classes of Tournaments. Electr. J. Comb. 7: (2000)
1999
76EELászló Babai, Sophie Laplante: Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. IEEE Conference on Computational Complexity 1999: 98-104
75EELászló Babai, Anna Gál, Avi Wigderson: Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica 19(3): 301-319 (1999)
1998
74EELászló Babai, Thomas P. Hayes, Peter G. Kimmel: The Cost of the Missing Bit: Communication Complexity with Help. STOC 1998: 673-682
1997
73EELá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
72EELászló Babai: Communication Complexity. MFCS 1997: 5-18
71 László Babai: The Growth Rate of Vertex-Transitive Planar Graphs. SODA 1997: 564-573
70EELá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
66EELá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
65EELá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)
61EELá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
58EELászló Babai, Robert Beals, Daniel N. Rockmore: Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time. ISSAC 1993: 117-126
57EELászló Babai, Katalin Friedl, Markus Stricker: Decomposition of *-closed Algebras in Polynomial Time. ISSAC 1993: 86-94
56EELá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
54EELá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
46EELá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)
39EENoga 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)
30EELá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)
26EELá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
23EELá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)
21EELá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
14EELá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)
6EELá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
2EELászló Babai: Spectra of Cayley graphs. J. Comb. Theory, Ser. B 27(2): 180-189 (1979)
1978
1EELászló Babai: Infinite digraphs with given regular automorphism groups. J. Comb. Theory, Ser. B 25(1): 26-46 (1978)

Coauthor Index

1Miklós Ajtai [17]
2Noga Alon [15] [39]
3Sanjeev Arora [59] [69]
4Robert Beals [53] [58] [60] [67] [85] [96]
5Jin-yi Cai [67]
6Peter J. Cameron [77]
7Sourav Chakraborty [93]
8Paolo Codenotti [95]
9Gene Cooperman [43] [46] [63]
10Paul Erdös [4]
11Larry Finkelstein [43] [46] [63]
12Lance Fortnow [37] [38] [40] [41] [44] [50] [55]
13Peter Frankl [7] [18] [79]
14Katalin Friedl [47] [57]
15Anna Gál [66] [75] [81]
16Igor Gorodezky [92]
17D. Yu. Grigoryev [9]
18Péter Hajnal [17] [20]
19Thomas P. Hayes [74] [80] [88]
20Friedhelm Meyer auf der Heide [27]
21Gábor Hetyei [36] [51]
22Alon Itai [15]
23Gábor Ivanyos [67]
24Bettina Just [27]
25William M. Kantor [11] [36]
26Peter G. Kimmel [65] [73] [74] [80] [81]
27János Kollár [66]
28János Komlós [17]
29Ludek Kucera [3]
30Samuel Kutin [79]
31Sophie Laplante [76]
32Leonid A. Levin [44]
33Satyanarayana V. Lokam [65] [81]
34Alexander Lubotzky [36]
35Eugene M. Luks [10] [11] [24] [29] [43] [63] [67] [68]
36Carsten Lund [38] [41] [50]
37Shlomo Moran [25] [31]
38David M. Mount [9]
39Nikolay Nikolov [94]
40Noam Nisan [32] [42] [49] [55]
41Haluk Oral [61]
42Igor Pak [78] [83]
43Kevin T. Phelps [61]
44Pavel Pudlák [17] [34]
45Ales Pultr [6]
46László Pyber [62] [94]
47Daniel N. Rockmore [58]
48Vojtech Rödl [17] [34]
49Lajos Rónyai [33] [66]
50Stanley M. Selkow [4]
51Ákos Seress [21] [24] [26] [29] [36] [43] [46] [63] [68] [85] [96]
52Amir Shpilka [82] [87]
53Janos Simon [18]
54Daniel Stefankovic [79] [82] [84] [87]
55Jacques Stern [59] [69]
56Markus Stricker [57]
57H. Suzuki [39]
58Z. Sweedyk [59] [69]
59Tibor Szabó [66]
60Mario Szegedy [32] [44] [49] [52]
61Endre Szemerédi [12] [17] [20] [34]
62Pál Takácsi-Nagy [53]
63György Turán [17] [20]
64Avi Wigderson [55] [66] [75]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)