Lower bounds for regular resolution over parities.
Klim EfremenkoMichal GarlíkDmitry ItsyksonPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- lower bound
- noise tolerant
- uniform distribution
- upper bound
- decision lists
- membership queries
- boolean functions
- attribute efficient learning
- pac learning
- concept class
- agnostic learning
- concept classes
- branch and bound
- vc dimension
- equivalence queries
- sample complexity
- worst case
- objective function
- noisy data
- np hard
- statistical queries
- decision trees
- machine learning
- regular languages
- linear programming relaxation
- lower and upper bounds
- learning dnf