László Babai

	2012
105		László Babai, Youming Qiao: Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. STACS 2012: 453-464
	2011
104		László Babai: Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas. CSR 2011: 162-180
103		László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao: Code Equivalence and Group Isomorphism. SODA 2011: 1395-1408
	2010
102		László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun: Weights of Exact Threshold Functions. MFCS 2010: 66-77
101		László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik: Evasiveness and the Distribution of Prime Numbers. STACS 2010: 71-82
100		László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik: Evasiveness and the Distribution of Prime Numbers CoRR abs/1001.4829: (2010)
	2009
99		László Babai, Robert Beals, Ákos Seress: Polynomial-time theory of matrix groups. STOC 2009: 55-64
98		László Babai, Pedro F. Felzenszwalb: Computing rank-convolutions with a mask. ACM Transactions on Algorithms 6(1): (2009)
97		László Babai, Barry Guiduli: Spectral Extrema for Graphs: The Zarankiewicz Problem. Electr. J. Comb. 16(1): (2009)
	2008
96		László Babai, Paolo Codenotti: Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS 2008: 667-676
95		László Babai, Nikolay Nikolov, László Pyber: Product growth and mixing in finite groups. SODA 2008: 248-257
94		Sourav Chakraborty, László Babai: Property Testing of Equivalence under a Permutation Group Action. Electronic Colloquium on Computational Complexity (ECCC) 15(040): (2008)
	2007
93		László Babai, Igor Gorodezky: Sandpile transience on the grid is polynomially bounded. SODA 2007: 627-636
	2006
92		László Babai: On the diameter of Eulerian orientations of graphs. SODA 2006: 822-831
91		László Babai: Automorphism groups of graphs and edge-contraction. Discrete Mathematics 306(10-11): 918-922 (2006)
90		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
89		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
88		László Babai, Amir Shpilka, Daniel Stefankovic: Locally testable cyclic codes. IEEE Transactions on Information Theory 51(8): 2849-2858 (2005)
	2004
87		László Babai: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004 ACM 2004
86		László Babai, Robert Beals, Ákos Seress: On the diameter of the symmetric group: polynomial bounds. SODA 2004: 1108-1112
85		László Babai, Daniel Stefankovic: Simultaneous diophantine approximation with excluded primes. SODA 2004: 1123-1129
84		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
83		László Babai, Amir Shpilka, Daniel Stefankovic: Locally Testable Cyclic Codes. FOCS 2003: 116-125
82		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
81		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)
80		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
79		László Babai, Igor Pak: Strong bias of group generators: an obstacle to the ``product replacement algorithm''. SODA 2000: 627-635
78		László Babai, Peter J. Cameron: Automorphisms and Enumeration of Switching Classes of Tournaments. Electr. J. Comb. 7: (2000)
	1999
77		László Babai, Sophie Laplante: Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. IEEE Conference on Computational Complexity 1999: 98-104
76		László Babai, Anna Gál, Avi Wigderson: Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica 19(3): 301-319 (1999)
	1998
75		László Babai, Thomas P. Hayes, Peter G. Kimmel: The Cost of the Missing Bit: Communication Complexity with Help. STOC 1998: 673-682
	1997
74		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
73		László Babai: Communication Complexity. MFCS 1997: 5-18
72		László Babai: The Growth Rate of Vertex-Transitive Planar Graphs. SODA 1997: 564-573
71		László Babai: Paul Erdös (1913-1996): His Influence on the Theory of Computing. STOC 1997: 383-401
70		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)
69		László Babai, Eugene M. Luks, Ákos Seress: Fast Management of Permutation Groups I. SIAM J. Comput. 26(5): 1310-1342 (1997)
	1996
68		László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks: Multiplicative Equations over Commuting Matrices. SODA 1996: 498-507
67		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
66		László Babai, Peter G. Kimmel, Satyanarayana V. Lokam: Simultaneous Messages vs. Communication. STACS 1995: 361-372
65		László Babai: A New Proof of Several Inequalities on Codes and Sets. J. Comb. Theory, Ser. A 71(1): 146-153 (1995)
64		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
63		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)
62		László Babai, Haluk Oral, Kevin T. Phelps: Eulerian Self-Dual Codes. SIAM J. Discrete Math. 7(2): 325-330 (1994)
	1993
