Approximate degree lower bounds for oracle identification problems.

Mark Bun Nadezhda Voronova

Published in: CoRR (2023)

Keyphrases

lower bound
exact solution
upper bound
np complete
lower and upper bounds
database
databases
learning algorithm
computational complexity
combinatorial optimization
solving problems
upper and lower bounds
randomly generated problems