English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Pebble games are single-player games on DAGs involving placing and movingpebbles on nodes of the graph according to a certain set of rules. The goal isto pebble a set of target nodes using a minimum number of pebbles. In thispaper, we present a possibly simpler proof of the result in [CLNV15] andstrengthen the result to show that it is PSPACE-hard to determine the minimumnumber of pebbles to an additive $n^{1/3-\epsilon}$ term for all $\epsilon >0$, which improves upon the currently known additive constant hardness ofapproximation [CLNV15] in the standard pebble game. We also introduce a familyof explicit, constant indegree graphs with $n$ nodes where there exists a graphin the family such that using constant $k$ pebbles requires $\Omega(n^k)$ movesto pebble in both the standard and black-white pebble games. This independentlyanswers an open question summarized in [Nor15] of whether a family of DAGsexists that meets the upper bound of $O(n^k)$ moves using constant $k$ pebbleswith a different construction than that presented in [AdRNV17].

Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs