Abstract Near-independence of permutations (2008)
and an almost sure polynomial bound on the diameter of the symmetric group We address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of...
László Babai, William M. Kantor, Péter P. Pálfy, Ákos Seress
Black-box recognition of finite simple groups of
Abstract Product Growth and Mixing in Finite Groups (2008)
László Babai, Nikolay Nikolov, László Pyber
We prove the following inequality on the convolution of distributions over a finite group G: (0.1) � X ∗ Y − U � ≤ � n/m � X − U � � Y − U �, where X, Y are probability...
the diameter of Eulerian orientations of graphs We compare the diameter of a graph with the directed diameter of its Eulerian orientations. We obtain positive results under certain symmetry...
time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991. (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron Testing, László Babai, ...
[4] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of
©North-Holland Publishing Company REPRESENTATION OF GROUP ELEMENTS AS SHORT PRODUCTS (2008)
Dedicated to Professor A. Kotzig on the occasion of his sixtieth birthday We prove that every group G of order n has t,log n/log 2+0dog log n) elements x, x, such that every group element is a...
Institute-New York University. His e-mail address is (2008)
László Babai, Joel Spencer, Uncle Paul, Joel Spencer
Paul Erdős was a searcher, a searcher for mathematical truth. Paul’s place in the mathematical pantheon will be a matter of strong debate, for in that rarefied atmosphere he had a unique style....
statistics of element orders (2008)
László Babai, László Babai, William M. Kantor, Péter P. Pálfy, Ákos Seress
Black-box recognition of finite simple groups of Lie type by
A Convergence Criterion For Recurrent Sequences With Application To The Partition Lattice (2007)
. We prove a fairly general convergence criterion for sequences satisfying a linear recurrence (defined by an infinite triangular matrix). We prove that every sequence of positive numbers satisfying...
Simultaneous Messages vs. Communication (2007)
László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam
In the multiparty communication game introduced by Chandra, Furst, and Lipton [CFL] (1983), k players wish to evaluate collaboratively a function f(x0 , ..., xk\Gamma1 ) for which player i sees all...
Master’s Paper [ROUGH DRAFT]: 2 Dimensional Min-Filters with Polygons (2007)
Paolo Codenotti, Advisors László Babai, Pedro Felzenszwalb, Exam Committee, László Babai, Pedro Felzenszwalb, ...
Computing min-filters is an important operation in image processing. Min-filters are the basic building blocks for translation invariant morphological operators, which are used to perform operations...
On the number of p-regular elements in finite simple groups (2007)
A p-regular element in a finite group is an element of order not divisible by the prime number p. We show that for every prime p and every finite simple group S, a fair proportion of elements of S is...
Property Testing of Equivalence under a Permutation Group Action, under preperation (2007)
László Babai, Sourav Chakraborty
For a permutation group G acting on the set Ω we say that two strings x, y: Ω → {0, 1} are G-isomorphic if they are equivalent under the action of G, i. e., if for some π ∈ G we have x(i π)...
Subdirectly Reducible Groups and Edge-Minimal Graphs with Given Automorphism Group (2006)
Babai, László, Goodman, Albert J.
A group is subdirectly reducible if it has two non-trivial normal subgroups with trivial intersection. Such groups may be an easy case in certain inductive arguments. We prove that every solvable...
Finite groups of uniform logarithmic diameter (2006)
We demonstrate the existence of an infinite family of finite groups with 2 generators and logarithmic diameter with respect to any set of generators. This answers a question of A. Lubotzky. Moreover,...
Computing rank convolutions with a mask (2006)
László Babai, Pedro Felzenszwalb
Min-convolution and more generally, rank-convolutions play an important role in many application areas, including nonlinear signal processing, pattern recognition, computer vision, and combinatorial...
Sourav Chakraborty, László Babai
We discuss several complexity measures for Boolean functions: sensitivity, block sensitivity, ℓ-block sensitivity, certificate complexity, average sensitivity and average block sensitivity. We...
Finite groups of uniform logarithmic diameter (2005)
We give an example of an infinite family of finite groups Gn such that each Gn can be generated by 2 elements and the diameter of every Cayley graph of Gn is O(log(|Gn|)). This answers a question of...
Locally testable cyclic codes (2003)
Cyclic linear codes of block length n over a finite field Fq are linear subspaces of F n q that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in...
Communication Complexity of Simultaneous Messages (2003)
László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam
In the multiparty communication game (CFL-game) of Chandra, Furst, and Lipton (Proc.
Near-representations of finite groups (2003)
László Babai, Katalin Friedl, András Lukács
A near-representation of a group G is a map M: G → GL(V), where V is a complex linear space and Mgh ≈ MgMh for all g, h ∈ G, i.e. M is approximately a homomorphism. Analogously to the...
Locally testable cyclic codes (2003)
László Babai, Amir Shpilka, Daniel Stefankovič
Cyclic linear codes of block length n over a finite field Fq are linear subspaces of F n q that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in...
On the number of zero-patterns of a sequence of polynomials (2002)
Lajos Rónyai, László Babai, K. Ganapathy
Let f =(f1,...,fm) be a sequence of polynomials of degree ≤ d in n variables (m ≥ n) overafieldF. The zero-pattern of f at u ∈ F n is the set of those i (1 ≤ i ≤ m) forwhichfi(u) =0. LetZF...
On the number of zero-patterns of a sequence of polynomials (2002)
Lajos Rónyai, László Babai, K. Ganapathy
Let f = (f1,..., fm) be a sequence of polynomials of degree ≤ d in n variables (m ≥ n) over a field F. The zero-pattern of f at u ∈ F n is the set of those i (1 ≤ i ≤ m) for which fi(u) =...
Dedicated to the Memory of Paul Erdős (2000)
László Babai, Thomas P, Peter G
We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b − 1 bits of...
Almost All Symmetric Functions Are as Powerful as Majority (1999)
László Babai, Bruno Codenotti, János Simon
We consider the power of constant depth, polynomial size circuits with Boolean gates (AND, OR, NOT) and gates which compute a symmetric Boolean function g. We show that for any constant ffl ? 0, for...
Randomized Simultaneous Messages (1996)
In the two-player communication model introduced by Yao [Y79], Alice and Bob wish to collaboratively evaluate a function f(x; y) in which Alice knows only input x and Bob knows only input y. Both...
Superpolynomial Lower Bounds for Monotone Span Programs (1996)
László Babai, Anna Gál, Avi Wigderson
In this paper we obtain the first superpolynomial lower bounds for monotone span programs computing explicit functions. The best previous lower bound was \Omega\Gamma n 5=2 ) by Beimel, G'al,...
Simultaneous Messages vs. Communication (1996)
László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam
In the multiparty communication game introduced by Chandra, Furst, and Lipton [CFL] (1983), k players wish to evaluate collaboratively a function f(x0 ; : : : ; xk\Gamma1 ) in which player i sees all...
Paul Erdős, László Babai, Carl Pomerance, Péter Vértesi, Paul Erdős Number, Carl Pomerance
a memorial article appears elsewhere in this issue. This feature article gives a cross section of his monumental oeuvre. Most of Erdős’s work falls roughly into the following categories: •...
Transparent Proofs and Limits to Approximation (1994)
We survey a major collective accomplishment of the theoretical computer science community on efficiently verifiable proofs. Informally, a formal proof is transparent (or holographic) if it can be...
Simultaneous Messages vs. Communication (1994)
In the multiparty communication game introduced by Chandra, Furst, and Lipton (1983), k players wish to evaluate collaboratively a function f(x 0 ; : : : ; x k\Gamma1 ) for which player i sees all...
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs (1993)
László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson, Ma P
. We show that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time ffi collapses to the second level of the polynomial-time hierarchy, ffi has...
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols (1991)
László Babai, Lance Fortnow, Carsten Lund
. We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers...
Arithmetization: A New Method In Structural Complexity Theory (1991)
. We introduce a technique of arithmetization of the process of computation in order to obtain novel characterizations of certain complexity classes via multivariate polynomials. A variety of...
Checking Computations in Polylogarithmic Time (1991)
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof...
Abstract. We present an O(V 4 log V) coin flipping algorithm to test vertex-colored graphs with bounded color multiplicities for color-preserving isomorphism. We are also able to generate uniformly...
Babai, László, Papp, Julius Gy, Parratt, James R, Végh, Ágnes
Dogs, anaesthetized with chloralose and urethane, were subjected to a 25 min occlusion of the left anterior descending coronary artery. This resulted in ventricular ectopic activity, a reduction in...
Black-box recognition of finite simple groups of Lie type by statistics of element orders
László Babai, William M. Kantor, Péter P. Pálfy, Ákos Seress
Given a black-box group G isomorphic to some finite simple group of Lie type and the characteristic of G, we compute the standard name of G by a Monte Carlo algorithm. The running time is polynomial...