Fast Probabilistic Algorithms for Verification of Polynomial Identities
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Multipartite secret sharing by bivariate interpolation
- A parameterized view on matroid optimization problems
- Maximum weight bipartite matching in matrix multiplication time
- Approximate string matching with address bit errors
- Factoring sparse multivariate polynomials
- Irreducibility of multivariate polynomials
- Matching is as easy as matrix inversion
- Complexity of parallel matrix computations
- Constructing a perfect matching is in random NC
- Automatic parameterization of rational curves and surfaces. III: Algebraic plane curves
- Rubber bands, convex embeddings and graph connectivity
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Polymatroids: Construction and random algorithms
- The image of weighted combinatorial problems
- An introduction to randomized algorithms
- Generalized sum graphs
- Random pseudo-polynomial algorithms for some combinatorial programming problems
- Improved processor bounds for combinatorial problems in RNC
- On interpolating arithmetic read-once formulas with exponentiation
- Elimination of parameters in the polynomial hierarchy
- Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones
- Finding the radical of matrix algebras using Fitting decompositions
- The computational complexity of some problems of linear algebra
- Decomposition of algebras over \(F_ q(X_ 1,\dots,X_ m)\)
- Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
- Probabilistically checkable proofs and their consequences for approximation algorithms
- On the degree of Boolean functions as real polynomials
- Efficient matrix preconditioners for black box linear algebra
- On the hardness of computing the permanent of random matrices
- Testing the shift-equivalence of polynomials using quantum machines
- Parallel computation of polynomial GCD and some related parallel computations over abstract fields
- Straight-line programs in geometric elimination theory
- Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines.
- On testing for zero polynomials by a set of points with bounded precision.
- Cardinality constrained minimum cut problems: complexity and algorithms.
- Efficient decomposition of separable algebras.
- Randomized algorithms over finite fields for the exact parity base problem.
- Effective equidimensional decomposition of affine varieties
- The Elekes-Szabó theorem in four dimensions
- On division polynomial PIT and supersingularity
- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- Quantum compression relative to a set of measurements
- Homomorphic signatures with sublinear public keys via asymmetric programmable hash functions
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Sparse resultants and straight-line programs
- Resultant elimination via implicit equation interpolation
- On the genericity of maximum rank distance and Gabidulin codes
- Joint equidistribution of CM points
- Maximum weight spectrum codes
- Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces
- Practical homomorphic message authenticators for arithmetic circuits
- Computing girth and cogirth in perturbed graphic matroids
- An efficient solution for Cauchy-like systems of linear equations
- On the equations relating a three-dimensional object and its two-dimensional images
- A probabilistic algorithm for verifying polynomial middle product in linear time
- A new approach to fast polynomial interpolation and multipoint evaluation
- Orthogonal representations and connectivity of graphs
- Randomised algorithms
- The time-precision tradeoff problem on on-line probabilistic Turing machines
- Functional programming concepts and straight-line programs in computer algebra
- Lower bounds for dynamic algebraic problems
- On the complexity of pattern matching for highly compressed two-dimensional texts.
- Early termination in sparse interpolation algorithms
- Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
- Fast computation of discrete invariants associated to a differential rational mapping
- Complexity results for triangular sets
- Computing Cartan subalgebras of Lie algebras
- Extractors for varieties
- Weighted Reed-Muller codes revisited
- Randomized preprocessing versus pivoting
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
- A case of depth-3 identity testing, sparse factorization and duality
- Computational indistinguishability: A sample hierarchy
- New techniques for the computation of linear recurrence coefficients
- Superfast algorithms for Cauchy-like matrix computations and extensions
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- A fast parallel sparse polynomial GCD algorithm
- Verification protocols with sub-linear communication for polynomial matrix operations
- A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
- Sparse affine-invariant linear codes are locally testable
- Linear matroid intersection is in quasi-NC
- Heuristic algorithms for recognition of some cubic hypersurfaces
- Obfuscating circuits via composite-order graded encoding
- On subversion-resistant SNARKs
- Blackbox identity testing for sum of special ROABPs and its border class
- Many-visits TSP revisited
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- Fast verification of masking schemes in characteristic two
- A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices
- Univariate ideal membership parameterized by rank, degree, and number of generators
- Simple multi-party set reconciliation
- An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
- Improved hitting set for orbit of ROABPs
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 2 submatrices
- Don't tamper with dual system encryption. Beyond polynomial related-key security of IBE
- Parameterized complexity of list coloring and max coloring
- Polynomial modular product verification and its implications
- Computing valuations of the Dieudonné determinants
- An efficient certificate-based signature scheme in the standard model
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
This page was built for publication: Fast Probabilistic Algorithms for Verification of Polynomial Identities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3899517)
