In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees – decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of ... more >>>

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity ... more >>>

In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,1\}$, and $A = Mx+b$ for $M \in \mathbb{F}_2^{n \times n}$ and $b \in \mathbb{F}_2^n$, the result of the ... more >>>

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>>

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for $pd(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudlak, ... more >>>

The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble game number of any DAG is the same as its Dymond-Tompa pebble number and ... more >>>

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>>

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove
super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al.(2011). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this ... more >>>

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