Bounded Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions.

Svyatoslav Gryaznov Navid Talebanfard

Published in: CoRR (2024)

Keyphrases

lower bound
upper bound
randomized algorithms
branch and bound algorithm
depth information
objective function
systematic errors
random instances
np hard
randomly generated
complex valued
upper and lower bounds
depth map
lower and upper bounds
optimal solution
max sat
vc dimension
randomized algorithm
search space