All reports by Author Rohit Gurjar:

__
TR24-044
| 28th February 2024
__

Rohit Gurjar, Taihei Oki, Roshan Raj#### Fractional Linear Matroid Matching is in quasi-NC

__
TR23-075
| 17th May 2023
__

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj#### Border Complexity of Symbolic Determinant under Rank One Restriction

__
TR21-121
| 21st August 2021
__

Sumanta Ghosh, Rohit Gurjar#### Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision

__
TR20-098
| 4th July 2020
__

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf#### Impossibility of Derandomizing the Isolation Lemma for all Families

__
TR16-182
| 14th November 2016
__

Rohit Gurjar, Thomas Thierauf#### Linear Matroid Intersection is in quasi-NC

__
TR16-009
| 28th January 2016
__

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

__
TR15-177
| 9th November 2015
__

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf#### Bipartite Perfect Matching is in quasi-NC

Revisions: 2

__
TR14-161
| 27th November 2014
__

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari#### Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

Revisions: 2

__
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, Taihei Oki, Roshan Raj

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose ... more >>>

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem ... more >>>

Sumanta Ghosh, Rohit Gurjar

We study the matroid intersection problem from the parallel complexity perspective. Given

two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted ...
more >>>

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

Rohit Gurjar, Thomas Thierauf

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

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

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... 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 >>>