Arithmetic natural proofs theory is sought
This post will be longer and more technical than most — but what can I say? Sometimes you need to get something technical off your chest. The topic is something my student, Andy Drucker, and I (along with several interested others) have been thinking about on and off for months, and if we’re not going to get a paper out of it, at least we’ll have this blog post.
Complexity theory could be defined as the field concerned with deep, nontrivial, mathematically-sophisticated justifications for failure. For example, we can’t solve NP-complete problems in polynomial time, but maybe that’s not so bad, since we conjecture there is no solution (P≠NP). Of course, we also can’t prove P≠NP — but maybe that’s not so bad either, since we have good explanations for why the problem is so hard, like relativization, natural proofs, and algebrization.
On the other hand, consider the problem of showing that the Permanent of an nxn matrix requires arithmetic circuits of more than polynomial size. (Given a field F—which we’ll assume for this post is finite—an arithmetic circuit over F is a circuit whose only allowed operations are addition, subtraction, and multiplication over F, and that doesn’t have direct access to the bit representations of the field elements.)
The problem of circuit lower bounds for the Permanent is currently at the frontier of complexity theory. As we now know, it’s intimately related both to derandomizing polynomial identity testing and to the τ problem of Blum, Cucker, Shub, and Smale. Alas, not only can we not prove that Perm∉AlgP/poly (which is the street name for this conjecture), we don’t have any good excuse for why we can’t prove it! Relativization and algebrization don’t seem to apply here, since no one would think of using diagonalization-based techniques on such a problem in the first place. So that leaves us with natural proofs.
The theory of natural proofs, which was developed by Razborov and Rudich in 1993 and for which they recently shared the Gödel Prize, started out as an attempt to explain why it’s so hard to prove NP⊄P/poly (i.e., that SAT doesn’t have polynomial-size circuits, which is a slight strengthening of P≠NP). They said: suppose the proof were like most of the circuit lower bound proofs that we actually know (as a canonical example, the proof that Parity is not in AC0). Then as a direct byproduct, the proof would yield an efficient algorithm A that took as input the truth table of a Boolean function f, and determined that either:
- f belongs to an extremely large class C of “random-looking” functions, which includes SAT but does not include any function computable by polynomial-size circuits, or
- f does not belong to C.
(The requirement that A run in time polynomial in the size of the truth table, N=2n, is called constructivity. The requirement that C be a large class of functions — say, at least a 2-poly(n) fraction of functions — is called largeness.)
Razborov and Rudich then pointed out that such a polynomial-time algorithm A could be used to distinguish truly random functions from pseudorandom functions with non-negligible bias. As follows from the work of Håstad-Impagliazzo-Levin-Luby and Goldreich-Goldwasser-Micali, one could thereby break one-way functions in subexponential time, and undermine almost all of modern cryptography! In other words, if cryptography is possible, then proofs with the property above are not possible. The irony — we can’t prove lower bounds because lower bounds very much like the ones we want to prove are true — is thick enough to spread on toast.
Now suppose we tried to use the same argument to explain why we can’t prove superpolynomial arithmetic circuit lower bounds for the Permanent, over some finite field F. In that case, a little thought reveals that what we’d need is an arithmetic pseudorandom function family over F. More concretely, we’d need a family of functions gs:Fn→F, where s is a short random “seed”, such that:
- Every gs is computable by a polynomial-size, constant-depth (or at most log-depth) arithmetic circuit, but
- No polynomial-time algorithm, given oracle access to gs (for a randomly-chosen s), is able to distinguish gs from a random low-degree polynomial over F with non-negligible bias.
It’s important not to get so hung up on definitional details that you miss the substantive issue here. However, three comments on the definition seem in order.
Firstly, we restrict gs to be computable by constant or log-depth circuits, since that’s the regime we’re ultimately interested in (more about this later). The Permanent is a low-degree polynomial, and well-known depth reduction theorems say (roughly speaking) that any low-degree polynomial that’s computable by a small circuit, is also computable by a small circuit with very small depth.
Secondly, we say that no polynomial-time algorithm should be able to distinguish gs from a random low-degree polynomial, rather than a random function. The reason is clear: if gs is itself a low-degree polynomial, then it can always be distinguished easily from a random function, just by picking a random line and doing polynomial interpolation! On the other hand, it’s reasonable to hope that within the space of low-degree polynomials, gs looks random—and that’s all we need to draw a natural proofs conclusion. Note that the specific distribution over low-degree polynomials that we simulate doesn’t really matter: it could be (say) the uniform distribution over all degree-d polynomials for some fixed d, or the uniform distribution over polynomials in which no individual variable is raised to a higher power than d.
Thirdly, to get a close analogy with the original Razborov-Rudich theory, we stipulated that no ordinary (Boolean) polynomial-time algorithm should be able to distinguish gs from a random low-degree polynomial. However, this is not essential. If we merely knew (for example) that no polynomial-size arithmetic circuit could distinguish gs from a random low-degree polynomial, then we’d get the weaker but still interesting conclusion that any superpolynomial arithmetic circuit lower bound for the Permanent would have to be “arithmetically non-naturalizing”: that is, it would have to exploit some property of the Permanent that violates either largeness or else “arithmetic constructivity.” There’s a smooth tradeoff here, between the complexity of the distinguishing algorithm and the strength of the natural proofs conclusion that you get.
There’s no question that, if we had an arithmetic pseudorandom function family as above, it would tell us something useful about arithmetic circuit lower bounds. For we do have deep and nontrivial arithmetic circuit lower bounds — for example, those of Nisan and Wigderson (see also here), Razborov and Grigoriev, Grigoriev and Karpinski, Shpilka and Wigderson, Raz (see also here), Raz, Shpilka, and Yehudayoff, Raz and Yehudayoff, and Mignon and Ressayre. And as far as I can tell, all of these lower bounds do in fact naturalize in the sense above. (Indeed, they should even naturalize in the strong sense that there are quasipolynomial-size arithmetic circuits for the relevant properties.) Concretely, most of these techniques involve looking at the truth table (or rather, the “value table”) of the function g:Fn→F to be lower-bounded, constructing so-called partial-derivatives matrices from that truth table, and then lower-bounding the ranks of those matrices. But these operations—in particular, computing the rank—are all polynomial-time (or quasipolynomial-time for arithmetic circuits). Thus, if we could construct arithmetic pseudorandom functions, we could use them to argue that no techniques similar to the ones we know will work to prove superpolynomial arithmetic circuit lower bounds for the Permanent.
So the problem is “merely” one of constructing these goddamned arithmetic pseudorandom functions. Not surprisingly, it’s easy to construct arithmetic function families that seem pseudorandom (concrete example coming later), but the game we’re playing is that you need to be able to base the pseudorandomness of your PRF on some ‘accepted’ or ‘established’ computational intractability assumption. And here, alas, the current toolbox of complexity theory simply doesn’t seem up for the job.
To be sure, we have pseudorandom function families that are computable by constant-depth Boolean threshold circuits — most famously, those of Naor and Reingold, which are pseudorandom assuming that factoring Blum integers or the decisional Diffie-Hellman problem are hard. (Both assumptions, incidentally, are false in the quantum world, but that’s irrelevant for natural proofs purposes, since the proof techniques that we know how to think about yield polynomial-time classical algorithms.) However, the Naor-Reingold construction is based on modular exponentiation, and doing modular exponentiation in constant depth crucially requires using the bit representation of the input numbers. So this is not something that’s going to work in the arithmetic circuit world.
At the moment, it seems the closest available result to what’s needed is that of Klivans and Sherstov in computational learning theory. These authors show (among other things) that if the n1.5-approximate shortest vector problem is hard for quantum computers, then learning depth-3 arithmetic circuits from random examples is intractable for classical computers. (Here quantum computing actually is relevant—since by using techniques of Regev, it’s possible to use a quantum hardness assumption to get a classical hardness consequence!)
This result seems like exactly what we need—so then what’s the problem? Why aren’t we done? Well, it’s that business about the random examples. If the learner is allowed to make correlated or adaptive queries to the arithmetic circuit’s truth table — as we need to assume it can, in the arithmetic natural proofs setting — then we don’t currently have any hardness result. Furthermore, there seems to me to be a basic difficulty in extending Klivans-Sherstov to the case of adaptive queries (though Klivans himself seemed more optimistic). In particular, there’s a nice idea due to Angluin and Kharitonov, which yields a generic way (using digital signatures) for converting hardness-of-learning results against nonadaptive queries to hardness-of-learning results against adaptive queries. But interestingly, the Angluin-Kharitonov reduction depends essentially on our being in the Boolean world, and seems to break down completely in the arithmetic circuit world.
So, is this all Andy and I can say—that we tried to create an arithmetic natural proofs theory, but that ultimately, our attempt to find a justification of failure to find a justification of failure was itself a failure? Well, not quite. I’d like to end this post with one theorem, and one concrete conjecture.
The theorem is that, if we don’t care about the depth of the arithmetic circuits (or, more-or-less equivalently, the degree of the polynomials that they compute), then we can create arithmetic pseudorandom functions over finite fields, and hence the arithmetic natural proofs theory that we wanted. Furthermore, the only assumption we need for this is that pseudorandom functions exist in the ordinary Boolean world — about the weakest assumption one could possibly hope for!
This theorem might seem surprising, since after all, we don’t believe that there’s any general way to take a polynomial-size Boolean circuit C that operates on finite field elements x1,…,xn represented in binary, and simulate C by a polynomial-size arithmetic circuit that uses only addition, subtraction, and multiplication, and not any bit operations. (The best such simulation, due to Boneh and Lipton, is based on elliptic curves and takes moderately exponential time.) Nevertheless, Andy and I are able to show that for pseudorandomness purposes, unbounded-depth Boolean circuits and unbounded-depth arithmetic circuits are essentially equivalent.
To prove the theorem: let the input to our arithmetic circuit C be elements x1,…,xn of some finite field Fp (I’ll assume for simplicity that p is prime; you should think of p as roughly exponential in n). Then what C will do will be to first compute various affine functions of the input:
y1=a0+a1x1+…+anxn, y2=b0+b1x1+…+bnxn, etc.,
as many such functions as are needed, for coefficients ai, bi, etc. that are chosen at random and then “hardwired” into the circuit. C will then raise each yi to the (p-1)/2 power, using repeated squaring. Note that in a finite field Fp, raising y≠0 to the (p-1)/2 power yields either +1 or -1, depending on whether or not y is a quadratic residue. Let zi=(yi+1)/2. Then we now have a collection of 0/1 “bits.” Using these bits as our input, we can now compute whatever Boolean pseudorandom function we like, as follows: NOT(x) corresponds to the polynomial 1-x, AND(x,y) corresponds to xy, and OR(x,y) corresponds to 1-(1-x)(1-y). The result of this will be a collection of pseudorandom output bits, call them w1,…,wm. The final step is to convert back into a pseudorandom finite field element, which we can do as follows:
Output = w1 + 2w2 + 4w3 + 8w4 + … + 2m-1wm.
This will be pseudorandom assuming (as we can) that 2m is much larger than p.
But why does this construction work? That is, assuming the Boolean circuit was pseudorandom, why is the arithmetic circuit simulating it also pseudorandom? Well, this is a consequence of two basic facts:
- Affine combinations constitute a family of pairwise-independent hash functions. That is, for every pair (x1,…,xn)≠(y1,…,yn), the probability over a0,…,an that a0+a1x1+…+anxn=a0+a1y1+…+anyn is only 1/p. Furthermore, the pairwise independence can be easily seen to be preserved under raising various affine combinations to the (p-1)/2 power.
- If we draw f from a family of pseudorandom functions, and draw h from a family of pairwise-independent hash functions, then f(h(x)) will again be a pseudorandom function. Intuitively this is “obvious”: after all, the only way to distinguish f(h(x)) from random without distinguishing f from random would be to find two inputs x,y such that h(x)=h(y), but since h is pairwise-independent and since the outputs f(h(x)) aren’t going to help, finding such a collision should take exponential time. A formal security argument can be found (e.g.) in this paper by Bellare, Canetti, and Krawczyk.
Now for the conjecture. I promised earlier that I’d give you an explicit candidate for a (low-degree) arithmetic pseudorandom function, so here it is. Given inputs x1,…,xn∈Fp, let m be polynomially related to n, and let L1(x1,…,xn),…,Lm^2(x1,…,xn) be affine functions of x1,…,xn, with the coefficients chosen at random and then “hardwired” into our circuit, as before. Arrange L1(x1,…,xn),…,Lm^2(x1,…,xn) into an mxm matrix, and take the determinant of that matrix as your output. That’s it.
(The motivation for this construction is Valiant’s result from the 1970s, that determinant is universal under projections. That might suggest, though of course it doesn’t prove, that breaking this function should be as hard as breaking any other arithmetic pseudorandom function.)
Certainly the output of the above generator will be computable by an arithmetic circuit of size mO(log m)n. On the other hand, I conjecture that if you don’t know L1,…,Lm^2, and are polynomial-time bounded, then the output of the generator will be indistinguishable to you from that of a random polynomial of degree m. I’m willing to offer $50 to anyone who can prove or disprove this conjecture—or for that matter, who can prove or disprove the more basic conjecture that there exists a low-degree arithmetic pseudorandom function family! (Here, of course, “prove” means “prove modulo some accepted hardness assumption,” while “disprove” means “disprove.”)
But please be quick about it! If we don’t hurry up and find a formal barrier to proving superpolynomial lower bounds for the Permanent, someone might actually roll up their sleeves and prove one—and we certainly don’t want that!
Follow
Comment #1 June 30th, 2008 at 4:05 pm
Fascinating post. Thanks very much for sharing this on your blog!
I strongly suspect this is an ignorant reply/question, but here goes:
Here’s a trick for turning a weak PRF into a PRF. A weak PRF (WPRF) is one that is indistinguishable from a random function when fed randomly chosen inputs (but not necessarily indistinguishable when fed chosen inputs, let alone adaptively chosen inputs). Given a WPRF F, you can easily build a pseudorandom generator (PRG) G: e.g., pick x,x’ randomly once and for all, and let G(k) = (F_k(x), F_k(x’)). Given a PRG G, you can build a PRF H, using the GGM tree construction: to compute H_k(x), you evaluate G(k), take the left or right half of the result according to the first bit of x, and then continue iteratively through the bits of x. In fact, one can make this more efficient by first hashing x with a 2-universal hash family. If the 2-universal hash produces a 160-bit output, then we get a new PRF that requires 2*160 invocations of the original WPRF F (since the GGM tree has depth 160). The insecurity of the new PRF is negligible if the insecurity of the WPRF is negligible.
That’s all in the boolean world. Can we apply this to the arithmetic world, using the trick from your post? It sounds like Klivans-Sherstov gives (under appropriate hardness assumptions) a algebraic WPRF, i.e., a WPRF that can be computed by an algebraic circuit. We could presumably build a new PRF (that is algebraic) as follows. On input x_1,..,x_n (a sequence of finite field elements), we hash it to a sequence of 160 bits (i.e., field elements that are all 0 or 1), using your trick, i.e., the output is z_1,..,z_160, where z_i is defined as in your post. Now we can use those in the GGM tree construction as above, using z_i to tell us whether to go left or right at depth i in the GGM tree. Of course, the multiplexor operation mult(i,w_0,w_1) = w_i is algebraic, since it can be expressed as mult(i,w_0,w_1) = i * (w_1 – w_0) + w_0. It sounds like this should give us a PRF that can be expressed as an algebraic circuit.
Is the issue that the depth of this circuit is increased too much (i.e., the degree is blown up by a ridiculous factor)? So the crucial hard problem is, given an algebraic WPRF, can we construct an algebraic PRF whose arithmetic circuit depth is not too much larger – is that right?
I suspect this is a stupid question; I’m just trying to work through and understand the implications of your post. Thanks again for your post!
Comment #2 June 30th, 2008 at 4:38 pm
David, thanks for the comment! Yes, you’re exactly right: the problem with GGM is that the circuit depth (and polynomial degree) increase by too much.
Comment #3 July 1st, 2008 at 12:09 am
Ok, what the hell, i have 5 minutes.
Comment #4 July 1st, 2008 at 3:28 am
I was told there would be no complexity theory on this exam.
Comment #5 July 1st, 2008 at 4:09 am
The answer is Brown!
Comment #6 July 2nd, 2008 at 1:23 pm
Proving a super-polynomial lower bound for the running-time of any algorithm which computes the permanent of an nxn matrix is easy: The problem is equivalent to solving n independent subproblems, namely that of picking one of the n entries in the top row and multiplying that entry by the permanent of the (n-1)x(n-1) matrix that does not include the top row and does not include the column of that entry, and then adding the answers to each of the n independent subproblems together to get the permanent of the original nxn matrix.
The n subproblems are independent because they each require a different entry from the top row. Hence, it is impossible for an algorithm that computes the permanent of the original nxn matrix to have a faster worst-case running-time than the algorithm with the fastest worst-case running-time that computes the permanent of each of the n (n-1)x(n-1) submatrices and adds them together. And the fastest way to do this is to compute the permanent of each of the n (n-1)x(n-1) submatrices in the fastest way possible while exploiting the fact that these subproblems are overlapping (since the subproblems are not totally independent, as they each involve the bottom n-1 rows of the original matrix). So we have just derived a recursive characteristic of the fastest possible algorithm which computes the permanent of an nxn matrix.
From this observation, it is easy to use mathematical induction to show that the standard dynamic programming method (see Ryser’s algorithm), which has exponential running-time on the order of O*(2^n), of computing a permanent of a matrix satisfies this recursive characteristic. Hence, the standard dynamic programming method for computing a permanent of a matrix has the best possible running-time of any algorithm that computes the permanent of a matrix.
It’s that simple. You can also use a similar argument to show that the Held-Karp algorithm has the fastest possible worst-case running-time for solving the Traveling Salesman problem too. This is all consistent with the fact that no improvement of the Held-Karp algorithm has ever been found since the Held-Karp algorithm was discovered in 1962 and no improvement of Ryser’s algorithm has ever been found since Ryser’s algorithm was published in 1963.
Comment #7 July 2nd, 2008 at 3:04 pm
Craig, the argument you sketch would seem to also imply that Determinant takes super-polynomial time as well, which is false.
There are two flaws in the argument. First, the sub-problems you mention are not truly ‘independent’ as you claim, since they have overlapping inputs.
Second, finding the permanent for the big matrix is not necessarily ‘equivalent’ (in any sense I recognize) to finding the n permanents of the submatrices. For example, I have in front of me a 5-by-5 matrix whose permanent is 100. Can you tell me what the 5 submatrix permanents are?
Comment #8 July 2nd, 2008 at 6:22 pm
Andy,
You said: “the argument you sketch would seem to also imply that Determinant takes super-polynomial time as well, which is false.”
My response is that the argument that I sketched does not imply that calculating the determinant takes super-polynomial time. I don’t know why you would think that.
You also said: “There are two flaws in the argument. First, the sub-problems you mention are not truly ‘independent’ as you claim, since they have overlapping inputs.”
My response to this comment is that you could not have read my whole post. In fact, I explicitly acknowledged this fact in my original post. I said, “while exploiting the fact that these subproblems are overlapping (since the subproblems are not totally independent, as they each involve the bottom n-1 rows of the original matrix).”
You also said: “Second, finding the permanent for the big matrix is not necessarily ‘equivalent’ (in any sense I recognize) to finding the n permanents of the submatrices. For example, I have in front of me a 5-by-5 matrix whose permanent is 100. Can you tell me what the 5 submatrix permanents are?”
My response: Again, you didn’t read everything I wrote. I never said that “finding the permanent for the big matrix is not necessarily ‘equivalent’ (in any sense I recognize) to finding the n permanents of the submatrices.” I said that finding the permanent for the big matrix is equivalent to finding the n permanents of the submatrices and then adding them together. The two problems are equivalent in the sense that they both yield the same answers.
Anyway, there you have it. A very simple way to derive lower bounds without doing anything fancy.
Comment #9 July 2nd, 2008 at 7:34 pm
Craig-
i) the same lower-bounds ‘proof’ appears to work for determinant since it has a similar expansion as a sum of top-row elements times dets of submatrices (this time a signed sum).
ii) even if you acknowledge the subproblems are not ‘totally independent’ (and I did overlook that, my apologies), in what formal sense are they independent and what does this imply?
iii) In the sense you’ve just mentioned, computing a sum x + y is ‘equivalent’ to running some correct addition algorithm that uses exponential time; but what does this observation tell us about the true complexity of addition? And what is it about the ‘subproblems’ you identify in computing Permanent that makes them somehow more intrinsic than the complications introduced by a suboptimal algorithm for any old problem?
Comment #10 July 2nd, 2008 at 8:03 pm
Andy,
You said: “i) the same lower-bounds ‘proof’ appears to work for determinant since it has a similar expansion as a sum of top-row elements times dets of submatrices (this time a signed sum).”
So what if the determinant has a similar expansion? The fact is that when taking the determinant, more things cancel out than when computing the permanent, so it is possible to better exploit the overlapping structure of the n subproblems when computing the determinant than when computing the permanent. You could even get a tight lower-bound for computing the determinant of a matrix using this argument, but in this case the tight lower-bound would be a polynomial.
You said: “ii) even if you acknowledge the subproblems are not ‘totally independent’ (and I did overlook that, my apologies), in what formal sense are they independent and what does this imply?”
I answered this question in the 2nd paragraph of my first post. I think you should read all of my post before critiquing it.
Comment #11 July 2nd, 2008 at 8:37 pm
Say, you wouldn’t happen to be the Craig of P vs NP fame, would you? Some of your reasoning sounds familiar.
Comment #12 July 2nd, 2008 at 9:45 pm
I thought we were asked to find a barrier to proving superpolynomial lower bounds for the Permanent, not prove superpolynomial lower bounds for the Permanent. Get with the program already.
Comment #13 July 2nd, 2008 at 10:30 pm
Craig, thanks so much! As it happens, I’ve been working incredibly hard this summer trying to prove a certain lower bound on AC0 circuits: staying up all night, filling notebooks, etc. I have some partial results but nowhere near what I wanted.
I don’t know why I never thought of your simple, easy Aggressive Doofosity approach: “I don’t see a better way to compute it, so there must not be one!” Had I used your method, I’d have long been finished with my problem, as well as every other problem in the field. Sorting: obviously it takes n2 comparisons (since you have to compare every element against every other one), next! Matrix multiplication: obviously n3 is optimal, next!
Indeed, precisely because you’ve shown us the way to settle each and every one of our open problems, you can have nothing further to add to this thread, and further comments from you will be deleted.
Comment #14 July 2nd, 2008 at 11:10 pm
(the blog text-ate)
I have a few beginner’s questions about pseudorandom functions:
If the output of a function A(x) requires f(n) time to compute and we’re time-bounded to g(n) where g(n) less than f(n), then A(x) is not necessarily pseudorandom, right?
Then, can we say that a function A(x) is pseudorandom (when time-bounded to g(n)) iff there is no repeating pattern in A(x) identifiable in g(n) time?
So we have to prove the absense of any g(n)-time-identifiable patterns in order to show that a given function or function family is pseudorandom or what?
Generally speaking, how does one prove that a function is pseudorandom?
Comment #15 July 2nd, 2008 at 11:28 pm
Generally speaking, how does one prove that a function is pseudorandom?
Alas, in our current state of knowledge, one generally doesn’t. Rather, one proves that if the function in question could be distinguished from truly random by a polynomial-time algorithm, then there would also be a polynomial-time algorithm for factoring integers, or for some other problem which is believed to be intractable.
(Having said that, we can prove that certain functions are pseudorandom against relatively weak kinds of distinguishers, like low-degree polynomials and constant-depth circuits. The hard part is proving that some efficiently computable function is pseudorandom against arbitrary polynomial-time algorithms. That’s at least as hard as proving P≠NP!)
Comment #16 July 3rd, 2008 at 10:08 am
Craig, don’t you actually realize you are talking nonsense?
First of all, as pointed out, your argument would imply the same for the determinant. It’s weird that you seem unable to see this, but if you substitute “permanent” for “determinant” in your first post, all your arguments work equally well (or bad), so you can’t deny that the reasoning is at least incomplete. You later go on to say that it doesn’t apply for the determinant, but you should be able to tell exactly where the difference lies then. Saying that “things cancel out” doesn’t prove anything; how do you prove that “things cancel out” in the case of the determinant but not in that of the permanent?
You haven’t answered in what sense those problems are independent of each other (since they aren’t). And the fact that you can compute the permanent from the permanents from the submatrices doesn’t mean that there can’t be any better method, since as Andy pointed out, you only need to compute the sum of those permanents, not necessarily each of them. Thus your claim “And the fastest way to do this is to compute the permanent of each of the n (n-1)x(n-1) submatrices in the fastest way possible” remains unsubstantiated. How can you know that is the fastest way? You could conceivable find out the permanent without finding that of the submatrices. Again, the determinant is a good counterexample to your line of reasoning. And if you think it isn’t, you should specify clearly which steps don’t apply in that case.
And yes, we have read all your posts. Have you read ours?
Comment #17 July 3rd, 2008 at 7:04 pm
Help! Wikipedia has nothing on the Held-Karp algorithm. Can anyone fix that?
Comment #18 July 3rd, 2008 at 7:17 pm
Scott or Andy or actually anyone: why are you SO sure
that getting a lower bound is hard to do that you are looking
at proving that you can’t (given some assumptions we
believe)? Is there some informal reason to think that getting
a lower bound on this problem is hard to do?
Comment #19 July 3rd, 2008 at 8:02 pm
Bill, for me the main informal reason is that it seems like an arithmetic analogue of P!=NP. But on top of that, for me it seems likely on independent grounds that arithmetic PRGs exist.
Comment #20 July 3rd, 2008 at 9:13 pm
The motivation for this construction is Valiant’s result from the 1970s, that determinant is universal under projections. That might suggest, though of course it doesn’t prove, that breaking this function should be as hard as breaking any other arithmetic pseudorandom function.
Isn’t the only reason that universality of determinant doesn’t imply that your construction is, um, complete for pseudorandom functions (probably the wrong usage, but you get the idea), that there might be only a few degree-m polynomials that are hard to distinguish from random, and most are easy to distinguish from random? (And those pseudorandom polynomials might themselves be hard to find, etc.?) I don’t really have a point to make here, I just want to make sure I understand the post correctly.
On a not-completely-unrelated note, is there an arithmetic analogue of Impagliazzo’s hard-core set theorem? Or better yet, of Trevisan et al.’s constructive version of said theorem? Something along those lines might, if nothing else, at least let us prove that the determinant-of-affine-combinations function is pseudorandom iff there exist low-degree pseudorandom functions… Or maybe I’m totally wrong, in which case someone let me know before I say something else stupid.
Comment #21 July 3rd, 2008 at 9:59 pm
Harrison: Don’t worry about saying something stupid; the bar was already set for that. :-). The reason my construction might not be as hard as any other arithmetic PRG is that Valiant’s reduction yields very special matrices, not random ones. I don’t know the answer to your very interesting question about arithmetic hardcore sets–anyone else?
Comment #22 July 4th, 2008 at 10:10 pm
Scott, you really ought to comment here on Valiant’s “holographic algorithms” and his surprising finding that certain #P-complete counting problems can not only be solved mod 2 in polynomial time (permanent –> determinant guarantees this) but also solved mod 7 in plynomial time. Obviously of you can solve a counting problem modulo enough primes in polynomial time then you can solve it unconditionally, so one “obstacle” to proving that calculating the Permanent is hard is understanding and explaining what’s special about 7.
Comment #23 July 6th, 2008 at 11:40 am
Joe: Yes, Valiant’s mod 7 stuff was another great example of how a central reason it’s so hard to prove lower bounds is that there are such clever upper bounds! On the other hand, we do have many other examples of clever upper bounds, and it’s not yet clear to me that we need to focus on one such example to the exclusion of others.
Comment #24 July 8th, 2008 at 1:35 am
http://itcs.tsinghua.edu.cn/papers/2007/2007008.pdf seems to explain why mod 7 is special and what analogous larger moduli can be found. I don’t claim to understand the paper. I found it with google just now.
Comment #25 July 8th, 2008 at 8:20 am
Not sure if this is even related, but you argued previously that circuits consisting only of arithmetic operations probably naturalize as well, much to my frustration because I was hoping that a useful nontrivial lower bound could be shown on them, even just for circuit complexity on circuits which only have arithmetic gates. Naturalization is frustratingly insidious.
Comment #26 July 8th, 2008 at 9:24 am
Bram: Yes, it’s exactly the same question. We want to know whether naturalization applies to circuits consisting only of arithmetic gates. We believe it does, but we want to show it.
Comment #27 July 11th, 2008 at 12:46 pm
It’s nice how accessible the questions on the cutting edge of complexity theory are. Do you think that circuits consisting all of a single group operation other than addition have the same property as well?
Comment #28 July 11th, 2008 at 2:06 pm
It’s nice how accessible the questions on the cutting edge of complexity theory are.
You’re telling me! 🙂
Do you think that circuits consisting all of a single group operation other than addition have the same property as well?
That’s a great queston, which I also thought about a while ago. Yes, depending on the underlying group G, I believe it should be possible to create “pseudorandom functions” using only G’s group operation, though I don’t know of any explicit constructions — does anyone else?
Note that there’s a bit of ambiguity in what we mean by pseudorandom function here: do we want a poly-size circuit that’s indistinguishable from a random function f:Gn→G (apart from a few degeneracies like all inputs being set to ‘1’), or that’s merely indistinguishable from much larger circuits involving the group operation?
In neither case will it work for the group G to be abelian. For in that case, any circuit C over G can be distinguished from a random function by just checking whether
C(x1y1,…,xnyn)=C(x1,…,xn)C(y1,…,yn).
Furthermore, if G is abelian, then any function computable by a circuit over G is computable by a circuit of size O(nlog|G|) — and hence functions requiring large circuits don’t exist!
So you’ll want G to be nonabelian. Personally, I would first try for a construction using the matrix groups GLn(Fq).
Comment #29 July 11th, 2008 at 6:39 pm
Isn’t addition abelian? Why would addition naturalize while abelian but no other abelian group do so?
Comment #30 July 11th, 2008 at 8:25 pm
Bram, I don’t quite understand your question — I was arguing that the natural proofs framework doesn’t apply to circuits over any abelian group, including additive groups.
On reflection, though, I was only talking about functions f:Gn→G, which map many input group elements to a single output element. If we were talking about functions f:Gn→Gn, which mapped many inputs to many outputs, and if we cared about quadratic differences in circuit size (e.g., linear-size versus quadratic-size circuits), then I conjecture that the natural proofs framework would again become relevant. (E.g., that that there are families of functions f:Z2n→Z2n that have linear-size circuits and are therefore non-random, but are indistinguishable by any efficient algorithm from random functions.)
Comment #31 July 16th, 2008 at 8:55 pm
Ah, I see your position now. I was confused because you’d previously stated your belief about circuits with multiple outputs, and that sounded contradictory.
‘Efficient’ of course means something different when the output is something which can be computed in polynomial, time, probably being a polynomial with a lower exponent. Normally anything polynomial at all is ‘efficient’.
Comment #32 July 18th, 2008 at 4:53 pm
Scott, do you have any comment on how Severini et al developed your ideas from:
arXiv:quant-ph/0406196 [ps, pdf, other]
Title: Improved Simulation of Stabilizer Circuits
Authors: Scott Aaronson, Daniel Gottesman
Comments: 15 pages. Final version with some minor updates and corrections. Software at this http URL
Journal-ref: Phys. Rev. A 70, 052328 (2004) (14 pages)
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
in their new:
A further look into combinatorial orthogonality
Authors: Simone Severini, Ferenc Szöllősi
(Submitted on 23 Sep 2007 (v1), last revised 16 Jul 2008 (this version, v2))
Abstract: Strongly quadrangular matrices have been introduced in the study of the combinatorial properties of unitary matrices. It is known that if a
(0, 1)-matrix supports a unitary then it is strongly quadrangular. However, the converse is not necessarily true. In this paper, we fully classify strongly quadrangular matrices up to degree 5. We prove that the smallest strongly quadrangular matrices which do not support unitaries have exactly degree 5. Further, we isolate two submatrices not allowing a (0, 1)-matrix to support unitaries.
Comments: 11 pages, some typos are corrected. To appear in The Electronic journal of Linear Algebra
Subjects: Combinatorics (math.CO); Quantum Physics (quant-ph)
MSC classes: 05B20
Cite as: arXiv:0709.3651v2 [math.CO]
Comment #33 July 24th, 2008 at 4:02 pm
Scott, do you have any comment on…
Looks like an interesting paper.