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"”.
-
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 …
-
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. …
-
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 …
-
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, …
-
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 …
-
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
-
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, …