Improved lower bounds on the randomized complexity of graph properties

DOI10.1002/rsa.20164zbMath1115.05084MaRDI QIDQ3437025

Amit Chakrabarti, Subhash A. Khot

Publication date: 11 May 2007

Published in: Random Structures and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic method; decision trees; randomized algorithms; graph packing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item