ML Anthology

The Backdoor Key: A Path to Understanding Problem Hardness

Yongshao Ruan, Henry A. Kautz, Eric Horvitz
AAAI 2004 pp. 124-130
/aaai/2004/ruan2004aaai-backdoor/

Abstract

We introduce our work on the backdoor key, a concept that shows promise for characterizing problem hardness in back-tracking search algorithms. The general notion of backdoors was recently introduced to explain the source of heavy-tailed behaviors in backtracking algorithms (Williams, Gomes, & Selman 2003a; 2003b). We describe empirical studies that show that the key faction, i.e., the ratio of the key size to the corresponding backdoor size, is a good predictor of problem hardness of ensembles and individual instances within an en-semble for structure domains with large key fraction.

PDF AAAI Semantic Scholar

Cite

Text

Ruan et al. "The Backdoor Key: A Path to Understanding Problem Hardness." AAAI Conference on Artificial Intelligence, 2004.

Markdown

[Ruan et al. "The Backdoor Key: A Path to Understanding Problem Hardness." AAAI Conference on Artificial Intelligence, 2004.](https://mlanthology.org/aaai/2004/ruan2004aaai-backdoor/)

BibTeX

@inproceedings{ruan2004aaai-backdoor,
  title     = {{The Backdoor Key: A Path to Understanding Problem Hardness}},
  author    = {Ruan, Yongshao and Kautz, Henry A. and Horvitz, Eric},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2004},
  pages     = {124-130},
  url       = {https://mlanthology.org/aaai/2004/ruan2004aaai-backdoor/}
}