Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Pebbling:
TR07-044 | 23rd April 2007
Philipp Hertel

Black-White Pebbling is PSPACE-Complete

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

TR08-026 | 28th February 2008
Jakob Nordström, Johan Hastad

Towards an Optimal Separation of Space and Length in Resolution

Most state-of-the-art satisfiability algorithms today are variants of
the DPLL procedure augmented with clause learning. The main bottleneck
for such algorithms, other than the obvious one of time, is the amount
of memory used. In the field of proof complexity, the resources of
time and memory correspond to the length ... more >>>

TR09-002 | 23rd November 2008
Eli Ben-Sasson, Jakob Nordström

Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... 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