A probabilistic remark on algebraic program testing
From MaRDI portal
Publication:1253894
DOI10.1016/0020-0190(78)90067-4zbMath0397.68011OpenAlexW1968245619WikidataQ61661701 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
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, 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, Improved hitting set for orbit of ROABPs, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture, A classification of computational assumptions in the algebraic group model, Parameterized complexity of list coloring and max coloring, Polynomial modular product verification and its implications, Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation, Equivalence of polynomial identity testing and polynomial factorization, Monomials in arithmetic circuits: complete problems in the counting hierarchy, A fast parallel algorithm for minimum-cost small integral flows, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, Constrained multilinear detection and generalized graph motifs, A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties
Cites Work
