Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Juntas

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 1 , Jul 21, 2003
    • 0 Attachment
      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.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 7/21/2003 05:43:23 PM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.