Circuit complexity of shuffle

DOI10.1007/978-3-642-45278-9_34MaRDI QIDQ2870045zbMATH OpenOpenAlexFDO

Authors Michael Soltys

Publication date 17 January 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45278-9_34

zbMATH Keywords

lower boundscircuit complexitystring shuffle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• String shuffle: circuits and graphs
• Unshuffling a square is NP-hard
• Shuffle languages are in P

Cited in

(8)

• On the complexity of iterated shuffle
• Finding shuffle words that represent optimal scheduling of shared memory access
• String shuffle: circuits and graphs
• Unshuffling permutations: trivial bijections and compositions
• A constant time string shuffle algorithm on reconfigurable meshes
• Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
• Unshuffling a square is NP-hard
• Finding shuffle words that represent optimal scheduling of shared memory access

This page was built for publication: Circuit complexity of shuffle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870045)