Integer factoring is a curious number theory problem with wide applications in complexity and cryptography. The best known algorithm to factor a number n takes time, roughly, exp(2*log^{1/3}(n)*log^{2/3}(log(n))) (number field sieve, 1989). One basic idea used is to find two squares, possibly in a number field, that are congruent modulo n. Several variants of this idea have been utilized to get other factoring algorithms in the last century. In this work we intend to explore new ideas towards integer factoring. In particular, we adapt the AKS primality test (2004) ideas for integer factoring. In the motivating case of semiprimes n=pq, i.e. p

We present a single common tool to strictly subsume all known cases of polynomial time black box polynomial identity testing (PIT), that have been hitherto solved using diverse tools and techniques, over fields of zero or large characteristic. In particular, we show that polynomial (in the size of the circuit) time hitting-set generators for identity testing of the two seemingly different and well studied models---depth-3 circuits with bounded top fanin, and constant-depth constant-read multilinear formulas---can be constructed using one common algebraic-geometry theme: Jacobian captures algebraic independence. By exploiting the Jacobian, we design the first efficient hitting-set generators for broad generalizations of the above-mentioned models, namely, (a) depth-3 ($\Sigma \Pi \Sigma$) circuits with constant transcendence degree of the polynomials computed by the product gates (no bounded top fanin restriction), and (b) constant-depth constant-occur formulas (no multilinear restriction). Constant occur of a variable, as we define it, is a more general concept than constant read. Also, earlier work on the latter model assumed that the formula is multilinear. Thus, our work goes further beyond the related results obtained by Saxena and Seshadhri [STOC, ACM, New York, 2011, pp. 431--440], Saraf and Volkovich [STOC, ACM, New York, 2011, pp. 421--430], Anderson, van Melkebeek, and Volkovich, [IEEE Conference on Computational Complexity, IEEE, Piscataway, NJ, 2011, pp. 273--282], Beecken, Mittmann, and Saxena [ICALP, Springer, New York, 2011, pp. 134--148] and Grenet et al. [Proceedings of the 30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Schloss Dagstuhl--Liebniz--Zentrum für Informatik, Wadern, Germany, 2011, pp. 127--139] and brings them under one unifying technique. In addition, using the same Jacobian-based approach, we prove exponential lower bounds for the immanant (which includes permanent and determinant) on the same depth-3 and depth-4 models for which we give efficient PIT algorithms. Our results reinforce the intimate connection between identity testing and lower bounds by exhibiting a concrete mathematical tool---the Jacobian. The Jacobian is equally effective in solving both the problems on certain interesting and previously well-investigated (but not well understood) models of computation.

In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. Further, we apply our quantification to the following problem. If we know that the dimension of a distribution on the set of n-length strings is s in (0,1], can we extract out O(sn) pseudorandom bits out of the distribution? We show that to construct such extractor, one need at least Omega(log n) bits of pure randomness. However, it is still open to do the same using O(log n) random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic pseudorandom extractor for this source. By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches O(log n) input bits to produce n output bits such that output distribution has dimension s in (0,1], implies P=BPP.

A finite-state Markov chain M can be regarded as a linear transform operating on the set of probability distributions over its node set. The iterative applications of M to an initial probability distribution μ 0 will generate a trajectory of probability distributions. Thus, a set of initial distributions will induce a set of trajectories. It is an interesting and useful task to analyze the dynamics of M as defined by this set of trajectories. The novel idea here is to carry out this task in a symbolic framework. Specifically, we discretize the probability value space [0,1] into a finite set of intervals I = { I 1 , I 2 ,..., I m }. A concrete probability distribution μ over the node set {1, 2,..., n } of M is then symbolically represented as D , a tuple of intervals drawn from I where the i th component of D will be the interval in which μ( i ) falls. The set of discretized distributions D is a finite alphabet. Hence, the trajectory, generated by repeated applications of M to an initial distribution, will induce an infinite string over this alphabet. Given a set of initial distributions, the symbolic dynamics of M will then consist of a language of infinite strings L over the alphabet D . Our main goal is to verify whether L meets a specification given as a linear-time temporal logic formula φ. In our logic, an atomic proposition will assert that the current probability of a node falls in the interval I from I . If L is an ω-regular language, one can hope to solve our model-checking problem (whether L ⊧ φ?) using standard techniques. However, we show that, in general, this is not the case. Consequently, we develop the notion of an ϵ-approximation, based on the transient and long-term behaviors of the Markov chain M . Briefly, the symbolic trajectory ξ' is an ϵ-approximation of the symbolic trajectory ξ iff (1) ξ' agrees with ξ during its transient phase; and (2) both ξ and ξ' are within an ϵ-neighborhood at all times after the transient phase. Our main results are that one can effectively check whether (i) for each infinite word in L , at least one of its ϵ-approximations satisfies the given specification; (ii) for each infinite word in L , all its ϵ-approximations satisfy the specification. These verification results are strong in that they apply to all finite state Markov chains.

