Arrow Research search

Author name cluster

Robert Beals

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
1 author row

Possible papers

11

STOC Conference 2009 Conference Paper

Polynomial-time theory of matrix groups

  • László Babai
  • Robert Beals
  • Ákos Seress

We consider matrix groups, specified by a list of generators, over finite fields. The two most basic questions about such groups are membership in and the order of the group. Even in the case of abelian groups it is not known how to answer these questions without solving hard number theoretic problems (factoring and discrete log); in fact, constructive membership testing in the case of 1 × 1 matrices is precisely the discrete log problem. So the reasonable question is whether these problems are solvable in randomized polynomial time using number theory oracles. Building on 25 years of work, including remarkable recent developments by several groups of authors, we are now able to determine the order of a matrix group over a finite field of odd characteristic, and to perform constructive membership testing in such groups, in randomized polynomial time, using oracles for factoring and discrete log. One of the new ingredients of this result is the following. A group is called semisimple if it has no abelian normal subgroups. For matrix groups over finite fields, we show that the order of the largest semisimple quotient can be determined in randomized polynomial time (no number theory oracles required and no restriction on parity). As a by-product, we obtain a natural problem that belongs to BPP and is not known to belong either to RP or to coRP. No such problem outside the area of matrix groups appears to be known. The problem is the decision version of the above: Given a list A of nonsingular d × d matrices over a finite field and an integer N, does the group generated by A have a semisimple quotient of order > N? We also make progress in the area of constructive recognition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become Las Vegas.

Details

FOCS Conference 1998 Conference Paper

Quantum Lower Bounds by Polynomials

  • Robert Beals
  • Harry Buhrman
  • Richard Cleve
  • Michele Mosca
  • Ronald de Wolf

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0, 1}/sup N/ in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i. e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T/sup 6/) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

Details

FOCS Conference 1995 Conference Paper

Algorithms for Matrix Groups and the Tits Alternative

  • Robert Beals

J. Tits (1972) has shown that a finitely generated linear group either contains a nonabelian free group or has a solvable subgroup of finite index. We give a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. Noting that many computational problems are undecidable for groups with nonabelian free subgroups, we investigate the complexity of problems relating to linear groups with solvable subgroups of finite index. For such a group G, we are able in polynomial time to compute a homomorphism /spl phi/ such that /spl phi/(G) is a finite matrix group and the kernel of /spl phi/ is solvable. If in addition G has a nilpotent subgroup of finite index, we obtain much stronger results. These include an effective encoding of elements of G such that the encoding length of an element obtained as a product of length /spl les/l over the generators is O(logl) times a polynomial in the input length. This result is the best possible. For groups with abelian subgroups of finite index, we obtain a Las Vegas algorithm for several basic computational tasks including membership testing and computing a presentation. This generalizes recent work of R. Beals and L. Babai (1993), who give a Las Vegas algorithm for the case of finite groups.

Details

FOCS Conference 1993 Conference Paper

Las Vegas algorithms for matrix groups

  • Robert Beals
  • László Babai

We consider algorithms in finite groups, given by a list of generators. We give polynomial time Las Vegas algorithms (randomized, with guaranteed correct output) for basic problems for finite matrix groups over the rationals (and over algebraic number fields): testing membership, determining the order, finding a presentation (generators and relations), and finding basic building blocks: center, composition factors, and Sylow subgroups. These results extend previous work on permutation groups into the potentially more significant domain of matrix groups. Such an extension has until recently been considered intractable. In case of matrix groups G of characteristic p, there are two basic types of obstacles to polynomial-time computation: number theoretic (factoring, discrete log) and large Lie-type simple groups of the same characteristic p involved in the group. The number theoretic obstacles are inherent and appear already in handling abelian groups. They can be handled by moderately efficient (subexponential) algorithms. We are able to locate all the nonabelian obstacles in a normal subgroup N and solve all problems listed above for G/N. >

Details