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).
We also mention that in @cite_19 @cite_28 Jansen, Qiao and Sarma studied black-box PIT in various models related to algebraic branching programs. Essentially, all these models can be cast as a problem of obtaining black-box PIT for read-once oblivious branching programs where each variable appears on a small number of edges. Their result gives a hitting set of size (roughly) @math when @math is an upper bound on the number of edges that a variable can label and the ABP is of polynomial size. In comparison, our Theorem gives a hitting set of size @math and works for @math (as long as the size of the ABP is polynomial in @math ). Our techniques are very different from those of @cite_19 , which follows the proof technique of @cite_24 . The later paper @cite_28 use an algebraic analogue of the Impagliazzo-Nisan-Wigderson @cite_5 generator, as we do, but the details are different.
@cite_28 @cite_19 @cite_5 @cite_24
1562749094 2011438986 1571321110
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. 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]. 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. Using ideas from automata theory we design a new efficient (deterministic) identity test for the noncommutative polynomial identity testing problem (first introduced and studied in [RS05, BW05]). More precisely, given as input a noncommutative circuit C x1, ldrldrldr , xn computing a polynomial in F x1, ldrldrldr , xn of degree d with at most t monomials, where the variables xi are noncommuting, we give a deterministic polynomial identity test that checks if C equiv 0 and runs in time polynomial in d, n, |C|, and t. The same methods works in a black-box setting: given a noncommuting black-box polynomial f isin F x1, ldrldrldr , xn of degree d with t monomials we can, in fact, reconstruct the entire polynomial f in time polynomial in n, d and t. Indeed, we apply this idea to the reconstruction of black-box noncommuting algebraic branching programs (the ABPs considered by Nisan in [N91] and Raz-Shpilka in [RS05]). Assuming that the black-box model allows us to query the ABP for the output at any given gate then we can reconstruct an (equivalent) ABP in deterministic polynomial time. Finally, we turn to commutative identity testing and explore the complexity of the problem when the coefficients of the input polynomial come from an arbitrary finite commutative ring with unity whose elements are uniformly encoded as strings and the ring operations are given by an oracle. We show that several algorithmic results for polynomial identity testing over fields also hold when the coefficients come from such finite rings. We study the problem of polynomial identity testing (PIT) for depth 2 arithmetic circuits over matrix algebra. We show that identity testing of depth 3 (SPS) arithmetic circuits over a field F is polynomial time equivalent to identity testing of depth 2 (PS) arithmetic circuits over U2(F), the algebra of upper-triangular 2 2 matrices with entries from F. Such a connection is a bit surprising since we also show that, as computational models, PS circuits over U2(F) are strictly ‘weaker’ than SPS circuits over F. The equivalence further implies that PIT of SPS circuits reduces to PIT of width-2 commutative Algebraic Branching Programs(ABP). Further, we give a deterministic polynomial time identity testing algorithm for a PS circuit of size s over commutative algebras of dimension O(log s log log s) over F. Over commutative algebras of dimension poly(s), we show that identity testing of PS circuits is at least as hard as that of SPS circuits over F. We continue the study of noncommutative polynomial identity testing initiated by Raz and Shpilka and present efficient algorithms for the following problems in the noncommutative model: polynomial identity testing: The algorithm gets as an input an arithmetic circuit with the promise that the polynomial it computes has small degree (for instance, a circuit of logarithmic depth or an arithmetic formula) and determines whether or not the output of the circuit is identically zero (as a formal expression). Unlike the algorithm by Raz and Shpilka, our algorithm is black-box (but randomized with one-sided error) and evaluates the circuit over the ring of matrices. In addition, we present query complexity lower bounds for identity testing and explore the possibility of de-randomizing our algorithm. The analysis of our algorithm uses a noncommutative variant of the Schwartz-Zippel test. Minimizing algebraic branching programs: The algorithm gets as an input an algebraic branching program (ABP) and outputs a smallest equivalent ABP. The algorithm is based on Nisan's characterization of ABP complexity, and uses as a sub-routine an algorithm for computing linear dependencies amongst arithmetic formulas, a problem previously studied by the authors. par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degreeror bounded “width.” Specifically: We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor @math , unless @math . H stad [18] proved that the problem is approximable to within a factor @math in polynomial time, and that is hard to approximate to within a factor @math . Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well. We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor @math unless @math . The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of @math -approximate algorithms [20, 23, 9] We present a new PCP construction, based on applying parallel repetition to the inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor @math . The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B =2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor @math , unless P = NP . This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor @math unless P = NP [1]. An algorithm achieving factor @math is also known [21, 2, 30, 16 . We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following: 1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^ Omega(n) size. 2. Any multilinear depth three circuit computing IMM_ n,d (the iterated matrix multiplication polynomial formed by multiplying d, n * n symbolic matrices) has n^ Omega(d) size. IMM_ n,d can be easily computed by a poly(n,d) sized ROABP. 3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n,d) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^ Omega(d) . This improves upon the quasi-polynomial separation result by Raz and Yehudayoff [2009] between these two models. The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure used previously in Nisan [1991], Raz [2006,2009], Raz and Yehudayoff [2009], and Forbes and Shpilka [2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure used by Nisan and Wigderson [1997]. Our lower bounds hold over any field. We give a deterministic polynomial time algorithm for polynomial identity testing in the following two cases: 1. Non commutative arithmetic formulas: the algorithm gets as an input an arithmetic formula in the non-commuting variables x sub i ,...,x sub n and determines whether or not the output of the formula is identically 0 (as a formal expression). 2. Pure arithmetic circuits: the algorithm gets as an input a pure arithmetic circuit (as defined by N. Nisan and A. Wigderson (1996)) in the variables x sub i ,...,x sub n and determines whether or not the output of the circuit is identically 0 (as a formal expression). We also give a deterministic polynomial time identity testing algorithm for non commutative algebraic branching programs as defined by N. Nisan (1991). One application is a deterministic polynomial time identity testing for multilinear arithmetic circuits of depth 3. Finally, we observe an exponential lower bound for the size of pure arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known by N. Nisan and A. Wigderson (1996). 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. We show the existence of @math -nets of size @math for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane and “fat” triangular ranges and for point sets in @math and axis-parallel boxes; these are the first known nontrivial bounds for these range spaces. Our technique also yields improved bounds on the size of @math -nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of @math -nets of size @math for the dual range space of “fat” regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Bronnimann and Goodrich or of Even, Rawitz, and Shahar, we obtain improved approximation factors (computable in expected polynomial time by a randomized algorithm) for the hitting set or the set cover problems associated with the corresponding range spaces. 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 . The full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary @math of a set @math , as a function of @math . A weaker (but more widely-used) lower bound is @math , where equality holds iff @math is a subcube. In 2011, the first author obtained a sharp stability' version of the latter result, proving that if @math , then there exists a subcube @math such that @math . The weak' version of the edge isoperimetric inequality has the following well-known generalization for the @math -biased' measure @math on the discrete cube: if @math , or if @math and @math is monotone increasing, then @math . In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if @math , then there exists a subcube @math such that @math , where @math . This result is a central component in recent work of the authors proving sharp stability versions of a number of Erd o s-Ko-Rado type theorems in extremal combinatorics, including the seminal complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the full' edge isoperimetric inequality, one relying on the Kruskal-Katona theorem. Purpose – The purpose of this paper is to suggest an alternative to the widely used Times Cited criterion for analysing citation networks. The approach involves taking account of the natures of the papers that cite a given paper, so as to differentiate between papers that attract the same number of citations.Design methodology approach – ArticleRank is an algorithm that has been derived from Google's PageRank algorithm to measure the influence of journal articles. ArticleRank is applied to two datasets – a citation network based on an early paper on webometrics, and a self‐citation network based on the 19 most cited papers in the Journal of Documentation – using citation data taken from the Web of Knowledge database.Findings – ArticleRank values provide a different ranking of a set of papers from that provided by the corresponding Times Cited values, and overcomes the inability of the latter to differentiate between papers with the same numbers of citations. The difference in rankings between Times Cited ... 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... In our LICS 2004 paper we introduced an approach to the study of the local structure of finite algebras and relational structures that aims at applications in the Constraint Satisfaction Problem (CSP). This approach involves a graph associated with an algebra @math or a relational structure A, whose vertices are the elements of @math (or A), the edges represent subsets of @math such that the restriction of some term operation of @math is ‘good’ on the subset, that is, act as an operation of one of the 3 types: semilattice, majority, or affine. In this paper we significantly refine and advance this approach. In particular, we prove certain connectivity and rectangularity properties of relations over algebras related to components of the graph connected by semilattice and affine edges. We also prove a result similar to 2-decomposition of relations invariant under a majority operation, only here we do not impose any restrictions on the relation. These results allow us to give a new, somewhat more intuitive proof of the bounded width theorem: the CSP over algebra @math has bounded width if and only if @math does not contain affine edges. Actually, this result shows that bounded width implies width (2,3). We also consider algebras with edges from a restricted set of types. In particular, it can be proved that type restrictions are preserved under the standard algebraic constructions. Finally, we prove that algebras without semilattice edges have few subalgebras of powers, that is, the CSP over such algebras is also polynomial time. Given an undirected graph G = (V ,E ), the density of a subgraph on vertex set S is defined as @math , where E (S ) is the set of edges in the subgraph induced by nodes in S . Finding subgraphs of maximum density is a very well studied problem. One can also generalize this notion to directed graphs. For a directed graph one notion of density given by Kannan and Vinay [12] is as follows: given subsets S and T of vertices, the density of the subgraph is @math , where E (S ,T ) is the set of edges going from S to T . Without any size constraints, a subgraph of maximum density can be found in polynomial time. When we require the subgraph to have a specified size, the problem of finding a maximum density subgraph becomes NP -hard. In this paper we focus on developing fast polynomial time algorithms for several variations of dense subgraph problems for both directed and undirected graphs. When there is no size bound, we extend the flow based technique for obtaining a densest subgraph in directed graphs and also give a linear time 2-approximation algorithm for it. When a size lower bound is specified for both directed and undirected cases, we show that the problem is NP-complete and give fast algorithms to find subgraphs within a factor 2 of the optimum density. We also show that solving the densest subgraph problem with an upper bound on size is as hard as solving the problem with an exact size constraint, within a constant factor. In a document network such as a citation network of scientific documents, web-logs, etc., the content produced by authors exhibits their interest in certain topics. In addition some authors influence other authors' interests. In this work, we propose to model the influence of cited authors along with the interests of citing authors. Moreover, we hypothesize that apart from the citations present in documents, the context surrounding the citation mention provides extra topical information about the cited authors. However, associating terms in the context to the cited authors remains an open problem. We propose novel document generation schemes that incorporate the context while simultaneously modeling the interests of citing authors and influence of the cited authors. Our experiments show significant improvements over baseline models for various evaluation criteria such as link prediction between document and cited author, and quantitatively explaining unseen text. We study arithmetic proof systems @math and @math operating with arithmetic circuits and arithmetic formulas, respectively, and that prove polynomial identities over a field @math . We establish a series of structural theorems about these proof systems, the main one stating that @math proofs can be balanced: if a polynomial identity of syntactic degree @math and depth @math has a @math proof of size @math , then it also has a @math proof of size @math in which every circuit has depth @math . As a corollary, we obtain a quasi-polynomial simulation of @math by @math . Using these results we obtain the following: consider the identities @math where @math , and @math are @math square matrices and @math is a triangular matrix with $z_...