Abstract. Informally, an obfuscator O is an (ecient, probabilistic) \\compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is \\unintel-ligible " in some sense. Obfuscators, if they exist, would have a wide vari-ety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice’s theorem. Most of these applications are based on an interpretation of the \\unintelligibility " condition in obfuscation as mean-ing that O(P) is a \\virtual black box, " in the sense that anything one can eciently compute given O(P), one could also eciently compute given oracle access to P. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above in-tuition, obfuscation is impossible. We prove this by constructing a family of functions F that are inherently unobfuscatable in the following sense:

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a $(\frac{1}{2}+o(1)){n \choose 2} $ upper bound and a nearly matching $0.32{n \choose 2}$ lower bound for the minimum possible number of queries. In contrast, if we allow randomness, then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0.32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

We investigate two problems concerning the complexity of evaluating a function f on k distinct inputs by k parallel decision-tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best depth-d decision tree is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth-d algorithms are all correct is at most p k , which is the trivial lower bound. We show that if we replace the restriction to depth d by "expected depth d," then this result need not hold. In the help-bits problem, before the decision-tree computations begin, up to k-1 arbitrary binary questions (help-bit queries) can be asked about the k-tuple of inputs. In the second stage, for each possible (k-1)-tuple of answers to the help-bit queries, there is a k-tuple of decision trees where the ith tree is supposed to correctly compute the value of the function on the ith input, for any input that is consistent with the help bits. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg s (f), which is the minimum degree of a multivariate polynomial whose sign is equal to f.

We prove that the Berman-Hartmanis isomorphism conjecturers true under ACO reductions.More generafly, we show three theorems that hold for any comdexitv class C closed under (uniform) TCO-commtable man~-one" reductions.Isomorp'hism:The sets c~mplete for Cunder ACO reductions are afl isomorphic under isomorphisms computable and invertible by ACO circuits of depth three.Ga : p The sets that are complete for C under ACO and NC reducibility coincide.Stop Gap: The sets that are complete for C under ACO[mod 2] and ACO reducibility do not coincide.(These theorems hold both in the non-uniform and P-uniform settings.) To prove the second theorem for P-uniform settings, we show how to derandomize a version of the switching lemma, which may be of independent interest.(We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.)

We study a new problem—the wakeup problem—that seems to be fundamental in distributed computing. We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader-election problem, and other related problems. The main question we try to answer is “How much memory is needed to solve the wakeup problem?” We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

We investigate two problems concerning the complexity of evaluating a function f at k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best decision tree algorithm of depth d is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth d algorithms are all correct is at most p/sup k/, which is the trivial lower bound. We show that if we replace the depth d restriction by "expected depth d", then this result fails. In the help-bit problem, we are permitted to ask k-1 arbitrary binary questions about the k-tuple of inputs. For each possible k-1-tuple of answers to these queries we will have a k-tuple of decision trees which are supposed to correctly compute all functions on k-tuples that are consistent with the particular answers. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg/sup s/(f) which is the minimum degree of a multivariate polynomial whose sign is equal to f. Finally, we give a brief discussion of these problems in the context of other complexity models.>

We present new results, both positive and negative, on the well-studied problem of learning disjunctive normal form (DNF) expressions.We first prove that an algorithm due to Kushilevitz and Mansour ysis of a finite class of boolean functions 011 the hypercube.1

Article Natural proofs Share on Authors: Alexander A. Razborov School of Mathematics, Institute for Advanced Study Princeton, NJ and Steklov Mathematical Institute Vavilova 42, 117966, GSP-1 Moscow, Russia School of Mathematics, Institute for Advanced Study Princeton, NJ and Steklov Mathematical Institute Vavilova 42, 117966, GSP-1 Moscow, RussiaView Profile , Steven Rudich Computer Science Department, Carnegie Mellon University, Pittsburgh, PA Computer Science Department, Carnegie Mellon University, Pittsburgh, PAView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 204–213https://doi.org/10.1145/195058.195134Online:23 May 1994Publication History 49citation861DownloadsMetricsTotal Citations49Total Downloads861Last 12 Months21Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Define the MOD~-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all O-1 assignments 5, F(o?) = O iff P(~= O.We obtain the unexpected result that the MOD,r,-degree of the OR of N variables is 0(~), where r is the number of distinct prime factors of m.This is optimal in the case of representation by symmetric polynomials.The MOD,, function is O if the number of input ones is a multiple of n and is 1 otherwise.We show that the MOD~-degree of both the MOD. and lMODn functions is N$)(l) exactly when there is a prime dividing n but not m.The MOD~-degree of the MOD~function is 1;we show that the MODrn,-degree of lMODm is NtiflJ if m is not a power of a prime, O(1) otherwise.A corollary is that there exists an oracle relative to which the MODm P classes (such as @P) have this structure: MODm P is closed under complement and union iff m is a prime power, and MOD.P is a subset of MODmP iff all primes dividing n also divide m.

This paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term DNF formulas in time O(n•2o(k)), where n is the number of input variables. This improves upon previous O(nk) bounds and allows one to learn DNF of O(log n) terms in polynomial time. We present the algorithm in its most natural form as a randomized algorithm, and then show how recent derandomization techniques can be used to make it deterministic. The algorithm is an exact learning algorithm, but one where the equivalance query hypotheses and the final output are general (not necessarily k-term) DNF formulas.

