A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates.

Ivan Mihajlin Anastasia Sofronova

Published in: CCC (2022)

Keyphrases

lower bound
upper bound
branch and bound algorithm
worst case
np hard
branch and bound
lower and upper bounds
objective function
depth map
depth information
lower bounding
upper and lower bounds
optimal solution
expressive power
mathematical formulas