Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kshitij Gajjar:

TR22-031 | 16th February 2022
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Transparency Beyond VNP in the Monotone Setting

Revisions: 4

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

TR21-114 | 29th July 2021
Henning Fernau, Kshitij Gajjar

The Space Complexity of Sum Labelling

Revisions: 1

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

ISSN 1433-8092 | Imprint