We give an $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious arithmetic branching programs (ROABPs). The best time complexity known for blackbox polynomial identity testing (PIT) for this class was $n^{O(\log^2 n)}$ due to Forbes, Saptharishi, and Shpilka [Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875]. Moreover, their result holds only when the individual degree is small, while we do not need any such assumption. With this, we match the time complexity for the unknown-order ROABP with the known-order ROABP (due to Forbes and Shpilka [Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 243--252]) and also with the depth-3 set-multilinear circuits (due to Agrawal, Saha, and Saxena [Proceedings of the 2013 ACM Symposium on Theory of Computing, 2013, pp. 321--330]). Our proof is simpler and involves a new technique called basis isolation. The depth-3 model has recently gained much importance, as it has become a stepping stone to understanding general arithmetic circuits. Multilinear depth-3 circuits are known to have exponential lower bounds but no polynomial time blackbox identity tests. In this paper, we take a step toward designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-3 circuits. To achieve this, we define the notions of distance and base sets. Distance, for a multilinear depth-3 circuit (say, in $n$ variables and $k$ product gates), measures how far the variable partitions corresponding to the product gates are from being a mere refinement of each other. The 1-distance circuits strictly contain the set-multilinear model, while $n$-distance captures general multilinear depth-3. We design a hitting-set in time $(nk)^{O(\Delta \log n)}$ for $\Delta$-distance. Further, we give an extension of our result to models where the distance is large (close to $n$) but is small when restricted to certain base sets (of variables). We also explore a new model of ROABPs where the factor matrices are invertible (called invertible-factor ROABPs). We design a hitting-set in time poly($n^{w^2}$) for width-$w$ invertible-factor ROABPs. Further, we could do without the invertibility restriction when w=2. Previously, the best result for width-2 ROABPs was quasi-polynomial time [M. A. Forbes, R. Saptharishi, and A. Shpilka, Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875].

We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition X1⊔⋅⋅⋅⊔ Xd of the variable indices [n] that the top product layer respects, i.e. C(term{x})=∑i=1k ∏j=1d fi,j(term{x}Xj), where fi,j is a sparse polynomial in F[term{x}Xj]. Extending this definition to any depth - we call a depth-D formula C (consisting of alternating layers of Σ and Π gates, with a Σ-gate on top) a set-depth-D formula if every Π-layer in C respects a (unknown) partition on the variables; if D is even then the product gates of the bottom-most Π-layer are allowed to compute arbitrary monomials. In this work, we give a hitting-set generator for set-depth-D formulas (over any field) with running time polynomial in exp((D2log s) Δ - 1), where s is the size bound on the input set-depth-D formula. In other words, we give a quasi-polynomial time blackbox polynomial identity test for such constant-depth formulas. Previously, the very special case of D=3 (also known as set-multilinear depth-3 circuits) had no known sub-exponential time hitting-set generator. This was declared as an open problem by Shpilka & Yehudayoff (FnT-TCS 2010); the model being first studied by Nisan & Wigderson (FOCS 1995) and recently by Forbes & Shpilka (STOC 2012 & ECCC TR12-115). Our work settles this question, not only for depth-3 but, up to depth εlog s / log log s, for a fixed constant ε < 1. The technique is to investigate depth-D formulas via depth-(D-1) formulas over a Hadamard algebra, after applying a 'shift' on the variables. We propose a new algebraic conjecture about the low-support rank-concentration in the latter formulas, and manage to prove it in the case of set-depth-D formulas.

