Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 7 of 7 for “"polynomial identity testing"”.

  1. New Lower Bounds in Algebraic Complexity and Connections to Polynomial Identity Testing

    … theory focuses on problems that manipulate polynomials, using models like arithmetic circuits (where each internal gate is either simply an add gate or a multiply gate) to understand the cost of algebraic computation. This thesis investigates two central questions in this area: Can we prove …

    toronto-retro Repository record for New Lower Bounds in Algebraic Complexity and Connections to Polynomial Identity Testing (opens in a new tab)

  2. Learning via automaton minimization and matrix factorization

    … We give a minimization algorithm that runs in polynomial time assuming unit-cost arithmetic, and show that a polynomial bound in the Turing model would require a breakthrough in the complexity of polynomial identity testing. We also improve the complexity of minimizing weighted word automata. …

    oxford Repository record for Learning via automaton minimization and matrix factorization (opens in a new tab)

  3. Algebraic dependence testing in the perspective of algebraic matroids

    … problem called algebraic dependence testing, where we seek to find a polynomial relation among a set of polynomials. This notion generalizes linear dependence, and understanding it has had applications to deterministic polynomial identity testing and algebraic circuit lower bounds. We …

    uiuc Repository record for Algebraic dependence testing in the perspective of algebraic matroids (opens in a new tab)

  4. Algebraic geometric methods for algorithms in satisfiability, irreducibility of varieties, and identity testing

    … computer science. The first of these is the polynomial identity testing problem, which is the task of determining if an algebraic circuit computes the identically zero polynomial. We give the first polynomial time deterministic algorithm for the special case of depth four algebraic circuits, …

    waterloo Repository record for Algebraic geometric methods for algorithms in satisfiability, irreducibility of varieties, and identity testing (opens in a new tab)

  5. Sparse Polynomial Interpolation and Testing

    … is the process of learning an unknown polynomial f from some set of its evaluations. We consider the interpolation of a sparse polynomial, i.e., where f is comprised of a small, bounded number of terms. Sparse interpolation dates back to work in the late 18th century by the French …

    waterloo Repository record for Sparse Polynomial Interpolation and Testing (opens in a new tab)

  6. Polynomial ideals in algebraic complexity

    Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms

    uiuc Repository record for Polynomial ideals in algebraic complexity (opens in a new tab)

  7. Randomness in completeness and space-bounded computations

    … the difficulty of solving any problem in NP. Polynomial-time reductions are at the heart of defining completeness. However, there is no single notion of reduction; researchers identified various polynomial-time reductions such as many-one reduction, truth-table reduction, Turing reduction, …

    iastate Repository record for Randomness in completeness and space-bounded computations (opens in a new tab)