Improved lower bounds on the randomized complexity of graph properties

DOI10.1002/rsa.20164zbMath1115.05084OpenAlexW4254584188MaRDI 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 methoddecision treesrandomized algorithmsgraph packing

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item

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