Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.

Lijie Chen Zhenjian Lu Xin Lyu Igor Carboni Oliveira

Published in: ICALP (2021)

Keyphrases

linear functions
average case complexity
average case
piecewise linear
machine learning
objective function
lower bound
support vector
special case
boolean functions
graph databases