A finite state Markov chain M is often viewed as a probabilistic transition system. An alternative view - which we follow here - is to regard M as a linear transform operating on the space of probability distributions over its set of nodes. The novel idea here is to discretize the probability value space [0,1] into a finite set of intervals. A concrete probability distribution over the nodes is then symbolically represented as a tuple D of such intervals. The i-th component of the discretized distribution D will be the interval in which the probability of node i falls. The set of discretized distributions is a finite set and each trajectory, generated by repeated applications of M to an initial distribution, will induce a unique infinite string over this finite set of letters. Hence, given a set of initial distributions, the symbolic dynamics of M will consist of an infinite language L over the finite alphabet of discretized distributions. We investigate whether L meets a specification given as a linear time temporal logic formula whose atomic propositions will assert that the current probability of a node falls in an interval. Unfortunately, even for restricted Markov chains (for instance, irreducible and aperiodic chains), we do not know at present if and when L is an (omega)-regular language. To get around this we develop the notion of an epsilon-approximation, based on the transient and long term behaviors of M. Our main results are that, one can effectively check whether (i) for each infinite word in L, at least one of its epsilon-approximations satisfies the specification; (ii) for each infinite word in L all its epsilon approximations satisfy the specification. These verification results are strong in that they apply to all finite state Markov chains. Further, the study of the symbolic dynamics of Markov chains initiated here is of independent interest and can lead to other applications.

We present a single common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT), that have been hitherto solved using diverse tools and techniques, over fields of zero or large characteristic. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied models - depth-3 circuits with bounded top fanin, and constant-depth constant-read multilinear formulas - can be constructed using one common algebraic-geometry theme: Jacobian captures algebraic independence. By exploiting the Jacobian, we design the first efficient hitting-set generators for broad generalizations of the above-mentioned models, namely: - depth-3 (Ω Π Ω) circuits with constant transcendence degree of the polynomials computed by the product gates (no bounded top fanin restriction), and - constant-depth constant-occur formulas (no multilinear restriction). Constant-occur of a variable, as we define it, is a much more general concept than constant-read. Also, earlier work on the latter model assumed that the formula is multilinear. Thus, our work goes further beyond the related results obtained by Saxena & Seshadhri (STOC 2011), Saraf & Volkovich (STOC 2011), Anderson et al. (CCC 2011), Beecken et al. (ICALP 2011) and Grenet et al. (FSTTCS 2011), and brings them under one unifying technique.

The Theory and Applications of Models of Computation (TAMC) conference series is both international and interdisciplinary in character, bringing together researchers working in computer science, mathematics (especially logic) and the physical sciences. It is this, together with its predominantly computational and computability theoretic focus, that gives the series its special character.

The Berman-Hartmanis conjecture states that all NP-complete sets are P-isomorphic each other. On this conjecture, we first improve the previous result of Agrawal and show that all NP-complete sets are lesli,1-1P/poly-reducible to each other based on the assumption that there exist regular one way functions that cannot be inverted by randomized polynomial time algorithms. Secondly, we show that, besides the above assumption, if all one-way functions have some easy part to invert, then all NP-complete sets are P/poly-isomorphic to each other.

We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of identity testing problem for depth four circuits with multiplication gates of small fanin implies a nearly complete derandomization of general identity testing.

We extract a paradigm for derandomizing tests for polynomial identities from the recent AKS primality testing algorithm. We then discuss its possible application to other tests.

We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Z n holds.We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over Z n for any n . The running time of the algorithms is polynomial in the size of arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, for example, the Schwartz--Zippel test [Schwartz 1980; Zippel 1979], Chen--Kao and Lewin--Vadhan tests [Chen and Kao 1997; Lewin and Vadhan 1998].

It is shown that, if there exist sets in E (the exponential complexity class) that require 2/sup /spl Omega/(n)/-sized circuits, then sets that are hard for class P (the polynomial complexity class) and above, under 1-1 reductions, are also hard under 1-1 size-increasing reductions. Under the assumption of the hardness of solving the RSA (Rivest-Shamir-Adleman, 1978) problem or the discrete log problem, it is shown that sets that are hard for class NP (nondeterministic polynomial) and above, under many-1 reductions, are also hard under (non-uniform) 1-1 and size-increasing reductions.

