All reports by Author Jayalal Sarma:

__
TR22-186
| 31st December 2022
__

Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma#### Power of Decision Trees with Monotone Queries

__
TR18-153
| 22nd August 2018
__

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma#### New Bounds for Energy Complexity of Boolean Functions

Revisions: 1

__
TR18-152
| 30th August 2018
__

Krishnamoorthy Dinesh, Jayalal Sarma#### Sensitivity, Affine Transforms and Quantum Communication Complexity

Revisions: 1

__
TR17-192
| 15th December 2017
__

Krishnamoorthy Dinesh, Jayalal Sarma#### Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps

Revisions: 1

__
TR16-076
| 27th April 2016
__

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma#### Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

__
TR16-067
| 20th April 2016
__

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani#### Pebbling Meets Coloring : Reversible Pebble Game On Trees

__
TR15-035
| 22nd February 2015
__

Sunil K S, Balagopal Komarath, Jayalal Sarma#### Comparator Circuits over Finite Bounded Posets

Revisions: 1

__
TR14-072
| 29th April 2014
__

Sajin Koroth, Jayalal Sarma#### Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

__
TR13-028
| 14th February 2013
__

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma#### Arithmetic Circuit Lower Bounds via MaxRank

__
TR13-006
| 8th January 2013
__

Balagopal Komarath, Jayalal Sarma#### Pebbling, Entropy and Branching Program Size Lower Bounds

__
TR10-084
| 14th May 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Identity Testing of Read-Once Algebraic Branching Programs

__
TR10-015
| 8th February 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

__
TR09-106
| 28th October 2009
__

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma#### Using Elimination Theory to construct Rigid Matrices

__
TR06-100
| 17th July 2006
__

Meena Mahajan, Jayalal Sarma#### On the Complexity of Rank and Rigidity

__
TR06-009
| 10th January 2006
__

Nutan Limaye, Meena Mahajan, Jayalal Sarma#### Evaluating Monotone Circuits on Cylinders, Planes and Tori

Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma

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

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

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

Krishnamoorthy Dinesh, Jayalal Sarma

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

Krishnamoorthy Dinesh, Jayalal Sarma

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

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

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

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani

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

Sunil K S, Balagopal Komarath, Jayalal Sarma

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

Sajin Koroth, Jayalal Sarma

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

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

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

Balagopal Komarath, Jayalal Sarma

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

Maurice Jansen, Youming Qiao, Jayalal Sarma

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

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

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

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

Meena Mahajan, Jayalal Sarma

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

Nutan Limaye, Meena Mahajan, Jayalal Sarma

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