Skip to main content.
Advanced search >
<< Back to previous page Print

<< Thursday, May 16, 2013 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


[Dissertation Talk] Pebble Games and Complexity

Seminar: Departmental | May 16 | 10-11 a.m. | 373 Soda Hall


Siu Man Chan, UC Berkeley

Electrical Engineering and Computer Sciences (EECS)


We study the connection between pebble games and complexity.

First, we derive complexity results using pebble games.
It is shown that three pebble games used for studying computational complexity are equivalent: namely, the two-person pebble game of Dymond–Tompa, the two-person pebble game of Raz–McKenzie, and the one-person reversible pebble game of Bennett have the same pebble costs over any directed acyclic graph.
The three pebble games have been used for studying parallel complexity and for proving lower bounds under restricted settings, and we show one more such lower bound on circuit-depth.

Second, the pebble costs are applied to proof complexity.
Concerning a family of unsatisfiable CNFs called pebbling contradictions, the pebble cost in any of the pebble games controls the scaling of some parameters of resolution refutations.
Namely, the pebble cost controls the minimum depth of resolution refutations and the minimum size of tree-like resolution refutations.

Finally, we study the space complexity of computing the pebble costs and of computing the minimum depth of resolution refutations.
It is PSPACE-complete to compute the pebble cost in any of the three pebble games, and to compute the minimum depth of resolution refutations.


siuman@cs.berkeley.edu, 510-529-8647