61		Robert Beals, László Babai: Las Vegas algorithms for matrix groups FOCS 1993: 427-436
60		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
59		László Babai, Robert Beals, Daniel N. Rockmore: Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time. ISSAC 1993: 117-126
58		László Babai, Katalin Friedl, Markus Stricker: Decomposition of *-closed Algebras in Polynomial Time. ISSAC 1993: 86-94
57		László Babai: Transparent (Holographic) Proofs. STACS 1993: 525-534
56		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
55		László Babai: Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time. SODA 1992: 33-40
54		László Babai, Robert Beals, Pál Takácsi-Nagy: Symmetry and Complexity STOC 1992: 438-449
53		László Babai, Mario Szegedy: Local Expansion of Ssymmetrical Graphs. Combinatorics, Probability & Computing 1: 1-11 (1992)
52		László Babai, Gábor Hetyei: On the Diameter of Random Cayley Graphs of the Symmetric Group. Combinatorics, Probability & Computing 1: 201-208 (1992)
51		László Babai, Lance Fortnow, Carsten Lund: Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 2: 374 (1992)
50		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)
49		László Babai: Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discrete Math. 5(1): 88-111 (1992)
	1991
48		László Babai, Katalin Friedl: Approximate Representation Theory of Finite Groups FOCS 1991: 733-742
47		László Babai, Gene Cooperman, Larry Finkelstein, Ákos Seress: Nearly Linear Time Algorithms for Permutation Groups with a Small Base. ISSAC 1991: 200-209
46		László Babai: Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups STOC 1991: 164-174
45		László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time STOC 1991: 21-31
44		László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress: Fast Monte Carlo Algorithms for Permutation Groups STOC 1991: 90-100
43		László Babai, Noam Nisan: BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. Structure in Complexity Theory Conference 1991: 213-219
42		László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1: 3-40 (1991)
41		László Babai, Lance Fortnow: Arithmetization: A New Method in Structural Complexity Theory. Computational Complexity 1: 41-66 (1991)
40		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
39		László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols FOCS 1990: 16-25
38		László Babai, Lance Fortnow: A Characterization of \sharp P Arithmetic Straight Line Programs FOCS 1990: 26-34
37		László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress: On the Diameter of Finite Groups FOCS 1990: 857-865
36		László Babai: E-mail and the Unexpected Power of Interaction. Structure in Complexity Theory Conference 1990: 30-44
35		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
34		László Babai, Lajos Rónyai: Computing Irreducible Representations of Finite Groups FOCS 1989: 93-98
33		László Babai, Noam Nisan, Mario Szegedy: Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) STOC 1989: 1-11
32		László Babai, Shlomo Moran: Proving Properties of Interactive Proofs by a Generalized Counting Technique Inf. Comput. 82(2): 185-197 (1989)
31		László Babai: The probability of generating the symmetric group. J. Comb. Theory, Ser. A 52(1): 148-153 (1989)
	1988
30		László Babai, Eugene M. Luks, Ákos Seress: Fast Management of Permutation Groups FOCS 1988: 272-282
29		László Babai: A short proof of the non-uniform Ray Chauhuri - Wilson inequality. Combinatorica 8(1): 133-135 (1988)
28		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)
27		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)
26		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
25		László Babai, Eugene M. Luks, Ákos Seress: Permutation Groups in NC STOC 1987: 409-420
24		László Babai: On the Nonuniform Fisher Inequality. Discrete Mathematics 66(3): 303-307 (1987)
23		László Babai: Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy. Inf. Process. Lett. 26(1): 51-53 (1987)
22		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)
21		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
20		László Babai: A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues FOCS 1986: 303-312
19		László Babai, Peter Frankl, Janos Simon: Complexity classes in communication complexity theory (preliminary version) FOCS 1986: 337-347
18		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
17		László Babai: On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica 6(1): 1-13 (1986)
16		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
15		László Babai: On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version). STACS 1985: 13-20
14		László Babai: Trading Group Theory for Randomness STOC 1985: 421-429
13		László Babai: An anti-Ramsey theorem. Graphs and Combinatorics 1(1): 23-28 (1985)
	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		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		László Babai: Spectra of Cayley graphs. J. Comb. Theory, Ser. B 27(2): 180-189 (1979)
	1978
1		László Babai: Infinite digraphs with given regular automorphism groups. J. Comb. Theory, Ser. B 25(1): 26-46 (1978)

Coauthor Index

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

Colors in the list of coauthors

Last update Sat May 26 04:23:17 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page