Quantum and classical query complexities for determining connectedness of matroids

DOI10.1016/J.JCSS.2026.103758MaRDI QIDQ6859726zbMATH OpenFDO

Authors Xiaowei Huang, Shiguang Feng, Lvzhou Li

Publication date 11 February 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103758

zbMATH Keywords

connectivitymatroidquantum computingquery complexity

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites work

• An extremal problem for non-separable matroids
• Complexity measures and decision tree complexity: a survey.
• Complexity of Matroid Property Algorithms
• Connectivity in Matroids
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3861184 (Why is no real title available?)
• scientific article; zbMATH DE number 3719168 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Matroid Intersection
• Matroid intersection algorithms
• Matroids and the greedy algorithm
• ON MATROID CONNECTIVITY
• On matroid connectivity
• On some extremal connectivity results for graphs and matroids
• On the abstract properties of linear dependence.
• On the connectivity function of a matroid
• Partial matroid representations
• Quantum algorithms for learning hidden strings with applications to matroid problems
• Quantum Algorithms for Matching and Network Flows
• Quantum computation and quantum information. 10th anniversary edition
• Quantum lower bounds by polynomials
• Quantum Query Complexity of Some Graph Problems
• Query complexity of matroids
• Temporally unstructured quantum computation
• The dependence graph for bases in matroids

This page was built for publication: Quantum and classical query complexities for determining connectedness of matroids

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