Lower bounds for monotone arithmetic circuits via communication complexity.

Arkadev Chattopadhyay Rajit Datta Partha Mukhopadhyay

Published in: STOC (2021)

Keyphrases

lower bound
upper bound
worst case
objective function
high speed
branch and bound
communication systems
complexity measures
average case complexity
neural network
branch and bound algorithm
np hard
lower and upper bounds
arithmetic operations
computational cost
quadratic assignment problem