Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Balagopal Komarath:

TR16-067 | 20th April 2016
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani

Pebbling Meets Coloring : Reversible Pebble Game On Trees

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

TR15-035 | 22nd February 2015
Sunil K S, Balagopal Komarath, Jayalal Sarma

Comparator Circuits over Finite Bounded Posets

Revisions: 1

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

TR13-006 | 8th January 2013
Balagopal Komarath, Jayalal Sarma

Pebbling, Entropy and Branching Program Size Lower Bounds

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

ISSN 1433-8092 | Imprint