NDLI: Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Content Provider	IEEE Xplore Digital Library
Author	Siu Man Chan Lauria, M. Nordstrom, J. Vinyals, M.
Copyright Year	2015
Description	Author affiliation: Dept. of Comput. Sci., Univ. of Toronto, Toronto, ON, Canada (Siu Man Chan) \|\| Sch. of Comput. Sci. & Commun., KTH R. Inst. of Technol., Stockholm, Sweden (Lauria, M.; Nordstrom, J.; Vinyals, M.)
Abstract	We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond -- Tompa and Raz -- McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant. We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this. We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.
Starting Page	466
Ending Page	485
File Size	297278
Page Count	20
File Format	PDF
ISBN	9781467381918
ISSN	02725428
DOI	10.1109/FOCS.2015.36
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-10-17
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Games Standards Approximation methods Complexity theory Additives Computer science Polynomials resolution depth pebbling reversible pebbling Dymond-Tompa game Raz-Mc Kenzie game PSPACE-complete separation PSPACE-hardness of approximation
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Just a Pebble Game

On the Relative Strength of Pebbling and Resolution

Parallel Repetition from Fortification

Black-white pebbling is pspace-complete (2007).

Black-White Pebbling is PSPACE-Complete (2007)

Narrow proofs may be spacious: separating space and width in resolution

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Similar Documents

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

Just a Pebble Game

On the Relative Strength of Pebbling and Resolution

Parallel Repetition from Fortification

Black-white pebbling is pspace-complete (2007).

Black-White Pebbling is PSPACE-Complete (2007)

Narrow proofs may be spacious: separating space and width in resolution

Hardness of Approximation in PSPACE and Separation Results for Pebble Games