Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Anurag Pandey:

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-031 | 10th March 2020
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

TR16-145 | 16th September 2016
Markus Bläser, Gorav Jindal, Anurag Pandey

Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

Revisions: 2

We consider the problem of commutative rank computation of a given matrix space, $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is $n$, subsumes problems such as testing perfect matching in graphs ... more >>>

ISSN 1433-8092 | Imprint