All reports by Author Kshitij Gajjar:

__
TR23-150
| 5th October 2023
__

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse#### Monotone Classes Beyond VNP

__
TR22-031
| 16th February 2022
__

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse#### Transparency Beyond VNP in the Monotone Setting

Revisions: 5

__
TR21-114
| 29th July 2021
__

Henning Fernau, Kshitij Gajjar#### The Space Complexity of Sum Labelling

Revisions: 1

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their ... more >>>

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be ... more >>>

Henning Fernau, Kshitij Gajjar

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider ... more >>>