On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant.
Hervé FournierSylvain PerifelRémi de Joannis de VerclosPublished in: Inf. Comput. (2015)
Keyphrases
- polynomial size
- lower bound
- boolean functions
- random instances
- dnf formulas
- upper bound
- exponential size
- learning theory
- concept class
- uniform distribution
- upper and lower bounds
- branch and bound algorithm
- branch and bound
- optimal solution
- lower and upper bounds
- np hard
- objective function
- pac learning
- concept classes
- vc dimension
- sample complexity
- knowledge compilation
- bounded treewidth
- randomly generated
- membership queries
- max sat