New lower bounds for Polynomial Calculus over non-Boolean bases.
Yogesh DahiyaMeena MahajanSasank MouliPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- lower bound
- upper bound
- average case complexity
- branch and bound algorithm
- real valued
- branch and bound
- objective function
- boolean functions
- upper and lower bounds
- optimal solution
- lower and upper bounds
- vc dimension
- sample complexity
- worst case
- np hard
- lower bounding
- basis functions
- max sat
- statistical queries
- logic programs
- average case
- polynomial size
- threshold functions
- search algorithm
- set of randomly generated instances