We show that any nonzero polynomial in the ideal generated by the r× r minors of an n× n
matrix X can be used to efficiently approximate the determinant. Specifically, for any nonzero …

Newton iteration is an almost 350-year-old recursive formula that approximates a simple root
of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that …

Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size
s, we show that all its factors can be computed by arithmetic branching programs of size poly …

The border, or the approximative, model of algebraic computation (VP) is quite popular due
to the Geometric Complexity Theory (GCT) approach to P≠ NP conjecture, and its complex …

Schur Polynomials are families of symmetric polynomials that have been classically studied
in Combinatorics and Algebra alike. They play a central role in the study of symmetric …

Algebraic complexity is about studying polynomials from a computational viewpoint. In this
thesis, we report progress on the following three problems in algebraic complexity. A …

Abstract Given ideals In⊆ F [x1,... xn] for each n, what can we say about the circuit
complexity of polynomial families fn in those ideals, that is, such that fn∈ In for all n? Such …