tag:blogger.com,1999:blog-37222332014-04-23T13:16:40.373-05:00Computational ComplexityComputational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill GasarchLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger2161125tag:blogger.com,1999:blog-3722233.post-18234549383512682532014-04-21T18:57:00.000-05:002014-04-21T18:57:15.622-05:00Changing the ORDER you teach things in might help A LOTI am teaching the undergrad jr/sr course Elementary Theory of Computation<br />
which is Reg Langs, Context free Langs, Computability theory, P and NP.<br />
<br />
Over the last few years I've changed some of the content (I dumped CFLs-- don't worry, they cover them some in the Prog Langs course) but more to my point today changed the ORDER I do things in<br />
<br />
<i>Change </i> 1: Do P and NP first and Computability later. While this is not historically accurate (which may be why the order was what it was)<br />
this is better pedagogically. Why? Consider the following reductions:<br />
<br />
1) Given a FORMULA phi produce a graph G and a number k such that<br />
phi is in SAT iff (G,k) is in CLIQ<br />
<br />
2) Given a MACHINE M_e produce a MACHINE M_i such that<br />
<br />
M_e(e) halts iff M_j halts on at least 10 numbers.<br />
<br />
Students have always found the second more confusing since the input and the output are both machines (and the reduction itself is done by a machine)<br />
where as the first one seems like a REAL transformation- you input a FORMULA<br />
and get out a GRAPH and a NUMBER.<br />
<br />
There are two other reasons to do P NP first:<br />
(1) Sometimes the last topic in a course gets short changed, and P NP is<br />
more important than Computability, so better if Computability gets short changed.<br />
(2) Lets say I could do P NP in either April or May. If I do it in April and someone resolves it in May, the students can get excited about it since they know about it. If I do it in May and its resolved in April then the students<br />
cannot share in the joy of the discovery. This reason may become more relevant in the year 2214. <br />
<br />
<i>Change</i> 2: I used to do the Cook-Levin Theorem (SAT is NP-complete) and<br />
then do a reduction like SAT \le CLIQ. This semester I did SAT \le CLIQ first<br />
and Cook-Levin later. Why? Because SAT\le CLIQ is better pedagogically (note- <i>pedagogically</i> is today's word on my word-of-the-day calendar) since the Cook-Levin reduction is harder and deals with Turing Machines as opposed to more familiar objects like Formulas and Graphs.<br />
<br />
More generally- the order you teach things in may matter, and changing it is relatively easy.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-75154044905073060282014-04-18T10:25:00.000-05:002014-04-18T10:25:30.245-05:00AnnouncementsTime for a short rundown of announcements.<br />
<br />
<ul>
<li><a href="http://www.columbia.edu/~cs2035/stoc/stoc2014/">STOC</a> will be held May 31-June 3 in New York City. Early registration and hotel deadline is April 30. Student travel support requests due by this Monday.</li>
<li>The newly renamed <a href="http://www.sigecom.org/ec14/">ACM Conference on Economics and Computation</a> (EC '14) will be held in Palo Alto June 8-12. Early registration deadline is May 15. Hotel deadline is May 19th but the organizers suggest booking early because Stanford graduation is June 13.</li>
<li>The <a href="http://computationalcomplexity.org/">Conference on Computational Complexity</a> will be held June 11-13 in Vancouver. Local arrangements information will be posted when available.</li>
<li>The ACM Transactions on Algorithms is <a href="http://talg.acm.org/talg-eic-call.v4.pdf">searching</a> for a new Editor-in-Chief. Nominations due May 16.</li>
<li>Several of the <a href="http://awards.acm.org/">ACM Awards</a> have been announced. Robert Blumofe and Charles Leiserson will receive the <a href="http://awards.acm.org/kanellakis/">Paris Kanellakis Theory and Practice Award</a> for their "contributions to robust parallel and distributed computing."</li>
<li>Belated congratulations to new <a href="http://www.sloan.org/fellowships/2014-sloan-research-fellows/">Sloan Fellows</a> Nina Balcan, Nayantara Bhatnagar, Sharon Goldberg, Sasha Sherstov, David Steurer and Paul Valiant.</li>
</ul>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-79111657529913973682014-04-17T07:13:00.000-05:002014-04-17T07:13:03.330-05:00Should you reveal a P = NP algorithm?<div class="tr_bq">
A reader asks</div>
<blockquote>
What would you do if you could prove that P=NP with a time-complexity of n<sup>2</sup> or better... moreover, would you publish it? </blockquote>
<blockquote>
There are all these statements of the good that could come of it. But how would the government react in its present state? Would it ever see the light of day? How would a person be treated if they just gave it away on the internet? Could a person be labeled a threat to national security for giving it away?</blockquote>
I consider this a completely hypothetical and unlikely scenario. If you think this applies to you, make sure you truly have a working algorithm. Code it up and mint yourself some bitcoins, but not enough to notice. If you can't use your algorithm to mint a bitcoin, you don't have a working algorithm.<br />
<br />
The next step is up to you. I believe that the positives of P v NP, like their use in curing diseases for example, greatly outweigh the negatives. I would first warn the Internet companies (like was done for <a href="http://en.wikipedia.org/wiki/Heartbleed">heartbleed</a>) so they can modify their systems. Then I would just publish the algorithm. Once the genie is out of the bottle everyone can use it and the government wouldn't be able to hide it.<br />
<br />
If you can find an algorithm so can others so you should just take the credit or someone else will discover it. I don't see how one can get into trouble for revealing an algorithm you created. But you shouldn't take legal advice from this blog.<br />
<br />
Once again though no one will take you seriously unless you really have a working algorithm. If you just tell Google you have an algorithm for NP-complete problem they will just ignore you. If you hand them their private keys then they will listen.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com9tag:blogger.com,1999:blog-3722233.post-56028825636129279132014-04-13T21:40:00.002-05:002014-04-16T11:49:42.827-05:00Factorization in coNP- in other domains?I had on an exam in my grad complexity course to show that the following set is in coNP<br />
<br />
FACT = { (n,m) : there is a factor y of n with 2 \le y \le m }<br />
<br />
The answer I was looking for was to write FACTbar (the complement) as<br />
<br />
FACTbar = { (n,m) | (\exists p_1,...,p_L) where L \le log n<br />
for all i \le L we have m < p_i \le n and p_i is prime (the p_i are not necc distinct)<br />
n =p_1 p_2 ... p_L<br />
}<br />
INTUITION: Find the unique factorization and note that the none of the primes are < m<br />
To prove this work you seem to need to use the Unique Factorization theorem and you need<br />
that PRIMES is in NP (the fact that its in P does not help).<br />
<br />
A student who I will call Jesse (since that is his name) didn't think to complement the set so instead he wrote the following CORRECT answer<br />
<br />
FACT = { (n,m) | n is NOT PRIME and forall p_1,p_2,...,p_L where 2\le L\le log n<br />
for all i \le L, m< p_i \le n-1 , (p_i prime but not necc distinct).<br />
n \ne p_1 p_2 ... p_L<br />
}<br />
(I doubt this proof that FACT is in coNP is new.)<br />
INTUITION: show that all possible ways to multiply together numbers larger than m do not yield n,<br />
hence n must have a factor \le m.<br />
<br />
Here is what strikes me- Jesse's proof does not seem to use Unique Factorization. Hence it can be used in other domains(?). Even those that do not have Unique Factorization (e.g. Z[\sqrt{-5}]. Let D= Z[\alpha_1,...,\alpha_k] where the alpha_i are algebraic. If n\in D then let N(n) be the absolute value of the sum of the coefficients (we might want to use the product of n with all of its conjugates instead, but lets not for now).<br />
<br />
FACT = { (n,m) : n\in D, m\in NATURALS, there is a factor y in D of n with 2 \le N(y) \le m}<br />
<br />
Is this in NP? Not obvious (to me) --- how many such y's are there.<br />
<br />
Is this the set we care about? That is, if we knew this set is in P would factoring be in P? Not obv (to me).<br />
<br />
I suspect FACT is in NP, though perhaps with a diff definition of N( ). What about FACTbar?<br />
I think Jesse's approach works there, though might need diff bound then log L.<br />
<br />
I am (CLEARLY) not an expert here and I suspect a lot of this is known, so my real point is<br />
that a students diff answer then you had in mind can be inspiring. And in fact I am inspired to<br />
read Factorization: Unique and Otherwise by Weintraub which is one of many books I've been<br />
meaning to read for a while.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com9tag:blogger.com,1999:blog-3722233.post-11720205411922777992014-04-09T16:24:00.000-05:002014-04-10T10:02:15.171-05:00Favorite Theorems: Extended FormulationsThe first couple of <a href="http://blog.computationalcomplexity.org/2014/01/favorite-theorems-introduction.html">favorite theorems</a> took place at the beginning of the last decade, but recent years have brought exciting results as well, such as the limitations of using linear programs to solve hard problems.<br />
<ul>
<li><a href="http://dx.doi.org/10.1145/2213977.2213988">Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds</a> by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf, STOC 2012 (<a href="http://arxiv.org/abs/1111.0837">ArXiv</a>).</li>
<li><a href="http://arxiv.org/abs/1311.2369">The matching polytope has exponential extension complexity</a> by Thomas Rothvoß. To appear in STOC 2014.</li>
</ul>
<div>
It all started with a paper by E.R. "Ted" Swart (the Deolalikar of the 80's) that claimed to show P = NP by giving a polynomial-time algorithm for Traveling Salesman based on linear programming. Yannakakis put the nail in that technique by <a href="http://dx.doi.org/10.1016/0022-0000%2891%2990024-Y">showing</a> that no symmetric linear program formulation can solve the traveling salesman problem. The TSP problem expressed as a linear program has many facets (multi-dimensional faces) but one could possibly have a higher dimensional polytope with a smaller number of facets that could project down to the TSP polytope. Yannakakis showed that these higher dimensional symmetric polytopes must still have many facets by showing an equivalence between the smallest number of facets and the monotone dimension of a slack matrix of the polytope describing the TSP.<br />
<br />
Not much happened since the 80's until Fiorini et al. generalized the Yannakakis result to give exponential lower bounds on the number of facets of general non-symmetric extensions of the polytope for traveling salesman. They combine Yannakakis' techniques with some <a href="http://dx.doi.org/10.1016/0304-3975%2892%2990260-M">communication lower bounds</a> due to Alexander Razborov. Their approach was inspired by quantum computing ideas but in the end they had a more conventional proof.<br />
<br />
Last fall Rothvoß showed even stronger exponential lower bounds for the matching polytope through a "substantial modification" of Razborov's work. Since matching is in P, Rothvoß showed that there are polynomial-time computable problems that can be formulated, but not succinctly formulated, as linear programs.<br />
<br />
There has also been <a href="http://dx.doi.org/10.1109/FOCS.2012.10">recent</a> <a href="http://dx.doi.org/10.1145/2488608.2488629">work</a> showing lower bounds approximating clique via linear programs.<br />
<br />
Ankur Moitra gave an <a href="http://people.csail.mit.edu/moitra/docs/tutorialf.pdf">excellent talk</a> at the recent <a href="http://blog.computationalcomplexity.org/2014/03/spring-breaking-at-dagstuhl.html">Dagstuhl</a> giving an overview of these results and the techniques involved. The next step: Show lower bounds for semidefinite programs.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-81307617827763471542014-04-07T07:50:00.004-05:002014-04-07T07:50:28.037-05:00How free is Randomness?Matthew Green had a great <a href="http://blog.cryptographyengineering.com/2014/03/how-do-you-know-if-rng-is-working.html">post</a> on the topic <i>how do you know a random number generator is working</i>. Gee, I just look at the sequence and see if it LOOKS random. Probably not the best idea. Actually people often found pattersn where there aren't any.<br /><br />
<i> </i><br />
Reminds me of a the following apocryphal story which would have to have taken place before everyone had a computer: A teacher assigns the class a HW assignment to flip a coin 600 times and record H's and T's. He warns them that if they just try to come up with a random sequence without flipping he will know. Sure enough, a few of them had sequences with NO runs of 6 or more H's or T's. He knows they are faked. One of the students fessed up that yes, he just wrote down H's and T's in a way that looked random. But another student claims that he DID flip the coins, but when he saw a sequence of 6 H's in a row he changed it since he THOUGHT the teacher would spot it and THINK it wasn't random.<br />
<br />
Is randomness a free resource? Papers in Complexity Theory strive to find good RNG's while papers in Crypto claim they already exist. Who is right?<br />
<br />
Faulty RNG's are surely a problem for crypto protocols. But are they a problem for randomized algorithms? People really do use randomized algorithms to test primes. What other algorithms do people in the real world routinely use randomness for? (Not counting crypto protocols).Is it ever a problem?<br />
<br />
I believe there are stories where a faulty RNG led to a crypto system being broken.<br />
<br />
Are there stories where a faulty RNG led to a randomized algorithm being wrong?GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-65704632165039415012014-04-04T10:45:00.002-05:002014-04-04T10:45:42.861-05:00How I learn a resultThere is a theorem I want to learn. How do I go about it? (How do YOU go about it?) I give an example here which also leads to pointers to some mathematics of interest.<br />
<br />
A division of a cake between n people is PROPORTIONAL (henceforth prop.)<br />
if everyone thinks they got (IN THEIR OWN MEASURE- AND PEOPLE CAN DIFFER WILDLY) at least 1/n. A division of a cake is ENVY FREE if everyone thinks they got the biggest (or tied) piece.<br />
<br />
There are two kinds of protocols- Discrete and Moving Knife. I discuss Discrete here.<br />
<br />
I had read several books on fair division (see <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cakebooks.pdf">here </a> for a review) and had some interest in the topic. In particular (1) I knew the (fairly easy) discrete 3-person Envy Free protocol, but did not know (2) the rather complicated discrete 4-person Envy Free Protocol. And I wanted to learn it! How to do I do that (this isn't quite advice on how YOU should do it, but I am curious what you think of what I do AND what you do.)<br />
<br />
<ol>
<li>Find a good source for it. I used the original article from the American Math Monthly. It is NOT always the case that the original source is the best (I discussed this in another <a href="http://blog.computationalcomplexity.org/2012/09/should-we-learn-from-masters-or-from.html">blog post.)</a></li>
<li>Create a REASON to learn it with a deadline. I both agreed to teach it in seminar AND I volunteered to do an HONORS COURSE (interdisciplinary) on Fair Division (nickname: Cake Cutting). The first time I taught the course I didn't get to the theorem (getting my feet wet in both HONORS courses and the material was a limiting factor) but I have in subsequent years.</li>
<li>While reading make HANDWRITTEN notes for the lecture I am going to give. I try to understand everything that I write down before going on, but sometimes, I have to go forward and then backward. I find myself redoing parts of the notes many times. The notes have many examples, pictures (which is why I don't type them initially), and counterexamples to check that the premises are needed. I check EVERY detail. What I present will be less detailed.</li>
<li>Type in the notes. (mine for 4-envyfree are <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/envyfree.pdf">here</a> ) For me, somehow, being forced to type it in I find corrections or better ways of saying or doing things. Also this produces notes for students or others. This MIGHT over time lead to survey articles or even textbooks but I DO NOT think in those terms. The notes that are produced are VERY GOOD FOR THE STUDENTS IN THE CLASS, or THE PEOPLE IN SEMINAR but NOT all that good for anyone else. (This may be why some textbooks are crap--- it is hard to turn class-specific notes into something anyone can use.)</li>
<li>TOSS OUT the handwritten notes. Knowing you will do this makes the typewritten version better. Also its hard to keep track of where one puts handwritten notes. I used to keep a math notebook but its hard to find anything in it.</li>
<li>In subsequent years when I teach the material I take my typewritten notes and make handwritten notes out of them. This force me to refresh on the material and I teach better if I can glance at notes that use large letters and symbols. If I do the course often enough I no longer need to. When I taught the Fair Division course in Fall 2013 I could do this proof off the top of my head.</li>
</ol>
There are some variants, Pros, and Cons of the above system:<br />
<br />
<ol>
<li> If the material is easy I may go straight to type and skip handwritten. This was the case for protocols for <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/prop.pdf">proportional cake cutting</a>.</li>
<li>I sometimes translate my notes, NOT to typed notes but to slides. There are some theorems whose ONLY writeup are my slides. I may or may not ever get them into notes (that's a tautology). I'll mention two but note that, even more than notes, slides are not really a good read unless you are taking the class. They are (1) An adaption of Mileti's proof of the infinite Canonical Ramsey Theory to the finite case- it gives pretty good bounds, though not the best known. Very good for teaching, so I may submit to <i>Journal of Pedagogical Ramsey Theory</i>. I am sure these slides contain a correct proof since I ran them by Mileti himself., who was surprised and delighted that someone got around to finitizing his proofs. The slides are <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/fcrmil1.pdf">here </a>and <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/fcrmil2.pdf">here.</a>(2) Using linear programming on some cake cutting problems. I doubt this is new, though I could not find it in the literature. I just did it for my class. Slides are <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/3lintalk.pdf">here.</a></li>
<li>If my GOAL is stuff for my class I may end up giving up. For example, I sort-of want to read the LOWER BOUND of Omega(nlogn) on number-of-cuts for n people, on prop. cake cutting due to Jeff Edmonds and Kirk Pruhs <a href="http://www.cse.yorku.ca/~jeff/research/">(this is Jeff Edmonds paper page)</a>. But the proof looks just a bit too hard for my students (recall- they are NOT math people, they are BRIGHT students from across majors). Knowing that I won't get to teach it to them I didn't quite have the motivation to look at it. I probably will someday--- for seminar.</li>
<li>If its not just one paper but an entire area of knowledge I try to find all the papers in the area and make a website out of them. This is easier in a limited area. My <a href="http://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html">Erdos Distance Problem Website</a> has only 10 papers on it (its prob missing a few), where as my <a href="http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/ramsey.html">Applications of Ramsey Theory to TCS website</a>Apps has 63 papers on it (I am sure its missing many). </li>
<li> One can get carried away with GATHERING papers as opposed to READING them.</li>
</ol>
What if you want to read a result, you begin, and its rather hard and/or you need a lot more background? There are several competing schools of thought:<br />
<br />
<ol>
<li>If at first you don't succeed, Try Try Again (credited to William Edward Hickson).</li>
<li>If at first you don't succeed, give up, Then Try Try again. Then quit. There's no point in being a damn fool about it (credited to W.C. Fields)</li>
<li>If at first you don't succeed then destroy all evidence that you tried.</li>
<li>If at first you don't succeed, skydiving is not for you.</li>
</ol>
The question of when to hold 'em, when to fold 'em, when to walk away, and when to run permeates life and mathematics as well as gambling. <br />
<ol></ol>
<br />
<br />
<ol></ol>
GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-66211644716139726282014-04-01T04:09:00.001-05:002014-04-01T04:11:15.117-05:00I am Bill Gasarch<div dir="ltr" style="margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: inherit; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; line-height: 1.15; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">I have a confession to make. Remember back in 2007 when I </span><a href="http://blog.computationalcomplexity.org/2007/03/end.html" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">retired</span></a><span style="background-color: transparent; color: black; vertical-align: baseline;"><span style="font-family: inherit;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> from the blog for about a year. I </span></span><span style="font-size: 15px; line-height: 17.25px; white-space: pre-wrap;">didn't</span><span style="font-family: inherit;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> actually retire at all but instead took the blog in a </span></span></span><a href="http://blog.computationalcomplexity.org/2007/03/complexity-blog-lives.html" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">new direction</span></a><span style="background-color: transparent; color: black; font-family: inherit; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; line-height: 1.15; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> by writing under the pseudonym William Ian “Bill” Gasarch, to be more playful and irreverent. All I had to do was be a little off the wall, add a FEW CAPITAL LETTERS and some mispellings and voila, same blog, new blogger. I’m especially proud of the </span><a href="http://blog.computationalcomplexity.org/2007/04/getting-8-year-old-interested-in.html" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">fake conversations</span></a><span style="background-color: transparent; color: black; font-family: inherit; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; line-height: 1.15; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> “Bill” had with his “relatives”. </span><br />
<span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"><br /></span>
<span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Now that I have come out, I’d like to thank Samir Khuller to help me set up a </span><a href="https://www.cs.umd.edu/~gasarch/" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="color: #1155cc; font-size: 15px; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">website</span></a><span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"> off Maryland’s CS page. The pictures of Bill are a friend of mine, a web programming consultant. Most of the rest of the links were plagiarized from the far corners of the Internet except for the </span><a href="https://www.cs.umd.edu/~gasarch/MYWRITINGS/god.html" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="color: #1155cc; font-size: 15px; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">God Play</span></a><span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">--wrote that one myself. </span><br />
<span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"><br /></span>
<span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">In 2008, I decided to </span><a href="http://blog.computationalcomplexity.org/2008/01/lance-20.html" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="color: #1155cc; font-size: 15px; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">return</span></a><span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"> to the blog as myself and also continue as Bill. Great fun switching context between the two personalities. I particularly enjoyed doing the </span><a href="http://blog.computationalcomplexity.org/2009/10/bill-and-lance-excellent-german.html" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="color: #1155cc; font-size: 15px; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">typecasts</span></a><span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"> with the two personalities talking to each other.</span><br />
<span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"><br /></span>
<span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">I have to admit Dick has done me </span><a href="http://rjlipton.wordpress.com/about-me/" style="font-family: inherit; line-height: 1.15; text-decoration: none;"><span style="color: #1155cc; font-size: 15px; text-decoration: underline; vertical-align: baseline; white-space: pre-wrap;">one better</span></a><span style="color: black; font-family: inherit; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">, with his teenage-chess-genius-turned-complexity-theorist alter ego Ken Regan.</span><br />
<span style="font-family: inherit;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: inherit;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;">I’m surprised how few people had caught on, after all how many of you have actually met Bill in person? But now that I have a respectable job, I realized it just </span></span><span style="font-size: 15px; line-height: 17.25px; white-space: pre-wrap;">wasn't</span><span style="font-family: inherit;"><span style="font-size: 15px; line-height: 1.15; white-space: pre-wrap;"> right for me to keep fooling the community.</span></span></div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-86142996591934936422014-03-27T07:14:00.000-05:002014-03-27T07:14:03.600-05:00Should We Have a TCS Ethics Board?We sometimes hear of the (rare) scientist who fakes data or results of experiments. In theoretical computer science one cannot fake a theorem, particularly an important result that will attract close scrutiny before publication in a conference or journal. But that doesn't mean we don't have academic improprieties from outright plagiarism to heated arguments over who should receive credit for a result.<br />
<div>
<br /></div>
<div>
If these issues involve submissions to a particular conference, journal or grant they generally get resolved through the program committee chair, editor-in-chief or program officer. But often these problems go beyond a particular venue.</div>
<div>
<br /></div>
<div>
What if we had a TCS Ethics Board composed of a few of the most trusted members of our community? For example, if two people argue whether or not they proved the same result independently, the board could first try to come to a mutually acceptable resolution and if that fails, make an independent assessment that could be used by PC chairs and EiCs.</div>
<div>
<br /></div>
<div>
For more egregious cases of intentional plagiarism and/or theft of ideas, the board could write a stern letter that would go the perpetrator's supervisor and possibly recommend banning that person from publishing in various TCS journal and conferences for a specified period of time.</div>
<div>
<br /></div>
<div>
The vast majority of TCS researchers are quite honest and to a fault share credit for their ideas, but every now and then some researchers, probably not even realizing they are acting unethically, create an atmosphere of distrust with their actions. An ethics board would show that we care about proper academic behavior and giving a confidential forum where people can address their grievances and hopefully resolve issues before, as had happened, driving people out of our field. </div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com13tag:blogger.com,1999:blog-3722233.post-67166434733671899622014-03-23T22:00:00.002-05:002014-03-23T22:00:22.709-05:00The answer is either 0,1, or on the board<br />
I have heard (and later told people) that the in a math course if you don't know the answer you should guess either <i>0</i> or <i>1</i> or <i>something on the board. </i>This works quite often.<br />
<br />
I have heard that in a course on history of theater you should guess either<br />
<i>the theater burned down </i> or <i>prostitution. </i> For example, the first musical<br />
was <a href="http://en.wikipedia.org/wiki/The_Black_Crook">The Black Crook</a> and it happened because of a fire (see the pointer).<br />
<br />
In upper level cell biology the guess is <i>If only we could solve the membrane problem.</i><br />
<br />
In a math talk you can always ask <i>is the converse true? </i>or <i>Didn't Gauss prove that? </i><br />
<br />
In computer science when someone asks me about a problem I say <i>Its probably NP-complete.</i><br />
<br />
In Christian Bible Study a good answer is either <i>Salvation </i>or <i>Jesus. </i>These are referred to as <i>Sunday school answers.</i><br />
<br />
If you know what the usual things to say in other fields is, please comment<i>.</i>GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com12tag:blogger.com,1999:blog-3722233.post-28584550628664952952014-03-20T01:33:00.003-05:002014-03-20T01:33:44.384-05:00Spring Breaking at Dagstuhl<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.dagstuhl.de/Gruppenbilder/14121.0.B.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://www.dagstuhl.de/Gruppenbilder/14121.0.B.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
It's spring break at Georgia Tech and time to head to Germany for the Dagstuhl Seminar <a href="http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=14121">Computational Complexity of Discrete Problems</a>. Lots of discussion on algebraic circuits, interactive coding, information complexity, pseudorandomness and <a href="http://www.dagstuhl.de/schedules/14121.pdf">much more</a>.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
This is a break for me, the ability to focus on complexity and research instead of hiring and administration. But even here, in rural Germany, one cannot completely escape the Internet and life back home.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Back in the states I'm hearing of the difficulty for theory students to find postdoc positions. Here I'm hearing of the difficulty of well-funded theory faculty in Europe finding postdocs. Not so bad to spend time on this side of the pond. Some of the positions are listed in the comments of the <a href="http://blog.computationalcomplexity.org/2013/10/2013-fall-jobs-post.html">fall jobs post</a>. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Want to organize your own Dagstuhl workshop? <a href="http://www.dagstuhl.de/en/program/dagstuhl-seminars/proposal/">Proposals</a> due by April 15. The Dagstuhl staff do an excellent job with most of the organizing, basically you just need to choose participants and talks.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The Dagstuhl library puts out the books authored by conference attendees and ask that authors sign those books. As this is the first Dagstuhl since <a href="http://goldenticket.fortnow.com/">The Golden Ticket</a> appeared, I carried on the tradition.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-FqudN9XogNw/UynlCz2_7eI/AAAAAAAAE9U/N-rlBNGGmLs/s1600/photo.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-FqudN9XogNw/UynlCz2_7eI/AAAAAAAAE9U/N-rlBNGGmLs/s1600/photo.JPG" height="150" width="200" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-34185168688995121622014-03-18T09:17:00.000-05:002014-03-19T07:25:52.533-05:00Leslie Lamport wins Turing Award!Leslie Lamport wins Turing Award!<br />
See <a href="http://cacm.acm.org/news/173049-acm-turing-award-goes-to-pioneer-who-advanced-reliability-and-consistency-of-computing-systems/fulltext">here </a>for more details.<br />
<br />
Leslie did work on reliability of systems and security that<br />
(according to the article) is ACTUALLY BEING USED. So Real People<br />
use his stuff.<br />
<br />
He also developed LaTeX (building on TeX) which we all know and most<br />
of us use. Academics use LaTeX but I honestly don't know how wide spread<br />
it is outside of academia. However, this could be the first time that a Turing award winner did something that I used DIRECTLY (I am sure I use RSA and other things indirectly). <br />
<br />
How well known is The Turing Award? its called `the nobel prize of computer science' but I think its far less well known than the Nobel Prize.<br />
<br />
The Fields Medal and he Mill Prize got a big publicity boost when Perelman turned them down. But that only got them 15 minutes of fame, including a Stephen Colbert segment `whose not honoring me now'. So I will not be urging Leslie Lamport to turn down his Turing Award in order to give it more fame.<br />
<br />
CONGRATULATIONS!GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-33249935107364533102014-03-13T08:44:00.000-05:002014-03-13T08:44:46.717-05:00Cosmos from Generation to GenerationDuring high school, well before the world-wide web with its bloggers and YouTube, out came a series <a href="http://en.wikipedia.org/wiki/Cosmos:_A_Personal_Voyage">Cosmos</a> that I watched religiously. Back then you had to watch a show when it was aired and no skipping of commercials, though Cosmos was a PBS (public-broadcasting) show so it didn't have any. Cosmos was hosted by the late great Carl Sagan. While I don't remember the contents of the show so much, I do remember being quite inspired by it and the show surely played a role in my future life as a scientist.<br />
<br />
I went to Cornell as an undergrad just a year after Cosmos' broadcast. Carl Sagan was a legend on campus, though I saw him just once, in a debate over Ronald Reagan's <a href="http://en.wikipedia.org/wiki/Strategic_Defense_Initiative">Star Wars</a> plan. Sagan did have an amazing house looking out over the Ithaca gorge that you could see from the suspension bridge I crossed every day.<br />
<br />
Now my younger daughter is in high school and Neil deGrasse Tyson takes on the difficult task of updating <a href="http://en.wikipedia.org/wiki/Cosmos:_A_Spacetime_Odyssey">Cosmos</a> for this new generation. Molly and I watched the first episode last night. (I'm still blown away we can watch when we want and skip the commercials.) It really brought back memories of the original show and I was really touched when Tyson talked about meeting Sagan as a high school student.<br />
<br />
Tyson is <a href="https://www.facebook.com/events/1476162692595961/">giving a talk</a> at Georgia Tech next month. Tickets went on sale yesterday and sold out within hours. Incredible to see the return of the scientific superstar.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-39912032763227451772014-03-10T09:55:00.000-05:002014-03-10T20:19:41.553-05:00Why do we think P NE NP? (inspired by Scott's post)Recently <a href="http://www.scottaaronson.com/blog?p=1720">Scott Posted</a> an excellent essay on reasons to think that P NE NP. This inspired me to post on the same topic. <i>Inspired </i>is probably the right word. Some of my post is copied and some of my post are my thoughts. A good test: if its intelligent and well thought out then its probably from Scott. <br />
<br />
Why do scientists believe any particular theory? I state three reasons, though there are likely more:<br />
(1) By doing Popperian experiments- experiments that really can fail. Their failure to fail helps to confirm the theory. This is common in Physics, though gets harder when the particles get smaller and string-like. (2) Great Explanatory power. Evolution is the main example here--- it's hard to do real experiments but one can look at the data that is already out there and find a theory that explains it all. (3) (Kuhn-light) It fits into the paradigm that scientists already have. This comes dangerously close to group think; however, if most of the people who have looked at problem X think Y, that should carry some weight.<br />
<br />
Can we do Popperian experiments for P vs NP? For that matter can we do Popperian experiments in Mathematics? Goldbach's conjecture and the Riemann Hypothesis seem to have good empirical evidence. Though that kind of reasoning gets me nervous because of the following true story: Let li(x) = int_0^x dt/ln t.<br />
Let pi(x) be the number of primes \le x. It is known that li(x) and pi(x) are VERY CLOSE. Empirical evidence suggested that li(x) \le pi(x) and this was conjectured. Skewes proved that there was an x for which li(x) \ge pi(x). His bound on x, the <a href="http://en.wikipedia.org/wiki/Skewes%27_number">the Skewes' number</a> ,was quite large, at one time the largest number to appear in a math paper (that record now belongs to <a href="http://en.wikipedia.org/wiki/Graham%27s_number">Graham's Number</a>). Then Littlewood, Skewes's advisor, showed that the sign of li(x)-pi(x) changes infinitely often. So the empirical evidence was not indicative.<br />
<br />
There might also be empirical tests you can do for continuous math, especially if its related to physics so you can do physics experiments.<br />
<br />
Have there been Popperian experiments to try to verify P NE NP? I am not quite sure what that means, but I do not think there have been (if I'm wrong please comment politely).<br />
<br />
So we move on to <i>Great Explanatory Power.</i> Are there many different empirical facts out there for which P NE NP would explain them and give a unifying reason? Does a bear... Well, never mind, the answer is YES! I give one examples (from Scott's post) and two more. But note that there are MANY MANY MORE.<br />
<br />
<ol>
<li>Set Cover problem: Given S_1,....S_m \subseteq {1,...,n} find the size of the smallest subset of S_1,...,S_m that covers the union of S_1,...,S_m. Chvatal showed in 1979 that one can find, i poly time, a subset of S_1,...,S_m that is (ln n)+OPT. Okay, great, an approximation. EMPIRICAL FACT: people seemed unable to improve on this at all. In 2013 Dana Moshkovitz <a href="http://people.csail.mit.edu/dmoshkov/papers/set-cover/set-cover-full.pdf">proved </a> that, assuming P\ne NP, this bound CANNOT be broken. Note that the algorithm of Chvatal and the lower bound of Moshkovitz have nothing to do with each other.</li>
<li>Vertex cover: given a graph find the smallest set of vertices so that every edge has one of them as an endpoint. There is an algorthm that gives 2OPT. There is one that does ever so slightly better: (2-(1/sqrt(log V))OPT. In 2005 Dinur and Safra <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/vc.pdf">proved</a> that, assuming P NE NP, there is no 1.36*OPT approximation. This does not match exactly but it still explains the lack of progress somewhat (more on this later when I discuss UQC).</li>
<li>Max 3-SAT: given a 3-CNF formula find an assignment that maximizes the number of clauses satisfied. Karloff and Zwick <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satu.pdf">proved</a> that there is an algorithm that finds an assignment satisfying (7/8)*OPT. Hastad <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf">proved</a> that, assuming P NE NP, (7/8)*OPT is the best you can do.</li>
</ol>
A bit more prosaic: P NE NP explains why people have had a hard time solving THOUSANDS OF PROBLEMS. I am most impressed with HAM CYCLE since mathematicians had been working on that one for quite some time--- trying to get a similar char to that of EULER circuit.<br />
<br />
So in summary, I find that P NE NP has GREAT explanatory power. That makes it a very compelling conjecture. Let us apply this test to other conjectures.<br />
<br />
<ol>
<li>Sigma_2 \ne Pi_2. Does this assumption explain anything? Our inability to find a circuit for SAT. I dont know what else it implies. Same for Sigma_i vs Pi_i. This might qualify as mini-kuhnian: Sigma_2\ne Pi_2 fits into how we view the world. </li>
<li>P=BPP. Almost every problem in BPP ended up falling into P over time. P=BPP would explain this. Also Nisan-Wigderson and its extensions make P=BPP fit into our world view.</li>
<li>Unique Game Conjecture. This explains many upper and lower bounds that match, though nowhere near that of P NE NP. One of them is the constant 2 for VC. Even so, I find that compelling. (One of Scott's commenters said that all of the lower bounds from UGC are actually unified some how, so its not quite as compelling.)</li>
<li>Factoring not in P. No real explanatory power here except that we seem to have a hard time finding an algorithm for Factoring. </li>
<li>Graph Isom not in P. Similar to Factoring not in P. </li>
</ol>
So, what are our reasons to think Sigma_2 \ne Pi_2?<br />
<br />
Lastly, mini-Kuhnian. What do people in the field think? The polls on P vs NP that I conducted in 2002 and 2012 (see <a href="http://www.cs.umd.edu/~gasarch/papers/papers.html">here</a>) indicate that believe that P NE NP is growing- roughly 60% in 2002, roughly 80% in 2012. Some of the commentators on Scott's blog took that 20% of P=NP people to be relevant.<br />
And indeed some of the P=NP people are both serious theorists and also not Dick Lipton (who seems to be who Lubos Motl points to) as a serious theorist who thinks P=NP).(ADDED LATER- SOME COMMENTERS HAVE INFORMED ME THAT LIPTON IS JUST OPEN TO THE POSS THAT P=NP. ) But some of those people emailed me that this was a protest vote, protesting the fields certainty that P=NP. I also note that three of them compared it to their voting or Ralph Nader in 2000, only with less drastic consequences.<br />
<br />
I personally don't take `what people think' that seriously, but because of my polls we actually know what people think, so I put it out there. <br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com15tag:blogger.com,1999:blog-3722233.post-58419589548954810282014-03-06T06:40:00.000-06:002014-03-06T06:57:32.919-06:00Favorite Theorems: Unique GamesMichel Goemans and David Williamson <a href="http://dx.doi.org/10.1145/227683.227684">made a splash</a> in the 90's using semidefinite programming to give a new approximation algorithm for the max-cut problem, a ratio of 2θ/(π(1-cos(θ)) minimized over θ between 0 and π, approximately 0.87856. Hard to believe that this ratio is tight, but it is assuming the <a href="http://blog.computationalcomplexity.org/2005/06/unique-games-conjecture.html">unique games conjecture</a>.<br />
<ul>
<li><a href="http://dx.doi.org/10.1137/S0097539705447372">Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?</a> by Subhash Khot, Guy Kindler, Elchanan Mossel and Ryan O’Donnell</li>
<li><a href="http://dx.doi.org/10.4007/annals.2010.171.295">Noise stability of functions with low influences: Invariance and optimality</a> by Elchanan Mossel, Ryan O’Donnell and Krzysztof Oleszkiewicz</li>
</ul>
The first paper showed that the Goemans-Williamson bound was tight assuming the unique games conjecture and a "majority is stablest conjecture", the last says very roughly that the most robust election scheme is a simple majority. The second paper, which followed soon thereafter, proved an invariance property that implies, among other things, that indeed majority is stablest.<br />
<br />
Khot and Oded Regev <a href="http://dx.doi.org/10.1016/j.jcss.2007.06.019">show</a> that under the unique games conjecture that essentially the best algorithm for approximating vertex cover is to take all the vertices involved in a maximal matching.<br />
<br />
Sanjeev Arora, Boaz Barak and David Steurer <a href="http://dx.doi.org/10.1109/FOCS.2010.59">describe an algorithm</a> that given a unique game where 1-δ fraction of the edges can be
satisfied, you can in time 2<sup>n<sup>poly(δ)</sup></sup>
find a coloring that satisfies a constant fraction of edges. This <a href="http://blog.computationalcomplexity.org/2010/03/unique-games-redux.html">may or may not</a> give evidence against the UGC.<br />
<br />
Luca Trevisan has a <a href="http://dx.doi.org/10.1090/S0273-0979-2011-01361-1">nice recent survey</a> on the unique games conjecture, covering much of the above and more, including beautiful connections between unique games and semidefinite programming.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-75505991957431638272014-03-04T10:07:00.000-06:002014-03-04T10:07:02.737-06:00Why are there so few intemediary problems in Complexity? In Computability?<br />
There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are<br />
in NP-P but are NOT NPC? Some candidates are Factoring, Discrete Log, Graph Isom, some in group theory, and any natural sparse set. See <br />
<a href="http://http://rjlipton.wordpress.com/2011/07/01/and-then-there-were-two/">here</a> for some more. <br />
<br />
A student asked me WHY there are so few natural intermediary problems. I don't know but here are some<br />
options:<br />
<br />
<ol><li> Bill you moron, there are MANY such problems. You didn't mention THESE problems (Followed by a list of problems<br />
that few people have heard of but seem to be intermediary.)<br />
<li> This is a question of Philosophy and hence not interesting.<br />
<li> This is a question of Philosophy and hence very interesting.<br />
<li> That's just the way it goes.<br />
<li> By Murphy's law there will be many problems that we can't solve quickly.<br />
</ol><br />
At least in complexity theory there are SOME candidates for intermediary sets.<br />
In computability theory, where we know Sigma_1 \ne \Sigma_0, there are no<br />
candidates for natural problems that are c.e., not decidable, but not complete. There have been some attempts to show that there can't be any<br />
such sets, but its hard to define ``natural'' rigorously. (There ARE sets that are c.e., not dec, not complete, but they are<br />
constructed for the sole purpose of being there. My darling would call them `dumb ass' sets,<br />
a terminology that my class now uses as well.)<br />
<br />
A long time ago an AI student was working on classifying various problems in planning. There was one that was c.e. and not decidable<br />
and he was unable to show it was complete. He asked me to help him prove it was not complete. I told him, without looking at it,<br />
that it was COMPLETE!!!!!!!!! My confidence inspired him to prove it was complete.<br />
<br />
So, aside from the answers above, is there a MATH reason why there are so few<br />
intermediary problems in Complexity, and NONE in computability theory?<br />
Is there some other kind of reason?GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-47765449343157782162014-02-27T07:18:00.001-06:002014-02-27T07:18:55.065-06:00Why Become a ProfessorSomeone took me to task because in November I <a href="http://blog.computationalcomplexity.org/2013/11/local-reductions.html">posted</a> that the CRA News had 50 pages of job ads but didn't note that very few of those ads specifically were searching for CS theory faculty. Yes, it is true that theory is not as high on the search agenda as big data and other applied areas, but many of these schools will hire theorists after they fail to find qualified applicants in the other areas. My advice is to apply widely and it's not too late to do so, as many CS departments are just starting their interview process.<br />
<br />
Why is it so hard for universities to hire in applied CS? Because you are not just competing against other universities, you are competing against industrial labs. Besides the usual arguments of typically hire base salary and no required teaching or grants, a place like Facebook or Google can give you access to data that you just can't get a university and your research will have a real-world impact faster than basic academic research.<br />
<br />
So why be a professor? Money isn't as big an issue as you expect, professors can consult, own significant portions of their IP (depending on the school) and can start companies. Teaching is time-consuming but extremely rewarding. To me there are two aspects that make being a professor the best job in the world.<br />
<br />
<ul>
<li>Freedom to set your own research agenda: Very few labs these days give you the freedom to choose your own research topics and even fewer will reward you for that. In academics we expect you to develop your own research areas and succeed in them. </li>
<li>Working with students: The relationship between advisor and advisee is not unlike a parent and child. And there's no better feeling than watching them succeed. You can often get summer interns and postdocs in industry but it just isn't the same.</li>
</ul>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-30182794927467933792014-02-23T16:33:00.000-06:002014-02-23T16:33:00.894-06:00When is a paper public? When is anything public?A while back I had a paper in an intermediary stage. The version posted to my Ramsey Theory Course Website was not final. Is the paper public? I didn't think about it much but I didn't intend it to be since it was not done yet. But Adam Sheffer's Google Scholar (more on that later) didn't know that. So his Google Scholar program found the paper and he blogged about it <a href="http://adamsheffer.wordpress.com/2013/07/27/subsets-with-distinct-volumes">here</a>.<br />
<br />
This was FINE- my co-author David Conlon posted a comment on the blog that a revised version was coming, and I asked Adam to modify the blog to say so as well. Plus, I am DELIGHTED and SURPRISED when someone noticed my work.<br />
When the final version came out Adam DID report about it <a href="http://adamsheffer.wordpress.com/2014/02/15/recent-results-feb-14/">here</a>.<br />
But it raises the question- when is a paper public? Some related thoughts<br />
<ol><li> (Kudos to Adam for pointing me to this one). I had heard the ABC conjecture might be solved. What I didn't quite know is that the author posted the papers on HIS OWN website, not on arXiv. Did he intend for it to go public? I do not know- but it is NOW public. If its not correct he can always say <i>well, I didn't tell you it was ready for<br />
prime time yet</i>.<br />
<li> A while back a student pointed me to a website with a paper that claimed to show GI is in P. The author DID NOT post it to arXiv (this may have been before there was an arXiv) nor did he email GI experts across the planet to look at it. So is it public? Is it my job to debunk it? It would be a bit odd to tell someone who didn't ask my opinion that YOUR PROOF IS WRONG! The student was hoping it was TRUE so he wouldn't have to learn the proof that if GI is NPC then PH collapses. I ended up telling the student that its surely wrong else since if GI was in P then I would known it--- not a really rigorous proof, but it sufficed. See <a href="http://blog.computationalcomplexity.org/2010/11/non-rigorous-proof-technique.html">here</a> for more on this non-rigorous proof technique.<br />
<li> I have read stories of people who post personal things on FaceBook (a common one is that they are gay) and then are shocked, shocked, when their parents find out.<br />
<li> There's a nice song about a related issue: <a href="http://www.youtube.com/watch?v=o_QePidL750&noredirect=1">My Mom's on Facebook</a>.<br />
<li> On the TV show West Wing there was a segment where someone thought a story was <i>just regional</i> and hence would not affect her confirmation hearing. She had to be told NO- there is no such thing as a story that is <i>just regional</i>. Journalists and others can FIND STUFF if it is out there.<br />
<li> Similarly to the last item: I can't post a paper <i>just for my class</i> because Google Scholar will find it (I DO NOT EVER require a password for a course website, I don't want to hassle the students and I am happy if somone else wants to see what I am teaching. Note also that this blog is NOT complaining that Adam found my paper). I (cordially) emailed Adam Sheffer inquiring how Google Scholar found me. For my fellow Luddites I reprint his answer (hmmm, I don't know if he meant his email to be public.)<br />
<blockquote>Regarding how Google Scholar works: The system constantly scans the web for new papers. It knows the papers which I have coauthored (it finds them while searching the web and asks me to verify that they are indeed mine). Then, in future scans, if it stumbles upon a paper that might be relevant to me - it sends me and update about it. I am not sure what exactly are the criteria that it uses, but it seems to be papers by my coauthors and papers on similar topics (perhaps papers that have common references with my papers?).<br />
</blockquote>Sound like when TIVO tried to guess what shows you liked- it could be right but it could be far off. I know of liberals who watched FOX news a lot to gain insight into what people they disagree with thought, and then their TIVO thought were Tea Partiers. Then TIVO thought they liked Tea.<br />
<li> I gave Adam kindly blogger-to-blogger advice: DO NOT let this be a cautionary tale. Do not ask permission to post about a PAPER --- just do it. I've done it <a href="http://blog.computationalcomplexity.org/2013/08/what-are-galois-games.html">here</a> when blogging about Galois games and <a href="http://blog.computationalcomplexity.org/2013/08/how-much-trig-does-your-governor-know.html">here</a> when blogging about how much trig should a governor know. If you post on something a bit more personal (e.g., <a href="http://blog.computationalcomplexity.org/2011/12/romney-vs-aaronson.html">here</a>) then maybe you should get permission (one of the people gave permission, the other never responded).<br />
</ol><br />
So what to make of all this? We are in a time of transition and some people<br />
may end up revealing more than they intended. The next generation may learn;<br />
however, we seem to always be in a time of transition.<br />
"p.html" 31L, 4785C written GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-16465190708441223512014-02-19T16:11:00.000-06:002014-02-19T16:11:33.086-06:00Analog Adventures<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.wired.com/images_blogs/photos/uncategorized/2008/09/09/dmg_2.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://www.wired.com/images_blogs/photos/uncategorized/2008/09/09/dmg_2.jpg" height="320" width="244" /></a></div>
I was 11 forty years ago when <a href="http://en.wikipedia.org/wiki/Dungeons_%26_Dragons">Dungeons and Dragons</a> first appeared and by high school many of my friends spent far too many hours embarking on those fantasy adventures. I didn't play much myself only joining a few campaigns for a short period of time. Nevertheless the game hit its mark, giving escapism to our inner nerdoms.<br />
<br />
I just finished a new book on D&D <a href="http://www.amazon.com/gp/product/B008J4CHX2/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=B008J4CHX2&linkCode=as2&tag=computation09-20">Of Dice and Men</a> by David Ewalt. Ewalt tells three interlocking stories: The history of D&D, Ewalt's personal journey into the game, and some campaigns he's embarked on from the characters' point of view. Gary Gygax and Dave Arneson originally created the game but Dave soon left the company and was written out of the books. Gary mismanaged the company which has bounced around from various owners every since. I hadn't really kept up with D&D after college and I'm surprised that it has so many incompatible versions (reminds me of LaTeX and Python). A fifth version of D&D to unite them all is due for release this summer.<br />
<br />
My daughter's school just put on a production of <a href="http://www.amazon.com/gp/product/0573700567/ref=as_li_ss_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0573700567&linkCode=as2&tag=computation09-20">She Kills Monsters</a>, a play about a woman who discovers her late sister through the sister's D&D adventures. My daughter played an evil cheerleader and her line "We're way too powerful for you" reminded us both of her <a href="https://www.youtube.com/watch?v=HjUEEHTyhdA">classic role as NP</a>.<br />
<br />
These days we have immersive rich interactive games on our Play Stations and smart phones but still there is still nothing like gathering around a table transformed into a tavern as we meet our fellow adventurers and embark on the next quest.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-13152647334474741702014-02-17T07:40:00.000-06:002014-02-17T07:40:20.542-06:00Maryland looking for a Lecturer/Who teachers your intro courses?My chairman, Samir Khuller, asked me to post our job posting for a lecturer to my blog, so I and doing it right <a href="https://www.cs.umd.edu/job/2014/lecturer-position-full-time">now</a>. I think he overestimates the power of this blog.<br />
<br />
At Univ of MD at College Park lecturers teach most sections of our intro sequence (CS1, CS2, CS3, Discrete Math). They might sometimes do a higher level course if the need arises. They are there to mostly teach and advise students, not do research, though some do and that's certainly fine. Some have PhD's and some don't. Note that this is a full time job--- these are not adjuncts or rent-a-profs. They are part of the department.<br />
<br />
Is having lecturers teach the intro courses a good idea? Overall YES; however, I would like to have professors teaching those courses once in a while, or be involved once in a while, as they may have a good idea to share with the lecturer (then again, they might not). Having said that, you don't see me volunteering for CS1, CS2, or CS3 (My policy: I never teach a course where I would get a B if I took it. One exception- I did once teach Graduate Algorithms and got in a bit over my head.) I do teach Discrete Math once in a while. I also like to proofread the midterm and final of whoever is teaching it. I'm NOT that good a proofreader, but I like to know what they are up to and it gives me an excuse to talk to them about the course and make sure it doesn't drift to much. I would like to think I have a good rapport with the lecturers.<br />
<br />
Does having a PhD in CS and being a professor give one some insights on what should be in CS1,2,3 and how to teach it? I honestly don't know. My first semester at Univ of MD (1985) we were teaching program verification in CS1. I knew immediately it was a bad idea and eventually (without any input from me) the dept stopped doing that. This is a case where being a researcher may be a negative with regard to education.<br />
<br />
I would like to think that my working in theory helps me teach Discrete Math. It does as a source of some problems (e.g, if a paper says `by an easy induction...' that can be a problem set) but one should not get to carried away and go over their heads.<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-13926889316957349662014-02-12T15:47:00.003-06:002014-02-14T07:38:59.434-06:00IEEE and the Conference on Computational ComplexityDieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a <a href="http://computationalcomplexity.org/forum/">forum</a> to discuss the future affiliation of the conference. Read over the <a href="http://computationalcomplexity.org/documents/affiliation_manifesto_ccc13.pdf">manifesto</a> and <a href="http://computationalcomplexity.org/forum/update-since-june-2013/">update</a>. You can give general comments on the <a href="http://computationalcomplexity.org/forum/about/">about post</a>. Dieter discusses three options:<br />
<br />
<ol>
<li>Remain with IEEE</li>
<li>Have a joint ACM/IEEE conference in some fashion.</li>
<li>Become an unaffiliated conference.</li>
</ol>
<div>
For most of you this shouldn't matter at all. Most of you readers have never attended the complexity conference (though you ought to give it a try sometime) and those that do would probably continue attending no matter who sponsors the meeting.</div>
<div>
<br /></div>
<div>
There has been a go-it-yourself tendency in this field so as not to pay any organization fees and to publish papers in an open-access format. Just realize this approach has some potential downfalls.</div>
<div>
<ul>
<li>Without a sponsor, the conference and in particular the organizing committee, is fully responsible for any deficit. One bad hotel contract can sink a conference. To guard against this, you'll need to budget a surplus far larger than IEEE or ACM would require. Also IEEE and ACM can use their influence to get better deals such as on hotels. </li>
<li>You'll need considerably more volunteer time from faculty to handle the larger administrative load. This time doesn't show up in the financial calculation but it is a real expense.</li>
<li>Having a sponsoring organization gives a set of checks and balances to guarantee that the conference retains a consistent mission and be fiscally responsible. If a conference is solo and the organizing committee drops the ball, the conference just disappears. </li>
</ul>
<div>
I'm not recommendation here, just trying to point out some pitfalls that usually don't get discussed. I'll stay out of the actual debate on the future sponsorship of CCC and leave that to the younger generation.</div>
</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com11tag:blogger.com,1999:blog-3722233.post-18687636802885935752014-02-09T21:52:00.000-06:002014-02-09T21:52:14.785-06:00Superbowl underdogs and overdogs(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a `big game sale on beer'. I will get around this the same way he does. I hope he doesn't sue.) <br />
<br />
In Superb owl XLVIII (48) (one of the few uses of Roman Numerals left) Denver was the favorite but got beaten. This is not so unusual and they were not a favorite by much-just 2.5 points. But they lost 43-8. That sounds unusual--- for the favorite to get completely whomped (spellcheck thinks that's not a word, but spellcheck doesn't even think spellcheck is a word).<br />
<br />
So- how uncommon is it for the favorite to get whomped? We would need a rigorous definition of whomped. I'll say two touchdowns, or 14 points. A list of all of the superb owl games and what the spread was and what happened <a href="http://www.vegasinsider.com/nfl/superbowl/history/">is here</a>. I summarize:<br />
<br />
<ol>
<li>The underdog WON 15 times. The most surprising was probably when the NY Jets were an 18-point underdog to the Baltimore Colts in Supeb owl III in 1969 and won 16-7. Good thing they won since Joe Namath (the NY Jets QB) guaranteed victory.</li>
<li>In 2010, Superb owl 44, Indianapolis was a 5 points favorite over the New Orleans Saints but the Saints whomped 31-17.</li>
<li>In 2003, Superb owl 37, Tampa Bay was a 4 point underdog to Oakland. Tampa Bay whomped by winning 48-21.'</li>
<li>In 1988, Supeb owl 22, Washington was a 3 point underdog to Denver, but Washington whomped 42-10.</li>
<li>In 1984, Superb owl 18, LA was a 3-point underdog to Washington, but LA whomped 38-9.</li>
<li>In 1981, Superb owl 15, Oakland was a 3 point underdog to Philadelphia, but Oakland Whomped 27-10.</li>
<li>In 1970, Superb owl 4, Kansas City was a 12 point underdog to Minnesoda, but whomped 23-7. The reason they were an underdog is that people still though the AFC to be the lesser league and didn't remember that in Superb Owl 3 the AFC won (though didn't whomp).</li>
</ol>
So the underdog has whomped 5 times. That is FAR MORE than I would have thought. Does this show that underdogs are undervalued? Not sure since if an underdog wins it doesn't matter by how much for the betting, where as if a favorite wins it matters by how much for the point spread.<br />
<br />
This may also call into question if point-spread is the best way to express `this teams is that much better than that team'. One issue (though it was NOT an issue in Superb owl 48) is that if a team is behind<br />
then they may use a high-risk high-reward strategy which, if it fails, they lose my a lot. The phrase one may hear is ``the game was closer than the score''. Note that for baseball they don't do point spreads, they do odds instead. Should Football follow that? What are the PROS and CONS of points spread vs odds?<br />
<br />
The cliche is `I watch the game for the commercials' I actually skip the game and watch the `best of superb owl commercials' that come the week before the game. <br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-22065510975708788022014-02-06T07:46:00.000-06:002014-02-06T07:46:39.147-06:00Favorite Theorems: Connecting in Log SpaceWe start the favorite theorems with a result that might surprise many is still less than ten years old.<br />
<br />
<div style="text-align: center;">
<a href="http://dx.doi.org/10.1145/1391289.1391291">Undirected Connectivity in Log-Space</a> by Omer Reingold (<a href="http://research.microsoft.com/pubs/148550/sl.pdf">PDF</a>)</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze. Reingold's algorithm builds an expander graph based on the <a href="http://www.jstor.org/stable/3062153">zig-zag construction</a> in a very clever way that uses very little space to construct and to check that two points connect.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
In 1979, Aleliunas, Karp, Lipton, Lovász and Rackoff <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.34">showed</a> that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. My <a href="http://blog.computationalcomplexity.org/2004/12/favorite-theorems-derandomizing-space.html">last favorite theorem</a> from 2004 talked about derandomizing space algorithms and before Reingold the best algorithm for s-t connectivity required log<sup>4/3</sup> space. Indepently of Reingold, Vladimir Trifonov <a href="http://dx.doi.org/10.1137/050642381">gave</a> a O(log n log log n) space algorithm for s-t connectivity, a victim of bad timing.<br />
<br />
One neat implication of Reingold's result is a new and simpler characterization of log-space as the set of problems expressible in first-order logic with ordering and symmetric transitive closure.<br />
<br />
After Reingold's result we might have expected solutions to a number of related problems but we didn't see much progress.<br />
<ul>
<li>Can every randomized log-space algorithm be derandomized in log space?</li>
<li>Do there exist log-space computable universal traversal sequences? </li>
<li>Can we solve directed s-t connectivity better than <a href="http://blog.computationalcomplexity.org/2005/07/favorite-theorems-p-np-for-space.html">Savitch</a>? </li>
<li>Can we modify Reingold's algorithm to bring log space into NC<sup>1</sup>?</li>
</ul>
</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-68170872147699772872014-02-03T07:02:00.003-06:002014-02-03T07:06:24.676-06:00Contribute to the Martin Gardner CentennialDana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments <a href="http://martin-gardner.org/Testimonials.html">here</a>. I left a comment there, but I expand it for this blog entry.<br />
<br />
When I got interested in mathematics in high school I went to the public library looking for math books (this was before Al Gore invented the internet). I found some books by Martin Gardner and began reading them. They were just right for the level of math I was on at the time. My very first proof that I read on my own (outside of a class) was in those books- the proof that (in the terminology I use now) a graph is Eulerian iff every vertex has even degree.<br />
<br />
I learned about SOMA cubes (I bought a set and did every puzzle in the book in about 2 days.This is the only evidence that as a kid I was good at math). I learned the unexpected hanging paradox which confused me then (and still does). I learned the hercules-hydra game and other games that go on for a LOOOOOOOOOONG time. They are related to things in logic. I also learned about NIM games which I have used as a starting point for several student projects.<br />
<br />
There have been some conferences in his honors, the Gathering-for-Gardner. I had the pleasure of reviewing some of the books from it. (My review is <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/gardnergath.pdf">here</a>.) These articles show that while his work was recreational this is not a well defined term- some if relates to very important and deep mathematics, and some deep math has arisen from such problems. The books also have articles about Gardner the Magician.<br />
<br />
In the 2000's some of his books were reprinted and I was asked to review them for my SIGACT News book review column. I took this opp to do a joint review of several math recreational books. What a delight to reread his books and contrast them to those of his successors. And I STILL learned some math that I didn't know from them. (My review is <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/bygardner.pdf">here</a>.)<br />
<br />
Shortly before a column appears I always email the authors-of-books, authors-of-reviews, and publishers a first draft of my column. His publisher told me that he didn't use email (he was in his 90's!) so I postal mailed him my review. He read it, corrected some typos, but otherwise was quite happy with the review. He died a few months later. I was happy to have some contact, albeit short, with the man who helped keep me interested in math in high school and beyond.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-5970520739803230102014-01-29T14:52:00.000-06:002014-01-29T14:52:24.527-06:00Snow Days<div class="separator" style="clear: both; text-align: left;">
An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many others just abandoned their cars, or slept in them. I'm talking about Valentine's Day, February 14, 1990 in Chicago. But the same story hit Atlanta yesterday. One big difference--Georgia Tech is closed today and tomorrow because the city can't handle the ice. The University of Chicago was open on February 15th. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
When these events happen, people wonder about the planning. Was it wise for all schools and businesses to shut down about the same time, early yesterday afternoon? Lots of blame to go around (and having CNN based in Atlanta <a href="http://www.cnn.com/2014/01/29/us/atlanta-traffic-hell-why/index.html">guarantees coverage</a>) but it is not clear that any plan would have done much better--how do you get millions of people safely home with dangerous roads and a limited public transit system? One of these times you wish P = NP and you can just find the right algorithm. One of the issues is that freak mid-day snowstorms don't happen that often, the last major one in Atlanta was 1982.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Meanwhile back in Chicago, schools were closed earlier this week, not for snow but for cold. But it was that cold on a regular basis back in the 90's. Global warming has changed expectations, as so brilliantly illustrated in this <a href="http://xkcd.com/1321/">xkcd</a>. </div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://imgs.xkcd.com/comics/cold.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://imgs.xkcd.com/comics/cold.png" height="320" width="316" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com3