Query complexity of matroids

DOI10.1007/978-3-642-38233-8_25MaRDI QIDQ4924658zbMATH OpenOpenAlexFDO

Authors Raghav Kulkarni, Miklos Santha

Publication date 7 June 2013

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-38233-8_25

zbMATH Keywords

(parity, randomized, quantum) decision tree complexityFourier spectrummatroidsread-once formulae

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 5888307
• Independence and port oracles for matroids, with an application to computational learning theory
• On the number of matroids
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• On the number of matroids

Cited in

(5)

• Alternation, sparsity and sensitivity: bounds and exponential gaps
• scientific article; zbMATH DE number 5888307 (Why is no real title available?)
• On the Complexity of Matroid Isomorphism Problems
• Matroid Complexity and Nonsuccinct Descriptions
• Quantum and classical query complexities for determining connectedness of matroids

This page was built for publication: Query complexity of matroids

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