Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PRANJAL DUTTA:
All reports by Author Pranjal Dutta:

TR22-157 | 16th November 2022
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

Border complexity via elementary symmetric polynomials

In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, ... more >>>


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 >>>




ISSN 1433-8092 | Imprint