tag:blogger.com,1999:blog-4975263359731311867.comments2010-12-15T15:01:29.233-05:0015-855: Intensive Intro to Computational ComplexityRyan O'Donnellhttp://www.blogger.com/profile/01760886084136827344noreply@blogger.comBlogger31125tag:blogger.com,1999:blog-4975263359731311867.post-85873621199019318482010-01-12T23:51:32.079-05:002010-01-12T23:51:32.079-05:00This comment has been removed by a blog administrator.wsxwhx660https://www.blogger.com/profile/14619553987450892051noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-89812248961612798772009-07-30T11:27:21.406-04:002009-07-30T11:27:21.406-04:00Dear Ryan,
It is due to Mike Sipser to the best ...Dear Ryan, <br /><br />It is due to Mike Sipser to the best of my knowledge. GilGil Kalainoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-76435967547645305892009-05-03T13:56:00.000-04:002009-05-03T13:56:00.000-04:00My notes for this aren't so polished; I'll email t...My notes for this aren't so polished; I'll email them to you.Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-39543268678645809722009-05-01T03:18:00.000-04:002009-05-01T03:18:00.000-04:00Al05: E. Allender et al. Power from Random Strings...Al05: E. Allender et al. Power from Random Strings<br /><br />BFNW93: L. Babai et al. BPP has subexponential time simulations<br />unless EXPTIME has publishable proofs.<br /><br />BM97: H. Buhrman and E. Mayordomo. An excursion to the Kolmogorov random strings.<br /><br />KC00: V. Kabanets and J.-Y. Cai. Circuit minimization problem.<br /><br />Ko91: K.-I Ko. On the complexity of learning minimum time-bounded turing machines.<br /><br />NW94: N. Nisan and A. Wigderson. Hardness vs randomness.Dafnahttps://www.blogger.com/profile/15699152399095970845noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-87309947869001708982009-04-30T18:14:00.000-04:002009-04-30T18:14:00.000-04:00Are there any notes that could be posted? (I had t...Are there any notes that could be posted? (I had to leave for a thesis defense.)Shiva Kaulhttps://www.blogger.com/profile/10496690820337439878noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-34049232858606821382009-04-30T17:10:00.000-04:002009-04-30T17:10:00.000-04:00You might be interested in reading my blog "Financ...You might be interested in reading my blog "Financial crisis? It's a pyramid, stupid."<br /><br />http://gregpytel.blogspot.com/<br /><br />Bascially I use basic complexity tools (growth of exponential function) and look at the current financial crisis from Cobham Thesis perspective. Any comments will be welcome.Greg Pytelhttps://www.blogger.com/profile/15749997788308388129noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-55254980559485530552009-04-10T09:35:00.000-04:002009-04-10T09:35:00.000-04:00Actually, the best known circuit size lower bound ...Actually, the best known circuit size lower bound for the standard basis (AND, OR, NOT) and an explicit (in NP) function is 5n - o(n), due to <A HREF="http://www.wisdom.weizmann.ac.il/~ranraz/publications/P5nlb.pdf" REL="nofollow">Iwama, Lachish, Morizumi, and Raz</A> (and their function is actually in P).Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-23275448357983937922009-03-06T17:08:00.000-05:002009-03-06T17:08:00.000-05:00This comment has been removed by the author.Shiva Kaulhttps://www.blogger.com/profile/10496690820337439878noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-51866736269492607782009-02-26T15:25:00.000-05:002009-02-26T15:25:00.000-05:00Homework hint requests will be taken, as usual, th...Homework hint requests will be taken, as usual, though no one ever seems to request them. For #4, the title is a hint; the correct advice should be a certain nonnegative integer.Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-14375363605455768562009-02-22T23:11:00.000-05:002009-02-22T23:11:00.000-05:00$a_b$$a_b$pranjalhttps://www.blogger.com/profile/02310973918876559133noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-3887677600757575482009-02-22T23:08:00.001-05:002009-02-22T23:08:00.001-05:00$a^b$$a^b$pranjalhttps://www.blogger.com/profile/02310973918876559133noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-75297499598745562432009-02-22T23:08:00.000-05:002009-02-22T23:08:00.000-05:00$A \subseteq B$$A \subseteq B$pranjalhttps://www.blogger.com/profile/02310973918876559133noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-63941541363242717972009-02-21T19:44:00.000-05:002009-02-21T19:44:00.000-05:00The connection between PRGs and circuit lower boun...The connection between PRGs and circuit lower bounds mentioned above should point to the following: <BR/><A HREF="http://www.cs.sfu.ca/~kabanets/Research/poly.html" REL="nofollow"><BR/>Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds</A>Venkatnoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-32249358208139466682009-02-21T19:39:00.000-05:002009-02-21T19:39:00.000-05:00We will most likely cover Nisan's PRG for small sp...We will most likely cover Nisan's PRG for small space machines and the Nisan-Wigderson generator for BPP machines in lectures. The post describes the high level connection between hardness and randomness used in the NW generator. To turn this idea into the construction of a useful generator, one needs to output more bits. This is done in the Nisan-Wigderson generator by applying the hard function to several (carefully chosen) subsets of bits of the seed s (so now the seed has to be somewhat longer than the input length of f). The subsets are picked to have limited intersection (i.e., from a "combinatorial design") and this is crucial to the very elegant analysis.<BR/><BR/>Unconditional PRGs for BPP machines are still unknown and constructing them is believed to be very hard. There is also formal evidence to this belief, as good PRGs for BPP would imply non-trivial circuit lower bounds. (We might cover <A HREF="" REL="nofollow">this connection</A> towards the end of the course.)<BR/><BR/>Cryptographic PRGs, where the output has to look random to machines that run in time in much greater than the time complexity of the PRG itself, imply the existence of one-way functions (and hence P not equal to NP). In the context of derandomization, the PRG can run in<BR/>time greater than the machine it is fooling, and so one might be able to get by with proving weaker circuit lower bounds. But even the weakest such lower bound which is necessary for derandomization seems very difficult to prove.Venkat Guruswaminoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-26862402014228559322009-02-17T15:37:00.000-05:002009-02-17T15:37:00.000-05:00And problem set 3 was handed out today and is also...And problem set 3 was handed out today and is also posted on the <A HREF="http://www.cs.cmu.edu/~odonnell/complexity/" REL="nofollow">course website.</A>Venkatnoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-3164661808841514122009-02-16T09:10:00.000-05:002009-02-16T09:10:00.000-05:00Really, no requests? I'm surprised. Guess it was...Really, no requests? I'm surprised. Guess it was an easy one. Just in case, here are a few hints: 1. completeness. 2. there is subtraction involved. 3. error reduction. 4. Show there is an NP machine N which, on input x, has a surviving branch for each sequence of oracle answers (for the P^NP machine on x) in which all the yes answers are confirmed. After Cook's Theorem, what is the lex-last satisfying assignment for N? 5. already has a hint. 6. already has hint/parts.Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-38790427340686606192009-02-14T19:03:00.000-05:002009-02-14T19:03:00.000-05:00Yes, good point Venkat. I forgot this is sometime...Yes, good point Venkat. I forgot this is sometimes called Concrete Complexity, which is a good name.<BR/><BR/>Also, there are way more branches of Complexity Theory :)Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-47128592149293954752009-02-13T15:07:00.000-05:002009-02-13T15:07:00.000-05:00Isn't this area sometimes referred to as "concrete...Isn't this area sometimes referred to as "concrete complexity" (perhaps motivated by fact that the lower bounds are for concrete, crisp problems)?Venkatnoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-69180284858895438482009-02-13T13:50:00.000-05:002009-02-13T13:50:00.000-05:00The lecture notes should keep being posted as the ...The lecture notes should keep being posted as the scribes finish them.a student in the classnoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-38757471520567720282009-02-12T13:38:00.000-05:002009-02-12T13:38:00.000-05:00This seems a reasonable place for homework hints. ...This seems a reasonable place for homework hints. Any requests?Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-13409752316946121542009-02-07T19:17:00.000-05:002009-02-07T19:17:00.000-05:00A few comments:. It's true that "random 3CNF formu...A few comments:<BR/><BR/>. It's true that "random 3CNF formula" are easy to solve by DPLL-style algorithms only for certain "clause densities". In fact, picking random 3CNFs with clause density around 4.2 is actually a great way to generate difficult-seeming SAT formulas. This is a fascinating area; here is just one possible quick survey, by CMU's own Abie Flaxman: http://www.math.cmu.edu/~adf/research/rand-sat-algs.pdf<BR/><BR/>. It is a very famous 1993 result of Feigenbaum and Fortnow that *no* NP-complete problem has a non-adaptive randomized self-reduction (like Discrete Log has) unless the Polynomial Hierarchy collapse. Getting rid of the "non-adaptive" constraint here has been a challenging problem with some positive results; see, e.g., this paper of Bogdanov and Trevisan:<BR/>http://www.cse.cuhk.edu.hk/~andrejb/pubs/redux-sicomp.pdf<BR/><BR/>. As Jeremiah says, Levin's theory is a bit hard to follow. After his initial work, Impagliazzo and Levin published an *equivalent* theory which is easier to understand: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=89604Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-6867519051114872852009-01-31T14:16:00.000-05:002009-01-31T14:16:00.000-05:00By the way, here are some homework hints: 3a) com...By the way, here are some homework hints: 3a) complete languages? 3b) padding. 4b) try showing it for Sigma_4, with diagonalization; 4c) there's already a hint.Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-63838364451641961242009-01-24T21:03:00.000-05:002009-01-24T21:03:00.000-05:00A succinct summary of known characterizations of v...A succinct summary of known characterizations of various complexity classes in terms of logics appears on Neil Immerman's page <A HREF="http://www.cs.umass.edu/~immerman/descriptive_complexity.html" REL="nofollow">here.</A>Venkat Guruswaminoreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-80242529280321988362009-01-24T12:58:00.000-05:002009-01-24T12:58:00.000-05:00Some remarks on Descriptive Complexity (aka Finite...Some remarks on Descriptive Complexity (aka Finite Model Theory): <BR/>1. To be a bit more precise, Fagin's theorem says a property of finite (relational) structures is in NP iff it's "definable" by an existential SOL (ESO) sentence. Evidently co-NP then corresponds to universal SOL (USO). So NP is different from co-NP iff there is a property of finite structures that is definable by USOL but not by ESOL or the other way round. More interestingly, not long after the Fagin theorem it's proved that for monadic SOL, i.e., when only unary predicates are involved, the existential and universal fragments can indeed be separated by simple properties, e.g., connectivity of a graph is definable by monadic-USO but not monadic-ESO. <BR/>2. Descriptive Complexity is concerned with ways of cooking up special logics to capture different complexity classes. A central question is, is there a logic that captures P? Surely if it's provable there is no such a logic, then P is not NP since NP is easily captured by ESO. People have different opinion on this issue, while many believe and try to prove it's impossible, some are seriously moving towards finding such a logic (surely different from ESO).Sean Gaohttps://www.blogger.com/profile/17687679611637666673noreply@blogger.comtag:blogger.com,1999:blog-4975263359731311867.post-53672558606369517012009-01-24T10:50:00.000-05:002009-01-24T10:50:00.000-05:00Update: Luca also discusses the result on his blo...Update: Luca also discusses the result on his blog here,<BR/><BR/>http://lucatrevisan.wordpress.com/2009/01/23/bounded-independence-ac0-and-random-3sat/<BR/><BR/>and makes some interesting connections to refuting random 3Sat and 3Xor formulas.Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.com