A probabilistic remark on algebraic program testing
From MaRDI portal
Publication:1253894
DOI10.1016/0020-0190(78)90067-4zbMath0397.68011DBLPjournals/ipl/DemilloL78OpenAlexW1968245619WikidataQ61661701 ScholiaQ61661701MaRDI QIDQ1253894
Richard A. DeMillo, Richard J. Lipton
Publication date: 1978
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(78)90067-4
Related Items (only showing first 100 items - show all)
Spotting Trees with Few Leaves ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Integral reduction with Kira 2.0 and finite field methods ⋮ Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly} ⋮ Beyond Uber: instantiating generic groups via PGGs ⋮ Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond ⋮ Hardness of graph-structured algebraic and symbolic problems ⋮ Unnamed Item ⋮ Efficient Black-Box Identity Testing for Free Group Algebras ⋮ Improved Explicit Hitting-Sets for ROABPs ⋮ Detecting and Counting Small Pattern Graphs ⋮ Linear independence, alternants, and applications ⋮ Unnamed Item ⋮ Numerically safe Gaussian elimination with no pivoting ⋮ Early termination in sparse interpolation algorithms ⋮ Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases ⋮ Zero testing of algebraic functions ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Spotting Trees with Few Leaves ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Schur aggregation for linear systems and determinants ⋮ Efficient matrix preconditioners for black box linear algebra ⋮ Finding linear dependencies in integration-by-parts equations: a Monte Carlo approach ⋮ Additive preconditioning for matrix computations ⋮ Parametric nonlinear discrete optimization over well-described sets and matroid intersections ⋮ Generic complexity of the membership problem for semigroups of integer matrices ⋮ Parameterized algorithms for the module motif problem ⋮ Parallel computation of polynomial GCD and some related parallel computations over abstract fields ⋮ Derandomization from Algebraic Hardness ⋮ Narrow sieves for parameterized paths and packings ⋮ Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic ⋮ Unnamed Item ⋮ Straight-line programs in geometric elimination theory ⋮ Chevalley-Warning at the boundary ⋮ The Schur aggregation and solving ill conditioned linear systems: the convergence theorem ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Minimisation of Multiplicity Tree Automata ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Weighted Reed-Muller codes revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Additive Preconditioning for Matrix Computations ⋮ Matrix computations and polynomial root-finding with preprocessing ⋮ Randomized preprocessing versus pivoting ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Sparse interpolation of multivariate rational functions ⋮ Two notions of correctness and their relation to testing ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Joint equidistribution of CM points ⋮ Solving linear systems of equations with randomization, augmentation and aggregation ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Efficient decomposition of separable algebras. ⋮ New techniques for the computation of linear recurrence coefficients ⋮ On Zeros of a Polynomial in a Finite Grid ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Superfast algorithms for Cauchy-like matrix computations and extensions ⋮ Read-once polynomial identity testing ⋮ Recent Results on Polynomial Identity Testing ⋮ Degeneration of structured integer matrices modulo an integer ⋮ Odd properly colored cycles in edge-colored graphs ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ On the Alon-Füredi bound ⋮ On multivariate polynomials with many roots over a finite grid ⋮ Practical homomorphic message authenticators for arithmetic circuits ⋮ Solving structured linear systems with large displacement rank ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Categories generated by a trivalent vertex ⋮ Additive preconditioning, eigenspaces, and the inverse iteration ⋮ Algorithms for topology-free and alignment network queries ⋮ Randomized preprocessing of homogeneous linear systems of equations ⋮ An efficient solution for Cauchy-like systems of linear equations ⋮ New progress in real and complex polynomial root-finding ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ On measures of space over real and complex numbers ⋮ The inverse moment problem for convex polytopes ⋮ A note on parameterized polynomial identity testing using hitting set generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Linear matroid intersection is in quasi-NC ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ Elimination-based certificates for triangular equivalence and rank profiles ⋮ Estimating the norms of random circulant and Toeplitz matrices and their inverses ⋮ A probabilistic algorithm for verifying polynomial middle product in linear time ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Backward error analysis of the extended iterative refinement or improvement algorithm for solving ill conditioned linear system ⋮ Many-visits TSP revisited ⋮ A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density ⋮ Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones ⋮ Unnamed Item ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ Bipartite Perfect Matching is in Quasi-NC
Cites Work
This page was built for publication: A probabilistic remark on algebraic program testing
