Pebbling, Entropy, and Branching Program Size Lower Bounds

DOI10.1145/2751320zbMath1347.68170arXiv1301.1425OpenAlexW2118961951MaRDI QIDQ2828231

Balagopal Komarath, M. N. Jayalal Sarma

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.1425

zbMATH Keywords

entropylower boundsbranching programspebbling games

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Pebbling, Entropy, and Branching Program Size Lower Bounds