How to represent a graph in memory is a fundamental data structuring question. In the usual representations of an n-vertex graph, the names of the vertices (i.e., integers from 1 to n) betray nothing about the graph itself. Indeed, the names (or labels) on the n vertices are just $\log n$ bit place holders to allow data on the edges to encode the structure of the graph. In this scenario, there is no such waste. By assigning $O(\log n)$ bit labels to the vertices, the structure of the graph is completely encoded, so that, given the labels of two vertices, one can test if they are adjacent in time linear in the size of the labels. Furthermore, given an arbitrary original labeling of the vertices, structure coding labels are found (as above) that are no more than a small constant factor larger than the original labels. These notions are intimately related to vertex-induced universal graphs of polynomial size. For example, planar graphs can be labeled with structure coding labels of size $ < 4\log n$, which implies the existence of a graph with $n^4 $ vertices that contains all n-vertex planar graphs as vertex-induced subgraphs. The theorems on finite graphs extend to a theorem about the constrained labeling of infinite graphs.

M. Karchmer et al. (1991) considered the circuit depth complexity of n-bit Boolean function constructed by composing up to d=log n/log log n levels of k=log-n-bit Boolean functions. Any such function is in AC/sup 1/. They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires dk in Omega (log/sup 2/ n/log log n) depth. This would separate AC/sup 1/ from NC/sup 1/. They recommend using the communication game characterization of circuit depth. They suggest an intermediate problem which they call the universal composition relation. An almost optimal lower bound of dk-O(d/sup 2/(k log k)/sup 1/2/) is given for this problem. In addition, a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega (k) circuit depth is presented.>

We consider the problem of approximating a Boolean function f : f0; 1g n ! f0; 1g by the sign of an integer polynomial p of degree k. For us, a polynomial p(x) predicts the value of f(x) if, whenever p(x) 0, f(x) = 1, and whenever p(x) ! 0, f(x) = 0. A low-degree polynomial p is a good approximator for f if it predicts f at almost all points. Given a positive integer k, and a Boolean function f , we ask, "how good is the best degree k approximation to f?" We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the case f is parity. Minsky and Papert [10] proved that a perceptron can not compute parity; our bounds indicate exactly how well Yale University, Dept. of Computer Science, P.O. Box 208285, New Haven CT 06520-8285. y Email: [email protected]. z Email: [email protected]. Supported in part by NSF grants CCR-8808949 and CCR-8958528. x Carnegie-Mellon University, Schoo...

We study a new problem, the wakeup problem, that seems to be very fundamental in distributed computing.We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader election problem, and other related problems.The main question we try to answer is, how much memory is needed to solve the wakeup problem?We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

This paper structurally characterizes the complexity of ranking. A set A is (strongly) P-rankable if there is a polynomial time computable function f so that for all x, f(x) computes the number of elements of A that are lexicographically ⩽ x, i.e., the rank of x with respect to A. This is the strongest of three notions of P-ranking we consider in this paper. We say a class C is P-rankable if all sets in C are P-rankable. Our main results show that with the same certainty with which we believe counting to be complex, and thus with at least the certainty with which we believe P ≠ NP, P has no uniform, strong, weak, or enumerative ranking functions. We show that: • P and NP are equally likely to be P-rankable, i.e., P is P-rankable if and only if NP is P-rankable. • P is P-rankable if and only if P = P#P. This extends work of Blum, Goldberg, and Sipser. • Even the two weaker notions of P-ranking that we study are hard if P ≠ P#P. •If P has small ranking circuits, then it has small ranking circuits of relatively low complexity. • If P has small ranking circuits then counting is in the polynomial hierarchy, i.e., P#P ⊆Σ2p = PH. • P/poly has small ranking circuits if and only if P#P/poly = P#P/poly = P/poly. • If P is P-rankable, then P/poly has small ranking circuits. This links the ranking complexity of uniform and nonuniform classes. • The ranks of some strings in easy sets are of high relative time-bounded Kolmogorov complexity unless P = P#P. It follows that even a type of approximate ranking, enumerative ranking, is hard unless P = P#P. • The complexity of generating “the next largest” element in a set has clear structural characterizations. In particular, (1) we can efficiently find some element of polynomial hierarchy sets at an input length if and only if P = PH ∩ P/poly, and (2) we can efficiently find some element of a polynomial hierarchy set greater than an input if and only if all sets in NP have infinite P-printable subsets.

We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if P = N P, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving P ≠ N P. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Our results present a general framework for proving statements of the form, “Cryptographic application X is not likely possible based solely on complexity assumption Y.”

How to represent a graph in memory is a fundamental data structuring question. In the usual representations of an n-node graph, the names of the nodes (i.e. integers from 1 to n) betray nothing about the graph itself. Indeed, the names (or labels) on the n nodes are just logn bit place holders to allow data on the edges to code for the structure of the graph. In our scenario, there is no such waste. By assigning Ο(logn) bit labels to the nodes, we completely code for the structure of the graph, so that given the labels of two nodes we can test if they are adjacent in time linear in the size of the labels. Furthermore, given an arbitrary original labeling of the nodes, we can find structure coding labels (as above) that are no more than a small constant factor larger than the original labels. These notions are intimately related to vertex induced universal graphs of polynomial size. For example, we can label planar graphs with structure coding labels of size < 4logn. This implies the existence of a graph with n4 nodes that contains all n-node planar graphs as vertex induced subgraphs (It was not previously known that this class had polynomial sized universal graphs). The theorems on finite graphs extend to a theorem about the constrained labeling of infinite graphs.

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f : {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f : {0,1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.