Source author record

Arpita Korwar

Arpita Korwar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

What is connected

2works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity $n^{O(\log n)}$. In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-$3$ circuits. The prior results for the sum of constantly many set-multilinear depth-$3$ circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

preprint2014arXiv

Hitting-sets for ROABP and Sum of Set-Multilinear circuits

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best result known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their exponential dependence on the individual degree. With this, we match the time-complexity for the unknown order ROABP with the known order ROABP (due to Forbes-Shpilka (FOCS 2013)) and also with the depth-$3$ set-multilinear circuits (due to Agrawal-Saha-Saxena (STOC 2013)). Our proof is simpler and involves a new technique called basis isolation. The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper, we take a step towards designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-$3$ circuits. To achieve this, we define notions of distance and base sets. Distance, for a multilinear depth-$3$ circuit, measures how far are the partitions from a mere refinement. We design a hitting-set in time $n^{O(d \log n)}$ for $d$-distance. Further, we give an extension of our result to models where the distance is large but it is small when restricted to certain base sets (of variables). We also explore a new model of ROABP where the factor-matrices are invertible (called invertible-factor ROABP). We design a hitting-set in time poly($n^{w^2}$) for width-$w$ invertible-factor ROABP. Further, we could do without the invertibility restriction when $w=2$. Previously, the best result for width-$2$ ROABP was quasi-polynomial time (Forbes-Saptharishi-Shpilka, STOC 2014).