Improved lower bounds on the randomized complexity of graph properties

DOI10.1002/RSA.20164MaRDI QIDQ3437025zbMATH OpenOpenAlexFDO

Authors Amit Chakrabarti, Subhash Khot

Publication date 11 May 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20164

zbMATH Keywords

decision treesgraph packingprobabilistic methodrandomized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1754599
• Lower bounds to randomized algorithms for graph properties
• An improved lower bound on the sensitivity complexity of graph properties
• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
• scientific article; zbMATH DE number 168429
• scientific article; zbMATH DE number 1775407
• Improved lower bounds for graph embedding problems
• On a certain complexity estimate in graph theory
• A lower bound for the complexity of monotone graph properties

Cited in

(7)

• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• scientific article; zbMATH DE number 168429 (Why is no real title available?)
• scientific article; zbMATH DE number 2019628 (Why is no real title available?)
• scientific article; zbMATH DE number 1754599 (Why is no real title available?)
• A lower bound for the complexity of monotone graph properties
• Decision tree complexity versus block sensitivity and degree
• Lower bounds to randomized algorithms for graph properties

This page was built for publication: Improved lower bounds on the randomized complexity of graph properties

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