An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of ... more >>>

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 $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>

The rigidity of a matrix A for target rank r is the minimum number of entries
of A that must be changed to ensure that the rank of the altered matrix is at
most r. Since its introduction by Valiant (1977), rigidity and similar
rank-robustness functions of matrices have found ... more >>>

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound
$k$, we want to decide whether the rank of $M$ can be brought down to
below $r$ by changing at most $k$ entries of $M$. This is a decision
version of the well-studied notion of ... more >>>

We re-examine the complexity of evaluating monotone planar circuits
MPCVP, with special attention to circuits with cylindrical
embeddings. MPCVP is known to be in NC^3, and for the special
case of upward stratified circuits, it is known to be in
LogDCFL. We characterize cylindricality, which is ... more >>>