Google Analytics

Monday, July 21, 2003

Juntas

Eldar Fischer gave a talk today on his paper on testing juntas. So what is a junta? According to the American Heritage Dictionary, a junta is a "A group of military officers ruling a country after seizing power", named after such groups in Central and South America in the 80's. In this paper a junta refers to a function that depends on a constant number of variables.

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.

No comments:

Post a Comment