For any class C closed under NC/sup 1/ reductions, it is shown that all sets complete for C under logspace-uniform AC/sup 0/ reductions are isomorphic under logspace-uniform AC/sup 0/-computable isomorphisms.

We investigate the computational complexity of the formula isomorphism problem (FI): on input of two boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. FI is contained in ${\Sigma_{2}{\bf P}}$, the second level of the polynomial hierarchy. Our main result is a one-round interactive proof for the complementary formula nonisomorphism problem (FNI), where the verifier has access to an NP-oracle. To obtain this, we use a result from learning theory by Bshouty et al. that boolean formulas can be learned probabilistically with equivalence queries and access to an NP-oracle. As a consequence, FI cannot be ${\Sigma_{2}{\bf P}}$-complete unless the polynomial hierarchy collapses. Further properties of FI are shown: FI has and- and or-functions, the counting version, #FI, can be computed in polynomial time relative to FI, and FI is self-reducible.

Gives a simple and new primality testing algorithm by reducing primality testing for a number n to testing if a specific univariate identity over Z/sub n/ holds. We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over Z/sub n/ for any n. The running time of the algorithms is polynomial in the size of the arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, e.g. the Schwartz-Zippel test (J.T. Schwartz, 1980; R.E. Zippel, 1979), the Chen-Kao (1997) test and the Lewin-Vadhan (1998) test. Our algorithms first transform the input polynomial to a univariate polynomial and then use Chinese remaindering over univariate polynomials to effectively test if it is zero.

Continuing a line of investigation that has studied the function classes P, we study the class of functions AC/sup 0/. One way to define AC/sup 0/ is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fanin addition and multiplication gates. In contrast to the preceding function classes, for which we know no nontrivial lower bounds, lower bounds for AC/sup 0/ follow easily from established circuit lower bounds. One of our main results is a characterization of TC/sup 0/ in terms of AC/sup 0/: A language A is in TC/sup 0/ if and only if there is a AC/sup 0/ function f and a number k such that x/spl isin/A/spl hArr/f(x)=2/sup |x|k/. Using the naming conventions, this yields: TC/sup 0/=PAC/sup 0/=C=AC/sup 0/. Another restatement of this characterization is that TC/sup 0/ can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC/sup 0/ in terms of AC/sup 0/ circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC/sup 0/ in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC/sup 0/. We also prove a number of closure properties and normal forms for AC/sup 0/.

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 show that all sets complete for NC/sup 1/ under AC/sup 0/ reductions are isomorphic under AC/sup 0/-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC/sup 1/-computable many-one reductions, the sets complete for C under NC/sup 0/ reductions are all isomorphic under AC/sup 0/-computable isomorphisms. Our result showing that the complete degree for NC/sup 1/ collapses to an isomorphism type follows from a theorem showing that in NC/sup 1/, the complete degrees for AC/sup 0/ and NC/sup 0/ reducibility coincide. This theorem does not hold for strongly uniform reduction: we show that there are Dlogtime-uniform AC/sup 0/-complete sets for NC/sup 1/ that are not Dlogtime-uniform NC/sup 0/-complete.

We show that for any graph G, k non-trivial automorphisms of G-if as many exist-can be computed in time |G|/sup O(log k/) with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence we show that some problems related to GA and GI are polynomial-time truth-table equivalent to GA.

We investigate the computational complexity of the Boolean isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for BI, where the verifier has access to an NP oracle. To obtain this, we use a recent result from learning theory by N. Bshouty et al. (1995), that Boolean formulas can be learned probabilistically with equivalence queries and access to an NP oracle. As a consequence, BI cannot be /spl Sigma//sub 2//sup p/ complete unless the polynomial hierarchy collapses. This solves an open problem posed previously. Further properties of BI are shown: BI has And- and Or-functions, the counting version, BI, can be computed in polynomial time relative to BI, and BI is self-reducible.