Back when I was young (those 80's) we had a different name for a function that depends on a constant number of variables: NC0, a specification of NCk, functions computable in constant fan-in circuits of depth O(logk n). If k = 0 we have constant fan-in and constant depth, which means it depends on a constant number of variables.
Digression: NC stands for "Nick's Class" named by Steve Cook in honor of Nick Pippenger. Pippenger repaid the favor with the class SC but enough of that for now.
Juntas are just one example I'm seeing of a trend of new names and definitions of concepts defined years ago. Makes me feel old. Of course back then we likely studied concepts were thought were new but might not have been. Just part of the great circle of math.
Post a Comment