tag:blogger.com,1999:blog-3722233.post112786193728594659..comments2019-11-20T05:21:31.299-05:00Comments on Computational Complexity: Circuit Complexity and P versus NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-1128129056533566552005-09-30T21:10:00.000-04:002005-09-30T21:10:00.000-04:00Yeah, there are n outputs, each of which requires ...Yeah, there are n outputs, each of which requires sqrt(n) to compute individually, and my conjecture is basically that computing them is completely orthogonal.<BR/><BR/>-BramAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127952397468186942005-09-28T20:06:00.000-04:002005-09-28T20:06:00.000-04:00Thanks, that makes perfect sense. Cool problem.Thanks, that makes perfect sense. Cool problem.Andynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127942628854726122005-09-28T17:23:00.000-04:002005-09-28T17:23:00.000-04:00I don't think this problem should be easy at all, ...I don't think this problem should be easy at all, even for linear circuits, although it looks interesting.<BR/><BR/>If I understand correctly the inputs are $n=p*p$ single bits (just ordered on the p*p grid) <BR/>and the (x,y)^th output is the XOR of all the bits that reside on the line specified by x and y. <BR/><BR/>Thus if (a,b) and (a',b') are two points then indeed they are contained in only one line. (Although I am pretty sure this property alone won't suffice for a lower bound)<BR/><BR/>Each individual bit is certainly easy here to produce as it takes \sqrt{n} XORs, so indeed any proof of this form is some kind of direct product construction.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127940652317871192005-09-28T16:50:00.000-04:002005-09-28T16:50:00.000-04:00Bram, I'm unsure of how to interpret your problem....Bram, I'm unsure of how to interpret your problem. Try to state it more formally. Especially worrisome, what is xor of numbers in Z^p? Do you mean addition mod p? <BR/><BR/>Also: be aware that if your input is n pairs of elements of [0, p), the strict input 'size' is bit-encoding size, i.e. ~2n*log(p) = 2p^2log(p). Your conjectured circuit lower bound, to be interesting, has to be superlinear in *this*, not just in n.<BR/><BR/>Finally, your output is more than a single bit; it's not a decision problem (which are more commonly studied), more is required. So proving you need a big circuit might be easier. But ask yourself if the individual output bits seem nearly as hard to produce; if this is the case you might prefer to concentrate on the problem of computing one of them.<BR/><BR/> If the complexity seems instead to come from there being many outputs, the issue is those outputs being relatively 'orthogonal' as mathematical entities--combining their computations doesn't give significant savings. I'm not aware of natural problems for which this is known in a strong way, and I'm not sure your problem is the one to achieve it since the bits seem integrally related.<BR/> Good luck.<BR/><BR/>P.S. for a classic problem that shows how problems can yield savings when computed together, try to write a prog to find both the max and min of n numbers with many fewer comparisons than just superimposing a max-search and a min-search.Andynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127921309972996082005-09-28T11:28:00.000-04:002005-09-28T11:28:00.000-04:00Are there any known results for circuits which onl...Are there any known results for circuits which only consist of xor gates?<BR/><BR/>Consider the following problem: we have n inputs, and n = p * p for some prime p. Each input can be specified as (x, y) for x, y in [0, p). We also have n outputs, referred to in the same way. The value of the (x, y) output is equal to the xor of each input (m, x + y * m) for m in [0, p).<BR/><BR/>There's no pair of inputs which are xored for two different outputs for this problem, so it's 'obvious' that the smallest number of xor gates which can be used to obtain the result is to simply do all the xors for each one, which leads to circuit complexity just under n * sqrt(n). It's also 'obvious' that using non-xor gates can't help compute the values any faster.<BR/><BR/>Clearly that second conjecture hasn't been proven, because it result in a superlinear circuit complexity. It seems like the first conjecture should be easy to prove though, but I can't get anywhere with it.<BR/><BR/>-BramAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127920785606229062005-09-28T11:19:00.000-04:002005-09-28T11:19:00.000-04:00On my understanding, Fortnow & co.'s method of 'ar...On my understanding, Fortnow & co.'s method of 'arithmetization' is both non-natural and nonrelativizing:<BR/><BR/>http://citeseer.ist.psu.edu/<BR/>babai91arithmetization.html<BR/><BR/>Basically, and with variations, the prover interpolates a low-degree polynomial through a boolean function, then runs an interactive proof to demonstrate a value or identity involving the polynomial. It works roughly because different low-degree polynomials are very different, and this difference is probabilistically detectable by the verifier.<BR/><BR/>It's nonrelativizing because the natural complete problems one can arithmetize (e.g. 3-SAT) are no longer complete under relativizations--their vocabulary fails to capture the dependence of a nondeterministic machine's behavior on exponentially many oracle bits. One can't hope to fix the technique because of Chang et al.'s result that IP^A doesn't contain coNP^A for random A; this is proved by standard techniques w/o reference to interpolation.<BR/><BR/>It's not 'natural' because it's just not a Razborov-Rudich hardness test for circuits (in any form I understand, at least). Its main thrust is to prove surprising class *equalities*. However, there is at least one nonrelativizing circuit lower bound that follows, see Burhman-Fortnow-Thierauf,<BR/>http://citeseer.ist.psu.edu/10573.html<BR/><BR/>How is this done? (The latter paper is short, so see for yourself..) Basically it's the same 'a bridge too far' method that Fortnow argues makes diagonalization a still-viable tool: class collapses combine powerfully with each other to produce further collapse; arithmetization is a collapsing technique; the assumed collapse one is trying to disprove then causes so much collapse that you contradict the classical (relativizable) hierarchy theorems.<BR/><BR/>As I see it, there's no particular reason to expect this particular technique to solve all complexity questions. To argue this, you might construct two oracle worlds that share the known equality results garnered by arithmetization yet differ as to whether e.g. P = NP.Andy Druckernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127899481903792822005-09-28T05:24:00.000-04:002005-09-28T05:24:00.000-04:00For me, Razborov-Rudich is a fascinating example o...For me, Razborov-Rudich is a fascinating example of "mining algorithms from a proof." Some logicians talk about this, for example <A HREF="http://www.math.cas.cz/~krajicek/ulrich.html" REL="nofollow"><BR/>Kohlebach</A> and <A HREF="http://www.brics.dk/DS/03/12/" REL="nofollow">Oliva</A>.<BR/>From what little I have seen, however, that work has not concentrated on discrete math and TCS. The Natural Proofs work,<BR/>in contrast, is a direct and <BR/>surprising application of that idea.<BR/>I suspect that the two communities<BR/>developed the idea independently,<BR/>but I don't know. <BR/><BR/>In my case, I do care, but at the<BR/>same time it seems hard to think<BR/>of any proof technique that does<BR/>not yield an efficient algorithm<BR/>yet is also good for separating<BR/>complexity classes.<BR/>You are left with counting <BR/>arguments of various types or diagonalization. <BR/><BR/>For a while I was<BR/>interested in Ehrenfeuct-Fraisse games, as there is a result showing that deciding the winner of such a game is PSPACE-complete in general. Therefore an algorithm mined from such a proof might be too expensive to act as an efficient distinguisher for a pseudo-random function. Unfortunately, that doesn't mean that the game used to separate a particular pair of complexity classes is hard to decide...so it's not clear what this means. Perhaps you could find a new proof of a result established via an EF game, but "pump up" the complexity of the game used for the separation? <BR/><BR/>Here is another question: is there any known proof technique which is both not natural and also does not relativize?David Molnarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127885200189954152005-09-28T01:26:00.000-04:002005-09-28T01:26:00.000-04:00Isn't the question of lower bounds still interesti...Isn't the question of lower bounds still interesting for algebraic circuits? Or does some Razborov-Rudich type obstruction exist for that situation too?<BR/><BR/>Rahul.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127883527775064572005-09-28T00:58:00.000-04:002005-09-28T00:58:00.000-04:00It amazes me that people seem sort of vaguely disi...It amazes me that people seem sort of vaguely disinterested in Razborov-Rudich. The proof doesn't strike me as any more complicate than say Blum-Micali-Yao. And it seems like it should give complexity theory some direction and something to grapple with. But instead people just seem to sort of not care.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127866463106881772005-09-27T20:14:00.000-04:002005-09-27T20:14:00.000-04:00I am surprised that you call the Boppana--Sipser s...I am surprised that you call the Boppana--Sipser survey up to date. I thought circuit complexity was more or less dead (or at least got a massive barrier to entry) after the Natural Proofs work of Razborov and Rudich, and this work appeared in 1994, well after the survey was written. <BR/><BR/>SivaD. Sivakumarhttps://www.blogger.com/profile/04674739621423058308noreply@blogger.com