Algorithmic Problems for Metrics on Permutation Groups

DOI10.1007/978-3-540-77566-9_12MaRDI QIDQ5448642zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Pushkar S. Joglekar

Publication date 7 March 2008

Published in SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77566-9_12

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Symbolic computation and algebraic computation (68W30)

Recommendations

• The complexity of the weight problem for permutation and matrix groups.
• Minimum bases for permutation groups: The greedy approximation
• On the subgroup distance problem.
• The complexity of the Weight Problem for permutation groups
• The distance of a permutation from a subgroup of S_n.

Cites work

• A sieve algorithm for the shortest lattice vector problem
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Hardness of approximating the minimum distance of a linear code
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• Metrics on permutations, a survey
• On the limits of nonapproximability of lattice problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(6)

• On the subgroup distance problem.
• Linear optimization over permutation groups
• The distance of a permutation from a subgroup of S_n.
• The complexity of the Weight Problem for permutation groups
• scientific article; zbMATH DE number 5240982 (Why is no real title available?)
• The complexity of the weight problem for permutation and matrix groups.

This page was built for publication: Algorithmic Problems for Metrics on Permutation Groups

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