Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
From MaRDI portal
Publication:3962460
DOI10.1145/322358.322373zbMath0497.68013OpenAlexW2011758726MaRDI QIDQ3962460
Publication date: 1983
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322358.322373
Related Items
On the complexity of pattern matching for highly compressed two-dimensional texts., On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, Evaluating Matrix Circuits, Feasible arithmetic computations: Valiant's hypothesis, Unnamed Item, Straight-line programs in geometric elimination theory, Processing succinct matrices and vectors, On enumerating monomials and other combinatorial structures by polynomial interpolation, Emptiness problems for integer circuits, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, On the complexity of commutativity analysis, Classifying the computational complexity of problems, Knapsack in graph groups, Probabilistic algorithms and straight-line programs for some rank decision problems, An arithmetic Poisson formula for the multi-variate resultant, On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Evaluation of circuits over nilpotent and polycyclic groups, Straight-line instruction sequence completeness for total calculation on cancellation meadows, Kronecker's and Newton's approaches to solving: a first comparison, Parallel identity testing for skew circuits with big powers and applications, The complexity of equivalence for commutative rings, Geometric complexity theory V: Efficient algorithms for Noether normalization, Emptiness Problems for Integer Circuits, Compression techniques in group theory
