Path Puzzles: Discrete Tomography with a Path Constraint is Hard

Autor: Jeffrey Bosboom, Erik D. Demaine, Justin Kopinsky, Adam Hesterberg, Roderick Kimball, Martin L. Demaine

Publikováno v: Springer Japan

We prove that path puzzles with complete row and column information--or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint--are strongly NP-complete, ASP-complete, and #P-complete. Along the way, we newly establish ASP-comp

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8838eec1405ea6a6d5cf1ae3f4605982
https://doi.org/10.1007/s00373-019-02092-5

Infinite All-Layers Simple Foldability

Autor: Hugo A. Akitaya, Erik D. Demaine, Joseph Bergeron, Cordelia Avery, Justin Kopinsky, Jason S. Ku

Publikováno v: Springer Japan

We study the problem of deciding whether a crease pattern can be folded by simple folds (folding along one line at a time) under the infinite all-layers model introduced by Akitaya et al. (J Inform Process 25:582–589, 2017), in which each simple fo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a2bdb67dade6f348ef19942da92b7065

Inherent limitations of hybrid transactional memory

Autor: Srivatsan Ravi, Petr Kuznetsov, Nir Shavit, Dan Alistarh, Justin Kopinsky

Publikováno v: Distributed Computing
Distributed Computing, Springer Verlag, 2018, 31 (3), pp.167-185. ⟨10.1007/s00446-017-0305-3⟩
Lecture Notes in Computer Science ISBN: 9783662486528
DISC
DISC 2015
DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_13⟩
Springer Berlin Heidelberg

Several hybrid transactional memory (HyTM) schemes have recently been proposed to complement the fast, but best-effort nature of hardware transactional memory with a slow, reliable software backup. However, the costs of providing concurrency between

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::49240df91c2729d9085c01b12b934fa8
https://hal.telecom-paris.fr/hal-02364297

Distributionally Linearizable Data Structures

Autor: Dan Alistarh, Justin Kopinsky, Giorgi Nadiradze, Trevor Brown, Jerry Li

Publikováno v: SPAA
Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures

Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications. Despite considerable interest, there exist families of natural, high performing randomized relaxed co

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aacdaab92ea20c62ff335d3ce7ad4506

The SprayList: a scalable relaxed priority queue

Autor: Dan Alistarh, Jerry Li, Nir Shavit, Justin Kopinsky

Publikováno v: PPOPP
MIT web domain

High-performance concurrent priority queues are essential for applications such as task scheduling and discrete event simulation. Unfortunately, even the best performing implementations do not scale past a number of threads in the single digits. This

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bd72f999560755a30605b1cdf85c2ed3
https://doi.org/10.1145/2688500.2688523