Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amit Sinhababu:

TR21-072 | 23rd May 2021
Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

Arithmetic Circuit Complexity of Division and Truncation

Given polynomials $f,g,h\,\in \mathbb{F}[x_1,\ldots,x_n]$ such that $f=g/h$, where both $g$ and $h$ are computable by arithmetic circuits of size $s$, we show that $f$ can be computed by a circuit of size $\poly(s,\deg(h))$. This solves a special case of division elimination for high-degree circuits (Kaltofen'87 \& WACT'16). The result ... more >>>

TR20-077 | 19th May 2020
Amit Sinhababu, Thomas Thierauf

Factorization of Polynomials Given by Arithmetic Branching Programs

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 $\text{poly}(s)$. Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was ... more >>>

TR18-019 | 28th January 2018
Zeyu Guo, Nitin Saxena, Amit Sinhababu

Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

TR17-153 | 9th October 2017
Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Discovering the roots: Uniform closure results for algebraic classes under factoring

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>

ISSN 1433-8092 | Imprint