New lower bounds for Massively Parallel Computation from query complexity.
Moses CharikarWeiyun MaLi-Yang TanPublished in: CoRR (2020)
Keyphrases
- massively parallel
- query complexity
- lower bound
- concept class
- vc dimension
- parallel computing
- upper bound
- fine grained
- equivalence queries
- membership queries
- exact learning
- data complexity
- learning theory
- parallel machines
- lower and upper bounds
- objective function
- sample complexity
- sample size
- concept classes
- target concept
- uniform distribution
- dnf formulas