On Fixed-Polynomial Size Circuit Lower Bounds for Uniform Polynomials in the Sense of Valiant.
Hervé FournierSylvain PerifelRémi de Joannis de VerclosPublished in: MFCS (2013)
Keyphrases
- polynomial size
- lower bound
- boolean functions
- dnf formulas
- concept class
- concept classes
- upper bound
- random instances
- exponential size
- learning theory
- uniform distribution
- branch and bound
- vc dimension
- randomly generated
- upper and lower bounds
- branch and bound algorithm
- bounded treewidth
- worst case
- membership queries
- lower and upper bounds
- np hard
- objective function
- sample complexity
- knowledge compilation
- optimal solution
- statistical queries
- pac learning
- inductive inference
- sample size
- computational complexity