All reports by Author Arpita Korwar:

__
TR16-009
| 28th January 2016
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Identity Testing for constant-width, and commutative, read-once oblivious ABPs

__
TR14-158
| 26th November 2014
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf#### Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

__
TR14-085
| 29th June 2014
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for ROABP and Sum of Set-Multilinear circuits

__
TR13-174
| 6th December 2013
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for low-distance multilinear depth-$3$

__
TR13-112
| 12th August 2013
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf#### Exact Perfect Matching in Complete Graphs

__
TR13-019
| 31st January 2013
__

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf#### On Two-Level Poset Games

__
TR11-148
| 3rd November 2011
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf#### Planarizing Gadgets for Perfect Matching do not Exist

Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost $(nw)^{O(\log n)}$, where $n$ is the number of variables and $w$ is the width of ... more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

A read once ABP is an arithmetic branching program with each variable occurring 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, i.e. ... more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

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 time-complexity 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 ... more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

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 define a notion of ... more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect ... more >>>

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

We consider the complexity of determining the winner of a finite, two-level poset game.

This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.

We give a simple formula allowing one to compute the status ...
more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.

The obvious way to construct such a reduction is via a {\em planarizing ...
more >>>