11 citations · 17 across the 4 of their papers we have counts for
4 papers
Deterministic Black-Box Identity Testing -Ordered Algebraic Branching Programs
Maurice Jansen, Youming Qiao, Jayalal Sarma
In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation of variab…
Deterministic Identity Testing of Read-Once Algebraic Branching Programs
Maurice Jansen, Youming Qiao, Jayalal Sarma
In this paper we study polynomial identity testing of sums of read-once algebraic branching programs (-RO-ABPs), generalizing the work in (Shpilka and Volkovich 2008,2009)…
Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion
Maurice Jansen
In (Kabanets, Impagliazzo, 2004) it is shown how to decide the circuit polynomial identity testing problem (CPIT) in deterministic subexponential time, assuming hardness of some ex…
Balancing Bounded Treewidth Circuits
Maurice Jansen, Jayalal Sarma M. N
Algorithmic tools for graphs of small treewidth are used to address questions in complexity theory. For both arithmetic and Boolean circuits, it is shown that any circuit of size $…