We study the problem of obtaining deterministic black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an deterministic white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg^2 S), this is analogous (in the terminology of boolean pseudorandomness) to a seed-length of lg^2 S, which is the seed length of the pseudorandom generators of Nisan and Impagliazzo-Nisan-Wigderson for read-once oblivious boolean branching programs. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg^2 S lglg S), corresponding to a seed length of lg^2 S lglg S. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounded width, where no pseudorandom generator (or hitting set) with seed length o(lg^2 S) is known. In follow up work, we strengthened a result of Mulmuley, and showed that derandomizing a particular case of the Noether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using the results of the present work, this gives a derandomization of Noether Normalization in that case, which Mulmuley conjectured would difficult due to its relations to problems in algebraic geometry. We also show that several other circuit classes can be black-box reduced to read-once oblivious ABPs, including set-multilinear ABPs (a generalization of depth-3 set-multilinear formulas), non-commutative ABPs (generalizing non-commutative formulas), and (semi-)diagonal depth-4 circuits (as introduced by Saxena).
This work fits into the research program of derandomizing PIT, in particular derandomizing black-box PIT. However, for many of the models of algebraic circuits studied, there are corresponding boolean circuit models for which derandomization questions can also be asked. In particular, for a class @math of boolean circuits, we can seek to construct a @math for @math , such that for any circuit @math on @math inputs, we have the @math -closeness of distributions @math , where @math denotes the uniform distribution on @math . Nisan @cite_15 studied pseudorandom generators for space-bounded computation, and for space @math computation gave a generator with seed length @math . Impagliazzo, Nisan and Wigderson @cite_5 later gave a different construction with the same seed length. Randomized space-bounded computation can be modeled with read-once oblivious (boolean) branching programs, and these generators apply to this model of computation as well.
@cite_5 @cite_15
2011438986 1982991092
We prove the existence of a polynomial time computable pseudorandom generator that @math -fools constant width regular read-once branching programs of length @math using a seed of length @math . The previous best pseudorandom generator for regular branching programs used a seed of length @math , and was due to Braverman et. al. and Brody and Verbin (FOCS 2010). Our pseudorandom generator is the INW generator due to Impagliazzo et. al. (STOC 1994). Our work shares some similarity with the recent work of Kouck ' y et. al. (STOC 2011)who get similar seed length for permutation branching programs. However, our work proceeds by analyzing the eigenvalues of the stochastic matrices that arise in the transitions of the branching program which arguably makes the technique more robust. As a corollary of our techniques, we present new results on the small biased spaces for group products'' problem by Meka and Zuckerman (RANDOM 2009). We get a pseudorandom generator with seed length @math . Previously, using the result of Kouck ' y et. al., it was possible to get a seed length of @math for this problem. The is the following problem: a coin is given, which lands on head with probability either @math or @math . We are given the outcome of @math independent tosses of this coin, and the goal is to guess which way the coin is biased, and to answer correctly with probability @math . When our computational model is unrestricted, the majority function is optimal, and succeeds when @math for a large enough constant @math . The coin problem is open and interesting in models that cannot compute the majority function. In this paper we study the coin problem in the model of . We prove that in order to succeed in this model, @math must be at least @math . For constant @math this is tight by considering the recursive tribes function, and for other values of @math this is nearly tight by considering other read-once AND-OR trees. We generalize this to a , where instead of independent tosses of a coin we are given independent tosses of one of two @math -sided dice. We prove that if the distributions are too close and the mass of each side of the dice is not too small, then the dice cannot be distinguished by small-width read-once branching programs. We suggest one application for this kind of theorems: we prove that Nisan's Generator fools width- @math read-once branching programs, using seed length @math . For @math , this seed length is @math . The coin theorem and its relatives might have other connections to PRGs. This application is related to the independent, but chronologically-earlier, work of Braver man, Rao, Raz and Yehudayoff BRRY . We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length O(log (n epsilon)) for error epsilon. Previously, only constructions with seed-length O( ^ 3 2 n) or O( ^2 n) were known for these classes with polynomially small error. The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces. We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time @math , where the input matrices have size n×n, the number of non-zero entries in the product matrix is at most s, ? is the exponent of the fast matrix multiplication and @math denotes O(f(n)log? d n) for some constant d. By the currently best bound on ?, its running time can be also expressed as @math . Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n 1.232 and it is never slower than the fast @math -time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form @math , where ?(p,q,t) is the exponent of the fast multiplication of an n p ×n q matrix by an n q ×n t matrix. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms. In [Proceedings of the Second Symposium on Switching Circuit Theory and Logical Design (FOCS), 1961, pp. 34-38], Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow parameters. Providing an algorithmic version of Chow's theorem—i.e., efficiently constructing a representation of a threshold function given its Chow parameters—has remained open ever since. This problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. In this paper we effectively solve the problem, giving a randomized polynomial-time approximation scheme with the following behavior: Given the Chow parameters of a Boolean threshold function @math over @math bits and any constant @math , the algorithm runs in time @math and with high probability outputs a representation of a threshold function @math which is @math -close to @math . Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include @math -time learning algorithms for threshold functions under the uniform distribution in the following models: (i) the restricted focus of attention model, answering an open question of ; (ii) an agnostic-type model. This contrasts with recent results of Guruswami and Raghavendra who show NP-hardness for the problem under general distributions; (iii) the PAC model, with constant @math . Our @math -time algorithm substantially improves on the previous best known running time and nearly matches the @math bits of training data that any successful learning algorithm must use. In this paper we study polynomial identity testing of sums of @math read-once algebraic branching programs ( @math -RO-ABPs), generalizing the work in (Shpilka and Volkovich 2008,2009), who considered sums of @math read-once formulas ( @math -RO-formulas). We show that @math -RO-ABPs are strictly more powerful than @math -RO-formulas, for any @math , where @math is the number of variables. We obtain the following results: 1) Given free access to the RO-ABPs in the sum, we get a deterministic algorithm that runs in time @math , where @math bounds the size of any largest RO-ABP given on the input. This implies we have a deterministic polynomial time algorithm for testing whether the sum of a constant number of RO-ABPs computes the zero polynomial. 2) Given black-box access to the RO-ABPs computing the individual polynomials in the sum, we get a deterministic algorithm that runs in time @math . 3) Finally, given only black-box access to the polynomial computed by the sum of the @math RO-ABPs, we obtain an @math time deterministic algorithm. We prove that for any decision tree calculating a boolean function @math , [ [f] i=1 ^n (f), ] where @math is the probability that the @math th input variable is read and @math is the influence of the @math th variable on @math . The variance, influence and probability are taken with respect to an arbitrary product measure on @math . It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced boolean function with a decision tree of depth @math has a variable with influence at least @math . The only previous nontrivial lower bound known was @math . Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with non-boolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least @math , where @math is the number of vertices and @math is the critical threshold probability. This supersedes the milestone @math bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson. In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits @math and @math of similar size, the obfuscations of @math and @math should be computationally indistinguishable. In functional encryption, ciphertexts encrypt inputs @math and keys are issued for circuits @math . Using the key @math to decrypt a ciphertext @math yields the value @math but does not reveal anything else about @math . Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: (1) We describe a candidate construction for indistinguishability obfuscation for @math circuits. The security of this construction is based on a new al... We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: @math Offline Hamming Nearest (and Furthest) Neighbors: Given @math red and @math blue points in @math -dimensional Hamming space for @math , we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time @math or deterministic time @math . These also lead to faster MAX-SAT algorithms for sparse CNFs. @math Offline Approximate Nearest (and Furthest) Neighbors: Given @math red and @math blue points in @math -dimensional @math or Euclidean space, we can find a @math -approximate nearest (or furthest) blue neighbor for each red point in randomized time near @math . @math SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for @math circuits with a subquadratic number of linear threshold gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic @math time. This also implies new circuit lower bounds for threshold circuits. We also give a randomized @math -time SAT algorithm for subexponential-size @math circuits, where the top @math gate and middle @math gates have @math fan-in. In this paper, we prove tight lower bounds on the smallest degree of a nonzero polynomial in the ideal generated by @math or @math in the polynomial ring @math , @math are coprime, which is called over @math . The immunity of @math is lower bounded by @math , which is achievable when @math is a multiple of @math ; the immunity of @math is exactly @math for every @math and @math . Our result improves the previous bound @math by Green. We observe how immunity over @math is related to @math circuit lower bound. For example, if the immunity of @math over @math is lower bounded by @math , and @math , then @math requires @math circuit of exponential size to compute. We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model, defined by El Gamal in [Open problems presented at the @math workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research, in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath, eds., Springer-Verlag, New York, 1987, pp. 60-62]. In this model there are @math processors @math , each of which is initially given a private input bit @math . The goal is for @math to learn the value of @math , for some specified function @math , using a series of noisy broadcasts. At each step a designated processor broadcasts one bit to all of the other processors, and the bit received by each processor is flipped with fixed probability (independently for each recipient). In 1988, Gallager [IEEE Trans. Inform. Theory, 34 (1988), pp. 176-180] gave a noise-resistant protocol that allows @math to learn the entire input with constant probability in @math broadcasts. We prove that Gallager's protocol is optimal, up to a constant factor. Our lower bound follows by reduction from a lower bound for generalized noisy decision trees, a new model which may be of independent interest. For this new model we show a lower bound of @math on the depth of a tree that learns the entire input. While the above lower bound is for an @math -bit function, we also show an @math lower bound for the number of broadcasts required to compute certain explicit boolean-valued functions, when the correct output must be attained with probability at least @math for a constant parameter @math (this bound applies to all threshold functions as well as any other boolean-valued function with linear sensitivity). This bound also follows by reduction from a lower bound of @math on the depth of generalized noisy decision trees that compute the same functions with the same error. We also show a (nontrivial) @math lower bound on the depth of generalized noisy decision trees that compute such functions with small constant error. Finally, we show the first protocol in the noisy broadcast model that computes the Hamming weight of the input using a linear number of broadcasts. We give a computationally efficient algorithm that learns (under distributional assumptions) a halfspace in the difficult agnostic framework of Kearns, Schapire, and Sellie [Mach. Learn., 17 (1994), pp. 115-141], where a learner is given access to a distribution on labelled examples but where the labelling may be arbitrary (similar to malicious noise). It constructs a hypothesis whose error rate on future examples is within an additive @math of the optimal halfspace, in time poly @math for any constant @math , for the uniform distribution over @math or unit sphere in @math as well as any log-concave distribution in @math . It also agnostically learns Boolean disjunctions in time @math with respect to any distribution. Our algorithm, which performs @math polynomial regression, is a natural noise-tolerant arbitrary-distribution generalization of the well-known “low-degree” Fourier algorithm of Linial, Mansour, and Nisan. We observe that significant improvements on the running time of our algorithm would yield the fastest known algorithm for learning parity with noise, a challenging open problem in computational learning theory. A function @math is @math -resilient if all its Fourier coefficients of degree at most @math are zero, i.e., @math is uncorrelated with all low-degree parities. We study the notion of @math @math of Boolean functions, where we say that @math is @math -approximately @math -resilient if @math is @math -close to a @math -valued @math -resilient function in @math distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class @math over the uniform distribution. Roughly speaking, if all functions in a class @math are far from being @math -resilient then @math can be learned agnostically in time @math and conversely, if @math contains a function close to being @math -resilient then agnostic learning of @math in the statistical query (SQ) framework of Kearns has complexity of at least @math . This characterization is based on the duality between @math approximation by degree- @math polynomials and approximate @math -resilience that we establish. In particular, it implies that @math approximation by low-degree polynomials, known to be sufficient for agnostic learning over product distributions, is in fact necessary. Focusing on monotone Boolean functions, we exhibit the existence of near-optimal @math -approximately @math -resilient monotone functions for all @math . Prior to our work, it was conceivable even that every monotone function is @math -far from any @math -resilient function. Furthermore, we construct simple, explicit monotone functions based on @math and @math that are close to highly resilient functions. Our constructions are based on a fairly general resilience analysis and amplification. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas. We construct an explicit polynomial @math , with coefficients in @math , such that the size of any syntactically multilinear arithmetic circuit computing @math is at least @math . The lower bound holds over any field. For an @math -variate degree– @math real polynomial @math , we prove that @math is determined up to an additive @math as long as @math is a @math -wise independent distribution over @math for @math . This gives a broad class of explicit pseudorandom generators against degree- @math boolean threshold functions, and answers an open question of (FOCS 2009). The analysis of linear threshold Boolean functions has recently attracted the attention of those interested in circuit complexity as well as of those interested in neural networks. Here a generalization of linear threshold functions is defined, namely, polynomial threshold functions, and its relation to the class of linear threshold functions is investigated.A Boolean function is polynomial threshold if it can be represented as a sign function of a polynomial that consists of a polynomial (in the number of variables) number of terms. The main result of this paper is showing that the class of polynomial threshold functions (which is called @math ) is strictly contained in the class of Boolean functions that can be computed by a depth 2, unbounded fan-in polynomial size circuit of linear threshold gates (which is called @math ).Harmonic analysis of Boolean functions is used to derive a necessary and sufficient condition for a function to be an S-threshold function for a given set S of monomials. This cond... This paper addresses the cornerstone family of in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the @math nodes can only send @math -bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in @math rounds, where @math is the diameter of the graph. The best known running time in terms of @math alone is @math , which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based @math -round algorithm, where @math is the maximal degree in the graph. On the way to obtaining the above, we show that in the model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in @math rounds. , where @math is the maximum degree. When @math , the bound improves to @math and holds also for @math -coloring. In addition, we deterministically construct a @math -spanner with @math edges in @math rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a @math -spanner with @math edges runs in @math rounds. It is shown that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs that use only three registers. This was previously known for Boolean formulas [D. A. Barrington, J. Comput. System Sci., 38 (1989), pp. 150–164], which are equivalent to algebraic formulas over the ring @math . For formulas over arbitrary rings, the result is an improvement over previous methods that require the number of registers to be logarithmic in the size of the formulas in order to obtain polynomial-length straight-line programs. Moreover, the straight-line programs that arise in these constructions have the property that they consist of statements whose actions on the registers are linear and bijective. A consequence of this is that the problem of determining the iterated product of @math matrices is complete (under P-projections) for algebraic @math . Also, when the ring is @math , the programs that arise in the c... An arithmetic read-once formula (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are + ,× and such that every input variable labels at most one leaf. In this paper we study the problems of giving deterministic identity testing and reconstruction algorithms for ROFs. Our main result is an @math time deterministic algorithm for checking whether a black box holding the sum of k n -variate ROFs computes the zero polynomial. In other words, we provide a hitting set of size @math for the sum of k ROFs. This result greatly improves [27] where an @math algorithm was given for the problem. Using our new results we obtain a deterministic reconstruction algorithms for read-once formulas that runs in time @math . In fact, our results also hold for the more general model of preprocessed read-once formulas that we define in this paper. In this model we are allowed to replace each variable x i with a polynomial T i (x i ). Our techniques are very close to the techniques in [27]. The main difference is that we obtain several tighter versions of the tools first used there. In particular we obtain a better version of the hardness of representation approach which was first used in [27]. This technique can be thought of as a very explicit way of transforming (mild) hardness of a very structured polynomial to an identity testing algorithm. Mulmuley [Mul12a] recently gave an explicit version of Noether’s Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In this work, we show this is not the case. That is, we improve Mulmuley’s reduction and correspondingly weaken the conjecture regarding PIT needed to give explicit Noether Normalization. We then observe that the weaker conjecture has recently been nearly settled by the authors ([FS12]), who gave quasipolynomial size hitting sets for the class of read-once oblivious algebraic branching programs (ROABPs). This gives the desired explicit Noether Normalization unconditionally, up to quasipolynomial factors. As a consequence of our proof we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also study the strength of conjectures that Mulmuley requires to obtain similar results as ours. We prove that his conjectures are stronger, in the sense that the computational model he needs PIT algorithms for is equivalent to the well-known algebraic branching program (ABP) model, which is provably stronger than the ROABP model. Finally, we consider the depth-3 diagonal circuit model as defined by Saxena [Sax08], as PIT algorithms for this model also have implications in Mulmuley’s work. Previous work (such as [ASS12] and [FS12]) have given quasipolynomial size hitting sets for this model. In this work, we give a much simpler construction of such hitting sets, using techniques of Shpilka and Volkovich [SV09].