SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE.

Ruta Jawale Yael Tauman Kalai Dakshita Khurana Rachel Yun Zhang

Published in: STOC (2021)

Keyphrases

computational complexity
depth map
np hard
database
artificial intelligence
knowledge base
decision trees
query language
upper bound
learning theory
depth information
continuous functions
np hardness