NDLI: Simple algebras are difficult

Please wait, while we are loading the content...

Matrix multiplication via arithmetic progressions

Solving minimum-cost flow problems by successive approximation

A new approach to all pairs shortest paths in planar graphs

An algorithm for linear programming which requires $O(((m+n)n^{2}+(m+n)^{1.5}n)L)$ arithmetic operations

A Linear time algorithm for computing the Voronoi diagram of a convex polygon

Testing for cycles in infinite graphs with periodic structure

Approximation algorithms for shortest path motion planning

The complexity of cutting convex polytypes

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Optimal bounds for decision problems on the CRCW PRAM

Two tapes are better than one for off-line Turing machines

Finite monoids and the fine structure of $NC^{1}$

The strong exponential hierarchy collapses

The Boolean formula value problem is in ALOGTIME

Deterministic simulation in LOGSPACE

Properties that characterize LOGCFL

Some consequences of the existence of pseudorandom generators

Efficiency considerations in using semi-random sources

Imperfect random sources and discrete controlled processes

The power of randomness for communication complexity

Towards a theory of software protection and simulation by oblivious RAMs

On hiding information from an oracle

The complexity of perfect zero-knowledge

Zero knowledge proofs of identity

How to play ANY mental game

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

Analysis of backoff protocols for multiple access channels

Dynamic parallel complexity of computational circuits

Constructing disjoint paths on expander graphs

Reconfiguring a hypercube in the presence of faults

On the learnability of Boolean formulae

On learning Boolean functions

A model for hierarchical memory

Parallel symmetry-breaking in sparse graphs

A random NC algorithm for depth first search

A new graphy triconnectivity algorithm and its parallelization

Matching is as easy as matrix inversion

Fast parallel algorithms for chordal graphs

Two algorithms for maintaining order in a list

An optimal online algorithm for metrical task systems

Searching a two key table under a single key

The page number of genus g graphs is (g)

Simple algebras are difficult

Permutation groups in NC

Threshold spectra for random graphs

The decision problem for the probabilities of higher-order properties

Size-time complexity of Boolean networks for prefix computations

Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials

Realistic analysis of some randomized algorithms

Recognizing primes in random polynomial time

Simple algebras are difficult

Content Provider	ACM Digital Library
Author	Ronyai, L.
Abstract	Let F be a finite field or an algebraic number field. In previous work we have shown how to find the basic building blocks (the radical and the simple components) of a finite dimensional algebra over F in polynomial time (deterministically in characteristic zero and Las Vegas in the finite case). Here we address the more general problem of finding zero divisors in A. This problem is equivalent to finding a nontrivial common invariant subspace of a set of linear operators and includes, as a subcase, the problem of factoring polynomials over the field in question. In [FR] the problem of zero divisors has been reduced, in polynomial time (Las Vegas in the finite case), to the case of simple algebras. We show that, while zero divisors can be found in Las Vegas polynomial time if F is finite, the problem over the rationals might be substantially more difficult. We link the problem to hard number theoretic problems such as quadratic residuosity modulo a composite number. We show that assuming the Generalized Riemann Hypothesis, there exists a randomized polynomial time reduction from quadratic residuosity to determining whether or not a given 4-dimensional algebra over Q has zero divisors. It will follow that finding a pair of zero divisors is at least as hard as factoring squarefree integers.As for the finite case, we give a polynomial time Las Vegas method to construct explicit isomorphisms of matrix algebras. Applications include an algorithm to solve the problem of finding common invariant subspaces for a set of linear operators. Another application answers a question of W. M. Kantor on permutation groups.Finally, as another application of the GRH, we mention a partial result on deterministic factoring over finite fields.
Starting Page	398
Ending Page	408
Page Count	11
File Format	PDF
ISBN	0897912217
DOI	10.1145/28395.28438
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-01-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in