Circuit complexity of shuffle

DOI10.1007/978-3-642-45278-9_34zbMATH Open1408.68081OpenAlexW2287320187MaRDI QIDQ2870045FDOQ2870045

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

Recommendations

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

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)

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)