Lajos Rónyai

STOC Conference 1996 Conference Paper

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs

• László Babai
• Anna Gál
• János Kollár
• Lajos Rónyai
• Tibor Szabó
• Avi Wigderson

I&C Journal 1991 Journal Article

Computing the order of centralizers in linear groups

• Lajos Rónyai

In this note we give a polynomial time algorithm to compute the order of the centralizer of a given subgroup of a full linear group over a finite field. The method is deterministic if the characteristic of the ground field is small and Las Vegas in the general case. As an application we whow that the verification of the center of a linear group over a finite field belongs to the complexity class AM. This settles a question of L. Babai.

FOCS Conference 1989 Conference Paper

Computing Irreducible Representations of Finite Groups

• László Babai
• Lajos Rónyai

The bit complexity of computing irreducible representations of finite groups is considered. Exact computations in algebraic number fields are performed symbolically. A polynomial-time algorithm for finding a complete set of inequivalent irreducible representations over the field of complex numbers of a finite group given by its multiplication table is presented. It follows that some representative of each equivalence class of irreducible representations admits a polynomial-size description. The problem of decomposing a given representation V of the finite group G over an algebraic number field F into absolutely irreducible constituents is considered. It is shown that this can be done in deterministic polynomial time if V is given by the list of matrices (V(g); g in G) and in randomized (Las Vegas) polynomial time under the more concise input (V(g); g in S), where S is a set of generators of G. >

FOCS Conference 1989 Conference Paper

Galois Groups and Factoring Polynomials over Finite Fields

• Lajos Rónyai

Let p be a prime and F be a polynomial with integer coefficients. Suppose that the discriminant of F is not divisible by p, and denote by m the degree of the splitting field of F over Q and by L the maximal size of the coefficients of F. Then, assuming the generalized Riemann hypothesis (GRH), it is shown that the irreducible factors of F modulo p can be found in deterministic time polynomial in deg F, m, log p, and L. As an application, it is shown that it is possible under GRH to solve certain equations of the form nP=R, where R is a given and P is an unknown point of an elliptic curve defined over GF(p) in polynomial time (n is counted in unary). An elliptic analog of results obtained recently about factoring polynomials with the help of smooth multiplicative subgroups of finite field is proved. >

FOCS Conference 1987 Conference Paper

Factoring Polynomials over Finite Fields

• Lajos Rónyai

We propose a new deterministic method of factoring polynomials over finite fields. Assuming the Generalized Riemann Hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other consequences include a polynomial time algorithm to find a nontrivial factor of any completely splitting even degree polynomial when a quadratic nonresidue in the field is given.

STOC Conference 1987 Conference Paper

Simple Algebras Are Difficult

• Lajos Rónyai

STOC Conference 1985 Conference Paper

Polynomial Time Solutions of Some Problems in Computational Algebra

• Katalin Friedl
• Lajos Rónyai

The first structure theory in abstract algebra was that of finite dimensional Lie algebras (Cartan-Killing), followed by the structure theory of associative algebras (Wedderburn-Artin). These theories determine, in a non-constructive way, the basic building blocks of the respective algebras (the radical and the simple components of the factor by the radical). In view of the extensive computations done in such algebras, it seems important to design efficient algorithms to find these building blocks. We find polynomial time solutions to a substantial part of these problems. We restrict our attention to algebras over finite fields and over algebraic number fields. We succeed in determining the radical (the “bad part” of the algebra) in polynomial time, using (in the case of prime characteristic) some new algebraic results developed in this paper. For associative algebras we are able to determine the simple components as well. This latter result generalizes factorization of polynomials over the given field. Correspondingly, our algorithm over finite fields is Las Vegas. Some of the results generalize to fields given by oracles. Some fundamental problems remain open. An example: decide whether or not a given rational algebra is a noncommutative field.