Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDLászló Babai
Laci Babai
Person information
- affiliation: University of Chicago, Departments of Computer Science and Mathematics
- award (2015): Knuth Prize
- award (1993): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2021
[c66]László Babai
, Bohdan Kivva:
Matrix Rigidity Depends on the Target Field. CCC 2021: 41:1-41:26
2010 – 2019
- 2019
- [c65]László Babai:
Canonical form for graphs in quasipolynomial time: preliminary report. STOC 2019: 1237-1246 - 2018
- [c64]László Babai, Timothy J. F. Black, Angela Wuu:
List-Decoding Homomorphism Codes with Arbitrary Codomains. APPROX-RANDOM 2018: 29:1-29:18 - [i6]László Babai, Timothy J. F. Black, Angela Wuu:
List-decoding homomorphism codes with arbitrary codomains. CoRR abs/1806.02969 (2018) - 2016
- [c63]László Babai:
Graph isomorphism in quasipolynomial time [extended abstract]. STOC 2016: 684-697 - 2015
- [i5]László Babai, John Wilmes:
Asymptotic Delsarte cliques in distance-regular graphs. CoRR abs/1503.02746 (2015) - [i4]László Babai:
Graph Isomorphism in Quasipolynomial Time. CoRR abs/1512.03547 (2015) - [i3]László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán:
The Graph Isomorphism Problem (Dagstuhl Seminar 15511). Dagstuhl Reports 5(12): 1-17 (2015) - 2014
- [c62]László Babai:
On the automorphism groups of strongly regular graphs I. ITCS 2014: 359-368 - 2013
- [j62]László Babai, Simon Guest, Cheryl E. Praeger, Robert A. Wilson:
Proportions of r-regular elements in finite classical groups. J. Lond. Math. Soc. 88(1): 202-226 (2013) - [c61]László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes:
Faster Canonical Forms for Strongly Regular Graphs. FOCS 2013: 157-166 - [c60]László Babai, John Wilmes:
Quasipolynomial-time canonical form for steiner designs. STOC 2013: 261-270 - 2012
- [c59]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 - [c58]László Babai, Youming Qiao:
Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. STACS 2012: 453-464 - 2011
- [c57]László Babai:
Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas. CSR 2011: 162-180 - [c56]László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao:
Code Equivalence and Group Isomorphism. SODA 2011: 1395-1408 - 2010
- [c55]László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun:
Weights of Exact Threshold Functions. MFCS 2010: 66-77 - [c54]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
- [j61]László Babai, Barry Guiduli:
Spectral Extrema for Graphs: The Zarankiewicz Problem. Electron. J. Comb. 16(1) (2009) - [j60]László Babai, Pedro F. Felzenszwalb:
Computing rank-convolutions with a mask. ACM Trans. Algorithms 6(1): 20:1-20:13 (2009) - [c53]László Babai, Robert Beals, Ákos Seress:
Polynomial-time theory of matrix groups. STOC 2009: 55-64 - 2008
- [c52]László Babai, Paolo Codenotti:
Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS 2008: 667-676 - [c51]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. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c50]László Babai, Igor Gorodezky:
Sandpile transience on the grid is polynomially bounded. SODA 2007: 627-636 - 2006
- [j59]László Babai:
Automorphism groups of graphs and edge-contraction. Discret. Math. 306(10-11): 918-922 (2006) - [j58]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) - [c49]László Babai:
On the diameter of Eulerian orientations of graphs. SODA 2006: 822-831 - 2005
- [j57]László Babai, Amir Shpilka, Daniel Stefankovic:
Locally testable cyclic codes. IEEE Trans. Inf. Theory 51(8): 2849-2858 (2005) - [c48]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
- [j56]László Babai, Igor Pak:
Strong bias of group generators: an obstacle to the "product replacement algorithm". J. Algorithms 50(2): 215-231 (2004) - [c47]László Babai, Robert Beals, Ákos Seress:
On the diameter of the symmetric group: polynomial bounds. SODA 2004: 1108-1112 - [c46]László Babai, Daniel Stefankovic:
Simultaneous diophantine approximation with excluded primes. SODA 2004: 1123-1129 - [e1]László Babai:
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 [contents] - 2003
- [j55]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) - [c45]László Babai, Amir Shpilka, Daniel Stefankovic:
Locally Testable Cyclic Codes. FOCS 2003: 116-125 - 2001
- [j54]László Babai, Thomas P. Hayes, Peter G. Kimmel:
The Cost of the Missing Bit: Communication Complexity with Help. Comb. 21(4): 455-488 (2001) - [j53]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
- [j52]László Babai, Peter J. Cameron:
Automorphisms and Enumeration of Switching Classes of Tournaments. Electron. J. Comb. 7 (2000) - [c44]László Babai, Igor Pak:
Strong bias of group generators: an obstacle to the "product replacement algorithm". SODA 2000: 627-635
1990 – 1999
- 1999
- [j51]László Babai, Anna Gál, Avi Wigderson:
Superpolynomial Lower Bounds for Monotone Span Programs. Comb. 19(3): 301-319 (1999) - [c43]László Babai, Sophie Laplante:
Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. CCC 1999: 98-104 - 1998
- [c42]László Babai, Thomas P. Hayes, Peter G. Kimmel:
The Cost of the Missing Bit: Communication Complexity with Help. STOC 1998: 673-682 - 1997
- [j50]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) - [j49]László Babai, Eugene M. Luks, Ákos Seress:
Fast Management of Permutation Groups I. SIAM J. Comput. 26(5): 1310-1342 (1997) - [c41]László Babai, Peter G. Kimmel:
Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. CCC 1997: 239-246 - [c40]László Babai:
Communication Complexity. MFCS 1997: 5-18 - [c39]László Babai:
The Growth Rate of Vertex-Transitive Planar Graphs. SODA 1997: 564-573 - [c38]László Babai:
Paul Erdös (1913-1996): His Influence on the Theory of Computing. STOC 1997: 383-401 - 1996
- [c37]László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, Eugene M. Luks:
Multiplicative Equations over Commuting Matrices. SODA 1996: 498-507 - [c36]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
- [j48]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) - [j47]László Babai:
A New Proof of Several Inequalities on Codes and Sets. J. Comb. Theory, Ser. A 71(1): 146-153 (1995) - [c35]László Babai:
Randomization in group algorithms: Conceptual questions. Groups and Computation 1995: 1-17 - [c34]László Babai, Peter G. Kimmel, Satyanarayana V. Lokam:
Simultaneous Messages vs. Communication. STACS 1995: 361-372 - 1994
- [j46]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) - [j45]László Babai, Haluk Oral, Kevin T. Phelps:
Eulerian Self-Dual Codes. SIAM J. Discret. Math. 7(2): 325-330 (1994) - 1993
- [j44]László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson:
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Comput. Complex. 3: 307-318 (1993) - [c33]Robert Beals, László Babai:
Las Vegas algorithms for matrix groups. FOCS 1993: 427-436 - [c32]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 - [c31]László Babai, Katalin Friedl, Markus Stricker:
Decomposition of *-closed Algebras in Polynomial Time. ISSAC 1993: 86-94 - [c30]László Babai, Robert Beals, Daniel N. Rockmore:
Deciding Finiteness of Matrix Groups in Deterministic Polynomial Time. ISSAC 1993: 117-126 - [c29]László Babai:
Transparent (Holographic) Proofs. STACS 1993: 525-534 - 1992
- [j43]László Babai, Lance Fortnow, Carsten Lund:
Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. 2: 374 (1992) - [j42]László Babai, Mario Szegedy:
Local Expansion of Ssymmetrical Graphs. Comb. Probab. Comput. 1: 1-11 (1992) - [j41]László Babai, Gábor Hetyei:
On the Diameter of Random Cayley Graphs of the Symmetric Group. Comb. Probab. Comput. 1: 201-208 (1992) - [j40]László Babai, Ákos Seress:
On the diameter of permutation groups. Eur. J. Comb. 13(4): 231-243 (1992) - [j39]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) - [j38]László Babai:
Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discret. Math. 5(1): 88-111 (1992) - [c28]László Babai:
Deciding Finiteness of Matrix Groups in Las Vegas Polynomial Time. SODA 1992: 33-40 - [c27]László Babai, Robert Beals, Pál Takácsi-Nagy:
Symmetry and Complexity. STOC 1992: 438-449 - 1991
- [j37]László Babai, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. 1: 3-40 (1991) - [j36]László Babai, Lance Fortnow:
Arithmetization: A New Method in Structural Complexity Theory. Comput. Complex. 1: 41-66 (1991) - [j35]László Babai, Albert J. Goodman, László Lovász:
Graphs with Given Automorphism Group and Few Edge Orbits. Eur. J. Comb. 12(3): 185-203 (1991) - [j34]Noga Alon, László Babai, Hiroshi Suzuki:
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. J. Comb. Theory, Ser. A 58(2): 165-180 (1991) - [j33]László Babai:
Vertex-transitive graphs and vertex-transitive maps. J. Graph Theory 15(6): 587-627 (1991) - [c26]László Babai, Noam Nisan:
BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. SCT 1991: 213-219 - [c25]László Babai, Eugene M. Luks, Ákos Seress:
Computing Composition Series in Primitive Groups. Groups And Computation 1991: 1-16 - [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
- [j32]László Babai, Miklós Simonovits, Joel Spencer:
Extremal subgraphs of random graphs. J. Graph Theory 14(5): 599-622 (1990) - [j31]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. SCT 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
- [j30]László Babai, William M. Kantor, A. Lubotsky:
Small-diameter Cayley Graphs for Finite Simple Groups. Eur. J. Comb. 10(6): 507-522 (1989) - [j29]László Babai, Shlomo Moran:
Proving Properties of Interactive Proofs by a Generalized Counting Technique. Inf. Comput. 82(2): 185-197 (1989) - [j28]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
- [j27]László Babai:
A short proof of the non-uniform Ray Chauhuri - Wilson inequality. Comb. 8(1): 133-135 (1988) - [j26]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) - [j25]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) - [j24]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
- [j23]László Babai:
On the Nonuniform Fisher Inequality. Discret. Math. 66(3): 303-307 (1987) - [j22]László Babai:
Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy. Inf. Process. Lett. 26(1): 51-53 (1987) - [j21]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) - [j20]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) - [j19]László Babai, György Turán:
The Complexity of Defining a Relation on a Finite Graph. Math. Log. Q. 33(3): 277-288 (1987) - [c12]László Babai, Eugene M. Luks, Ákos Seress:
Permutation Groups in NC. STOC 1987: 409-420 - 1986
- [j18]László Babai:
On Lovász' lattice reduction and the nearest lattice point problem. Comb. 6(1): 1-13 (1986) - [j17]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
- [j16]László Babai, Vera T. Sós:
Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs. Eur. J. Comb. 6(2): 101-114 (1985) - [j15]László Babai:
An anti-Ramsey theorem. Graphs Comb. 1(1): 23-28 (1985) - [j14]László Babai:
Arc transitive covering digraphs and their eigenvalues. J. Graph Theory 9(3): 363-370 (1985) - [c8]László Babai:
On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version). STACS 1985: 13-20 - [c7]László Babai:
Trading Group Theory for Randomness. STOC 1985: 421-429 - 1984
- [c6]László Babai, Endre Szemerédi:
On the Complexity of Matrix Group Problems I. FOCS 1984: 229-240 - 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]László Babai, Eugene M. Luks:
Canonical Labeling of Graphs. STOC 1983: 171-183 - 1982
- [j13]László Babai, Chris D. Godsil:
On the Automorphism Groups of almost all Cayley Graphs. Eur. J. Comb. 3(1): 9-15 (1982) - [c3]László Babai, D. Yu. Grigoryev, David M. Mount:
Isomorphism of Graphs with Bounded Eigenvalue Multiplicity. STOC 1982: 310-324 - 1981
- [c2]László Babai:
Moderately Exponential Bound for Graph Isomorphism. FCT 1981: 34-50 - 1980
- [j12]László Babai, Peter Frankl:
On Set Intersections. J. Comb. Theory, Ser. A 28(1): 103-105 (1980) - [j11]