activity
20122026
most citedIdentity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

9 citations · 13 across the 9 of their papers we have counts for

collaborators
Showing 2016Show all

2 papers · 1 filter

cs.CC2016

Bipartite Perfect Matching is in quasi-NC

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC. That is, it has uniform circuits of quasi-polynomial size , and depth. Previousl…

cs.CC2016★ 9 cited

Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

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 order of the variables. T…