tag:blogger.com,1999:blog-37222332015-03-27T11:03:36.532-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.comBlogger2260125tag:blogger.com,1999:blog-3722233.post-43401636535606759392015-03-25T13:10:00.000-05:002015-03-25T13:10:49.472-05:00News AplentyBoth the Turing Award and the Abel Prize were announced this morning.<br />
<br />
MIT databases researcher Michael Stonebraker <a href="http://preview.acm.org/2014-turing-award">wins the ACM Turing Award</a>. He developed INGRES one of the first relational databases. Stonebraker is the first Turing award winner since the prize went up to a cool million dollars.<br />
<br />
John Nash and Louis Nirenberg <a href="http://www.abelprize.no/nyheter/vis.html?tid=63589">share this years Abel Prize</a> “for striking and seminal contributions to the theory of nonlinear partial differential equations and its applications to geometric analysis.” This work on PDEs is completely independent from the equilibrium results that won Nash the 1994 Nobel Prize.<br />
<br />
Earlier this week the CRA released their latest Best Practice Memo: <a href="http://cra.org/resources/bp-view/best_practices_memo_evaluating_scholarship_in_hiring_tenure_and_promot">Incentivizing Quality and Impact: Evaluating Scholarship in Hiring, Tenure, and Promotion</a>. In short: Emphasize quality over quantity in research.<br />
<br />
The NSF announced their <a href="http://www.nsf.gov/news/special_reports/public_access/">public access plan</a> to ensure that research is "available for download, reading and analysis free of charge no later than 12 months after initial publication".Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-1952925513089465012015-03-22T21:35:00.000-05:002015-03-22T21:35:50.034-05:00Which mathematician had the biggest gap between fame and contribution?(I was going to call this entry <i> Who was the worst mathematician of all time? </i>but Clyde Kruskal reminded me that its not (say) Goldbach's fault that his conjecture got so well known, in fact its a good thing! I'll come back to Goldbach later.) <br />
<br />
Would Hawking be as well known if he didn't have ALS? I suspect that within Physics yes, but I doubt he would have had guest shots on <i>ST:TNG, The Simpsons, Futurama, and The Big Bang Theory</i> (I just checked the IDMB database- they don't mention Futurama but they do say he's a Capricorn. I find that appalling that they mention a Scientists Horoscope.) I also doubt there would be a movie about him.<br />
<br />
Would Turing be as well known if he wasn't gay and didn't die young (likely because of the ``treatment'') would he be as well known? I suspect that within Computer Science yes, but I doubt there would be a play, a movie, and there are rumors of a musical. Contrast him with John von Neumann who one could argue contributed as much as Turing, but, alas, no guest shots on I Love Lucy, no movie, no Rap songs about him. (The only scientist that there may be a rap song about is Heisenberg, and that doesn't count since it would really be about Walter White.)<br />
<br />
Hawking and Turing are/were world class in their fields. Is there someone who is very well known but didn't do that much? <br />
<br />
SO we are looking for a large gap between how well known the person is and how much math they actually did. This might be unfair to well-known people (it might be unfair to ME since complexityblog makes me better known than I would be otherwise). However, I have AN answer that is defensible. Since the question is not that well defined there prob cannot be a definitive answer.<br />
<br />
First lets consider Goldbach (who is NOT my answer). He was a professor of math and did some stuff on the Theory of curves, diff eqs, and infinite series. Certainly respectable. But if not for his<br />
conjecture (every even number is the sum of two primes- still open) I doubt we would have heard of him.<br />
<br />
My answer: Pythagoras! He is well known as a mathematician but there is no evidence that he had any connection to the theorem that bears his name.<br />
<br />
Historians (or so-called historians) would say that it was well known that he proved the theorem, or gave the first rigorous proof, or something, but there is no evidence. Can people make things up out of whole cloth? Indeed they can.<br />
<br />
Witness this <a href="https://www.youtube.com/watch?v=bnROB_RCF7U">Mr. Clean Commercial</a> which says: <i>they</i> <i>say that after seeing </i>a <i>magician make his assistant disappear Mr Clean came up with a product that makes dirt disappear- the magic eraser.</i> REALLY? Who are ``they''? Is this entire story fabricated? Should we call the FCC :-) ANYWAY, yes, people can and do make up things out of whole cloth and then claim they are well known. Even historians.<br />
<br />
Commenters: I politely request that if you suggest other candidates for large gap then they be people who died before 1950 (arbitrary but firm deadline). This is not just out of politeness to the living and recently deceased, its also because these questions needs time. Kind of like people who want to rank George W Bush or Barack Obama as the worst prez of all time--- we need lots more time to evaluate these things.<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com15tag:blogger.com,1999:blog-3722233.post-7436931793636524492015-03-19T08:58:00.001-05:002015-03-19T08:58:51.962-05:00Feeling UnderappreciatedAs academics we live and die by our research. While our proofs are either correct or not, the import of our work has a far more subjective feel. One can see where the work is published or how many citations it gets and we often say that we care most about the true intrinsic or extrinsic value of the research. But the measure of success of a research that we truly care most about is how it is viewed within the community. Such measures can have a real value in terms of hiring, tenure, promotion, raises and grants but it goes deeper, filling some internal need to have our research matter to our peers.<br />
<br />
So even little things can bother you. Not being cited when you think your work should be. Not being mentioned during a talk. Seeing a review that questions the relevance of your model. Nobody following up on your open questions. Difficulty in finding excitement in others about your work. We tend to keep these feelings bottled up since we feel we shouldn't be bragging about own work.<br />
<br />
If you feel this way a few things to keep in mind. It happens to all of us even though we rarely talk about it. You are not alone. Try not to obsess, it's counterproductive and just makes you feel even worse. If appropriate let the authors know that your work is relevant to theirs, the authors truly may have been unaware. Sometimes it is just best to acknowledge to yourself that while you think the work is good, you can't always convince the rest of the world and just move on.<br />
<br />
More importantly remember the golden rule, and try to cite all relevant research and show interest in other people's work as well as your own.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-73299330028082239252015-03-15T21:25:00.001-05:002015-03-15T22:54:30.452-05:00Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP?<br />
When I was young and foolish and I heard that someone thinks they proven P=NP or P ≠ NP I would think <i>Wow- maybe they did!</i>. Then my adviser, who was on the FOCS committee, gave me a<i> paper that claimed to resolve P vs NP! </i> to review for FOCS. It was terrible. I got a became more skeptical.<br />
<br />
When I was older and perhaps a byte less foolish I would think the following: <br />
<br />
For P=NP proofs: I am sure it does not proof P=NP BUT maybe there are some nice ideas here that could be used to speed up some known algorithms in practice, or give some insights, or something. Could still be solid research (A type of research that Sheldon Cooper has disdain for, but I think is fine).<br />
<br />
and<br />
<br />
For P ≠ NP proofs: I am sure it does not prove P ≠ NP BUT maybe there are some nice ideas here, perhaps a `if BLAH than P ≠ NP', perhaps an nlog^* lower bound on something in some restricted model'.<br />
<br />
Since I've joined this blog I've been emailed some proofs that claim to resolve P vs NP (I also get some proofs in Ramsey Theory, which probably saves Graham/Rothchild/Spencer some time since cranks might bother me instead of them). These proofs fall into some categories:<br />
<br />
P ≠ NP because there are all those possibilities to look through (or papers that are far less coherent than that but that's what it comes down to)<br />
<br />
P=NP look at my code!<br />
<br />
P=NP here is my (incoherent) approach. For example `first look for two variables that are quasi-related' What does `quasi-related' mean? They don't say.<br />
<br />
Papers where I can't tell what they are saying. NO they are not saying independent of ZFC, I wish they were that coherent. Some say that its the wrong question, a point which could be argued intelligently but not by those who are writing such papers.<br />
<br />
OKAY, so is there ANY value to these papers? Sadly looking over all of the papers I've gotten on P vs NP (in my mind- I didn't save them --should I have?) the answer is an empirical NO. Why not? I'll tell you why not by way of counter-example:<br />
<br />
Very early on, before most people know about FPT, I met Mike Fellows at a conference and he told me about the Graph Minor Theorem and Vertex Cover. It was fascinating. Did he say `I've solved P vs NP' Of course not. <i>He knew better.</i><br />
<br />
Taking Mike Sipers's Grad Theory course back in the 1980's he presented the recent result: DTIME(n) ≠ NTIME(n). Did Mike Sipser or the authors (Paul, Pippenger, Szemeredi, Trotter) claim that they had proven P vs NP? Of course not, <i>they knew better</i><br />
<br />
Think of the real advances made in theory. They are made by insiders, outsiders, people you've heard of, people you hadn't heard of before, but they were all made my people who... were pretty good and know stuff. YES, some are made by people who are not tainted by conventional thinking, but such people can still differentiate an informal argument from a proof, and they know that an alleged proof that resolves P vs NP needs to be checked quite carefully before bragging about it.<br />
<br />
When the result that Monotone circuits have exponential lower bounds for some problems there was excitement that this may lead to a proof that P ≠ NP, however, nobody, literally nobody, claimed that these results proved P ≠ NP.<i> They knew better.</i><br />
<br />
So, roughly speaking, the people who claim they've resolved P vs NP either have a knowledge gap or can't see their own mistakes or something that makes their work unlikely to have value. One test for that is to ask if they retracted the proof once flaws have been exposed. <br />
<br />
This is not universally true- I know of two people who claimed to have solved the problem who are pretty careful normally. I won't name names since my story might not be quite right, and because they of them retracted IMMEDIATELY after seeing the error. (When Lance proofread this post he guessed one of them,<br />
so there just aren't that many careful people who claim to have resolved P vs NP.) And one of them got an obscure paper into an obscure journal out of their efforts.<br />
<br />
I honestly don't know how careful Deolaikar is, nor do I know if anything of interest every came out of his work, or if has retracted it. If someone knows, please leave a comment.<br />
<br />
I discuss Swart after the next paragraph. <br />
<br />
I WELCOME counter-example! If you know of a claim to resolve P vs NP where the authors paper had something of value, please comment. The term <i>of value</i> means one of two things: there really was some theorem of interest OR there really were some ideas that were later turned into theorems (or in the case of P=NP turned into usable algorithms that worked well in practice).<br />
<br />
One partial counter-example- Swarts claim that P=NP inspired OTHER papers that were good: Yannakakis's proof that Swart's approach could not work and some sequels that made Lance's list of best papers of the 2000's (see <a href="http://blog.computationalcomplexity.org/2014/04/favorite-theorems-extended-formulations.html#comment-form">this post</a>). I don't quite know how to count that.<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com13tag:blogger.com,1999:blog-3722233.post-3971161127339714822015-03-12T06:25:00.000-05:002015-03-12T06:25:13.952-05:00Quotes with which I disagreeOften we hear pithy quotes by famous people but some just don't hold water.<br />
<br />
"Computer science is no more about computers than astronomy is about telescopes."<br />
<br />
Usually <a href="http://en.wikiquote.org/wiki/Computer_science#Disputed">attributed to Edsger Dijkstra</a>, the quote tries to capture that using computers or even programming is not computer science, which I agree. But computer science is most definitely about the computers, making them connected, smarter, faster, safer, reliable and easier to use. You can get a PhD in computer science with a smarter cache system, you can't get a PhD in Astronomy from developing a better telescope lens.<br />
<br />
"If your laptop cannot find it, neither can the market."<br />
<br />
This quote by Kamal Jain is used to say a market can't find equilibrium prices when the equilibrium problem is hard to compute. But to think that the market, with thousands of highly sophisticated and unknown trading algorithm combined with more than a few less than rational agents all interacting with each other can be simulated on a sole laptop seems absurd, even in theory.<br />
<br />
"If you never miss the plane, you're spending too much time in airports."<br />
<br />
George Stigler, a 1982 Nobelist in economics, had this quote to explain individual rationality. But missing a flight is a selfish activity since you will delay seeing people at the place or conference you are heading to or family if you are heading home. I've seen people miss PhD defenses because they couldn't take an extra half hour to head to the airport earlier. If you really have no one on the other side, go ahead and miss your plane. But keep in mind usually you aren't the only one to suffer if you have to take a later flight.<br />
<br />
I take the opposite approach, heading to the airport far in advance of my flight and working at the airport free of distractions of the office. Most airports have the three ingredients I need for an effective working environment: wifi, coffee and restrooms.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com11tag:blogger.com,1999:blog-3722233.post-3558663766432502872015-03-10T12:52:00.000-05:002015-03-15T22:17:31.021-05:00Guest Post by Thomas Zeume on Applications of Ramsey Theory to Dynamic Descriptive ComplexityGuest Post by Thomas Zeume on<br />
<br />
Lower Bounds for Dynamic Descriptive Complexity<br />
<br />
(A result that uses Ramsey Theory!)<br />
<br />
<br />
In a previous blog post Bill mentioned his hobby to collect theorems that<br />
apply Ramsey theory. I will present one such application that arises in<br />
dynamic descriptive complexity theory. The first half of the post introduces<br />
the setting, the second part sketches a lower bound proof that uses Ramsey theory.<br />
<br />
Dynamic descriptive complexity theory studies which queries can be maintained by<br />
first-order formulas with the help of auxiliary relations, when the input structure<br />
is subject to simple modifications such as tuple insertions and tuple deletions.<br />
<br />
As an example consider a directed graph into which edges are inserted. When an edge<br />
(u, v) is inserted, then the new transitive closure T' can be defined from the old<br />
transitive closure T by a first-order formula that uses u and v as parameters:<br />
<br />
T'(x,y) = T(x,y) ∨ (T(x, u) ∧ T(v, y))<br />
<br />
Thus the reachability query can be maintained under insertions in this fashion<br />
(even though it cannot be expressed in first-order logic directly).<br />
<br />
The above update formula is an example of a dynamic descriptive complexity program.<br />
In general, dynamic programs may use several auxiliary relations that are helpful<br />
to maintain the query under consideration. Then each auxiliary relation has one<br />
update formula for edge insertions and one formula for edge deletions.<br />
The example above uses a single auxiliary relation T (which is also the designated<br />
query result) and only updates T under insertions.<br />
<br />
This principle setting has been independently formalized in very similar ways by<br />
Dong, Su and Topor [1, 2] and by Patnaik and Immerman [3]. For both groups one of<br />
the main motivations was that first-order logic is the core of SQL and therefore<br />
queries maintainable in this setting can also be maintained using SQL. Furthermore<br />
the correspondance of first-order logic with built-in arithmetic to uniform<br />
AC0-circuits (constant-depth circuits of polynomial size with unbounded fan-in)<br />
yields that queries maintainable in this way can be evaluated dynamically in a<br />
highly parallel fashion.<br />
<br />
One of the main questions studied in Dynamic Complexity has been whether<br />
Reachability on directed graphs can be maintained in DynFO<br />
(under insertions and deletions of edges). Here DynFO is the class of<br />
properties that can be maintained by first-order update formulas.<br />
The conjecture by Patnaik and Immerman that this is possible has been recently<br />
confirmed by Datta, Kulkarni, Mukherjee, Schwentick and the author of this post,<br />
but has not been published yet [4].<br />
<br />
In this blog post, I would like to talk about dynamic complexity LOWER rather<br />
than upper bounds. Research on dynamic complexity lower bounds has not been<br />
very successful so far. Even though there are routine methods to prove that a<br />
property can not be expressed in first-order logic (or, for that matter, not in AC0),<br />
the dynamic setting adds a considerable level of complication. So far, there is<br />
no lower bound showing that a particular property can not be maintained in<br />
DynFO (besides trivial bounds for properties beyond polynomial time).<br />
<br />
For this reason, all (meaningful) lower bounds proved so far in this setting<br />
have been proved for restricted dynamic programs. One such restriction is to<br />
disallow the use of quantifiers in update formulas. The example above illustrates<br />
that useful properties can be maintained even without quantifiers<br />
(though in this example under insertions only). Therefore proving lower bounds<br />
for this small syntactic fragment can be of interest.<br />
<br />
Several lower bounds for quantifier-free dynamic programs have been proved by using<br />
basic combinatorial tools. For example, counting arguments yield a lower bound for<br />
alternating reachability and non-regular languages [5], and Ramsey-like theorems<br />
as well as Higman's lemma can be used to prove that the reachability query<br />
(under edge insertions and deletions) cannot be maintained by<br />
quantifier-free dynamic programs with binary auxiliary relations [6].<br />
<br />
Here, I will present how bounds for Ramsey numbers can be used to obtain lower bounds.<br />
Surprisingly, the proof of the lower bound in the following result relies on both<br />
upper and lower bounds for Ramsey numbers. Therefore the result might be a good candidate<br />
for Bill's collection of theorems that use Ramsey-like results.<br />
<br />
THEOREM (from [7])<br />
When only edge insertions are allowed, then (k+2)-clique can be maintained by a<br />
quantifier-free dynamic program with (k+1)-ary auxiliary relations, but it cannot be<br />
maintained by such a program with k-ary auxiliary relations.<br />
<br />
SKETCH OF PROOF<br />
<br />
I present a (very) rough proof sketch of the lower bound in the theorem.<br />
The proof sketch aims at giving a flavour of how the upper and lower bounds<br />
on the size of Ramsey numbers are used to prove the above lower bound.<br />
<br />
Instead of using bounds on Ramsey numbers, it will be more convenient to use<br />
the following equivalent bounds on the size of Ramsey cliques. For every c and large enough n:<br />
<br />
1) Every $c$-colored complete $k$-hypergraph of size n contains a large Ramsey clique.<br />
<br />
2) There is a 2-coloring of the complete $(k+1)$-hypergraph of size n that does \emph{not} contain a large Ramsey clique.<br />
<br />
<br />
In the following it is not necessary to know what "large" exactly means<br />
(though it roughly means of size log^{k-1} n in both statements).<br />
Those bounds are due to Rado, Hajnal and Erdős.<br />
<br />
Towards a contradiction we assume that there is a quantifier-free program P with<br />
k-ary auxiliary relations that maintains whether a graph contains a (k+2)-clique.<br />
<br />
The first step is to construct a graph G = (V UNION W, E) such that in all large subsets<br />
C of V one can find independent sets A and B of size k+1 such that adding all edges<br />
between nodes of A yields a graph containing a (k+2)-clique while adding all edges<br />
between nodes of B yields a graph without a (k+2)-clique. Such a graph G can be constructed<br />
using (2). (Choose a large set V and let W := V^{k+1}. Color the set W according to<br />
(2) with colors red and blue. Connect all blue elements w = (v_1, ..., v_{k+1}) in W<br />
with the elements v_1, \ldots, v_{k+1} in V.)<br />
<br />
Now, if the program P currently stores G, then within the current auxiliary relations<br />
stored by P one can find a large subset C of V where all k-tuples are colored equally<br />
by the auxiliary relations. Such a set C can be found using (1). (More precisely:<br />
by a slight extension of (1) to structures.)<br />
<br />
By the construction of G there are subsets A and B of the set C with the property stated<br />
above. As A and B are subsets of C, they are isomorphic with respect to the auxiliary<br />
relations and the edge relation. A property of quantifier-free programs is that for such<br />
isomorphic sets, the application of corresponding modification sequences yields the same<br />
answer of the program, where "corresponding" means that they adhere to the isomorphism.<br />
<br />
Thus the dynamic program P will give the same answer when adding all edges of A, and whenadding all edges of B (in an order that preserves the isomorphism). This is a contradiction<br />
as the first sequence of modifications yields a graph with a (k+2)-clique while the second<br />
yields a graph without a (k+2)-clique. Hence such a program P cannot exist. This proves<br />
the lower bound from the above theorem.<br />
<br />
I thank Thomas Schwentick and Nils Vortmeier for many helpful suggestions on how to<br />
improve a draft of this blog post.<br />
<br />
[1] Guozhu Dong and Rodney W. Topor. Incremental evaluation of datalog queries. In ICDT 1992, pages 282–296. Springer, 1992.<br />
<br />
[2] Guozhu Dong and Jianwen Su. First-order incremental evaluation of datalog queries. In Database Programming Languages, pages 295–308. Springer, 1993.<br />
<br />
[3] Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199–209, 1997.<br />
<br />
[4] Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. ArXiv 2015.<br />
<br />
[5] Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. ACM Trans. Comput. Log., 13(3):19, 2012.<br />
<br />
[6] Thomas Zeume and Thomas Schwentick. On the quantifier-free dynamic complexity of Reachability. Inf. Comput. 240 (2015), pp. 108–129<br />
<br />
[7] Thomas Zeume. The dynamic descriptive complexity of k-clique. In MFCS 2014, pages 547–558. Springer, 2014.<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-88249917133709237492015-03-05T09:23:00.000-06:002015-03-05T09:55:35.839-06:00(1/2)! = sqrt(pi) /2 and other conventions (This post is inspired by the book <a href="http://www.amazon.com/The-Cult-Pythagoras-Math-Myths/dp/0822962705">The cult of Pythagoras: Math and Myths</a> which I recently<br />
read and reviewed. See <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cult.pdf">here</a> for my review.)<br />
<br />
STUDENT: The factorial function is only defined on the natural numbers. Is there some way to extend it to all the reals? For example, what is (1/2)! ?<br />
<br />
BILL: Actually (1/2)! is sqrt(π)/2<br />
<br />
STUDENT: Oh well, ask a stupid question, get a stupid answer.<br />
<br />
BILL: No, I'm serious, (1/2)! is sqrt(π)/2.<br />
<br />
STUDENT: C'mon, be serious. If you don't know or if its not known just tell me.<br />
<br />
The Student has a point. (1/2)! = sqrt(π)/2 is stupid even though its true. So I ask--- is there some other way that factorial could be expanded to all the reals that is as well motivated as the Gamma function? Since 0!=1 and 1!=1, perhaps (1/2)! should be 1.<br />
<br />
Is there a combinatorial interpretation for (1/2)!=sqrt(π) /2?<br />
<br />
If one defined n! by piecewies linear interpolation that works but is it useful? interesting?<br />
<br />
For that matter is the Gamma function useful? Interesting?<br />
<br />
ANOTHER CONVENTION: We say that 0^0 is undefined. But I think it should be 1.<br />
Here is why:<br />
<br />
d/dx x^n = nx^{n-1} is true except at 1. Lets make it ALSO true at 1 by saying that x^0=1 ALWAYS<br />
and that includes at 0.<br />
<br />
A SECOND LOOK AT A CONVENTION: (-3)(4) = -12 makes sense since if I owe my bookie<br />
3 dollars 4 times than I owe him 12 dollars. But what about (-3)(-4)=12. This makes certain<br />
other laws of arithmetic extend to the negatives, which is well and good, but we should not<br />
mistake this convention for a discovered truth. IF there was an application where definiting<br />
NEG*NEG = NEG then that would be a nice alternative system, much like the diff geometries.<br />
<br />
I COULD TALK ABOUT a^{1/2} = sqrt(a) also being a convention to make a rule work out<br />
however (1) my point is made, and (2) I think I blogged about that a while back.<br />
<br />
So what is my point- we adapt certain conventions which are fine and good, but should not<br />
mistake them for eternal truths. This may also play into the question of is math invented or<br />
discovered. <br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com11tag:blogger.com,1999:blog-3722233.post-11236355999729444012015-03-02T14:46:00.000-06:002015-03-02T14:46:29.827-06:00Leonard Nimoy (1931-2015)<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-vAZdHhfPsY4/VPTL0FZ2-MI/AAAAAAAA0UM/-I_nORUSvXU/s1600/spock.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-vAZdHhfPsY4/VPTL0FZ2-MI/AAAAAAAA0UM/-I_nORUSvXU/s1600/spock.jpg" height="116" width="400" /></a></div>
<br />
Bill and I rarely write joint blog posts but with the loss of a great cultural icon we both had to have our say.<br />
<br />
<b>Bill:</b> Leonard Nimoy (Spock) died last week at the age of 83. DeForest Kelley (McCoy) passed away in 1999. William Shatner (Kirk) is still alive, though I note that he is four days older than Nimoy.<br />
<br />
Spock tried to always be logical. I wonder if an unemotional scientist would be a better or worse scientist.<br />
Does emotion drive our desire to learn things? Our choice of problems to work on? Our creativity?<br />
<br />
Did Star Trek (or its successors) inspire many to go into science? Hard to tell but I suspect yes. Did it inspire you?<br />
<br />
There depiction of technology ranged from predicative (communicators are cell phones!) to awful (Episode 'The Ultimate Computer' wanted to show that humans are better than computers. It instead showed that humans are better than a malfunctioning killer-computer. I think we knew that.) I think TV shows now hire science consultants to get things right (The Big Bang Theory seems to get lots of science right, though their view of academia is off.) but in those days there was less of a concern for that.<br />
<br />
<b>Lance:</b> I'm too young to remember the original Star Trek series when it first aired but I did watch the series religiously during the 70's when a local TV station aired an episode every day, seeing every episode multiple times. The original Star Trek was a product of its time, using the future to reflect the current societal issues of the 60's. Later Star Trek movies and series seemed to have lost that premise.<br />
<br />
Every nerdy teenager, myself included, could relate to Spock with his logical exterior and his half-human emotional interior that he could usually suppress. Perhaps my favorite Spock episode was the penultimate "All Our Yesterdays" where Spock having been sent back in time takes on an earlier emotional state of the old Vulcans and falls in love.<br />
<br />
I did see Leonard Nimoy in person once, during a lecture at MIT in the 80's. He clearly relished being Spock and we all relished him.<br />
<br />
Goodby Leonard. You have lived long and prospered and gone well beyond where any man has gone before.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-41517567124879906032015-02-26T16:22:00.000-06:002015-02-26T16:23:08.129-06:00Selecting the Correct OracleAfter my <a href="http://blog.computationalcomplexity.org/2015/02/and-winners-are.html">post last week</a> on the Complexity accepts, a friend of Shuichi Hirahara send Shuichi an email saying that I was interested in his paper. Shuichi contacted me, sent me his paper and we had a few good emails back and forth. He posted his paper <a href="http://arxiv.org/abs/1502.07258">Identifying an Honest EXP<sup>NP</sup> Oracle Among Many</a> on the arXiv yesterday.<br />
<div>
<br /></div>
<div>
Shuichi asks the following question: Given two oracles both claiming to compute a language L, figure out which oracle is correct. For which languages does there exist such a selector?</div>
<div>
<br /></div>
<div>
For deterministic polynomial-time selectors, every such L must sit in PSPACE and all PSPACE-complete languages have selectors. The question gets much more interesting if you allow probabilistic computation.</div>
<div>
<br /></div>
<div>
Shuichi shows that every language that has a probabilistically poly-time selector sits in S<sub>2</sub><sup>EXP</sup>, the exponential analogue of <a href="http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html">S<sub>2</sub><sup>P</sup></a>. His main theorem shows that EXP<sup>NP</sup>-complete sets have this property. His proof is quite clever, using the EXP<sup>NP</sup>-complete problem of finding the lexicographically least witness of a succinctly-described exponential-size 3-SAT question. He uses PCP techniques to have each oracle produce a witness and then he has a clever way to doing binary search to find the least bit where these witnesses differ. I haven't checked all the details carefully but the proof ideas look good.</div>
<div>
<br /></div>
<div>
Still leaves an interesting gap between EXP<sup>NP</sup> and S<sub>2</sub><sup>EXP</sup>. Is there a selector for Promise-S<sub>2</sub><sup>EXP</sup>-complete languages?</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-6312709626999915252015-02-23T11:11:00.001-06:002015-02-23T11:11:29.875-06:00Eliminate the Postal ServiceIt's gotten very difficult to mail a letter these days. There are no mailboxes along my ten mile commute. Georgia Tech has contracted with an outside company to handle outgoing mail. To send a piece of mail requires filling out a form with an account number and many other universities have similar practices. Mail into or out of the university can tack on several days. I sent a piece of mail from Georgia Tech in Atlanta to the University of Pennsylvania in Philadelphia--two weeks from sender to recipient.<br />
<br />
Why do I have to send mail in this world with email, texts and instant messages? Some places require "original receipts". Some government agencies require forms sent by mail or fax, and I've given up trying to find a reliable fax machine with someone who knows how to work it. It's still not always easy to transfer money to another person or company with a physical check. I stopped using the Netflix DVD service because it lost its value when I had to make a special trip to mail the DVD back. It's easier to find a Redbox than a mailbox.<br />
<br />
Meanwhile most of the mail I receive is junk, or magazines, which look better on the iPad, or official letters that I have to scan to keep an electronic copy since they didn't email it to me. I do get the occasional birthday card or hand-written thank you note, a nice Southern tradition but we can live without it. USPS also does package delivery but that is often handled better by private provider such as UPS and FedEx.<br />
<br />
So what if we just eliminated the US Postal System, say with a three-year warning? There is nothing that can't be replaced by electronic means and a planned closing would force the various government and businesses make that final push. We'll reminisce about mail like we did about the telegram. But why keep an inferior technology alive? It's time to move on.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-19154488270828506202015-02-19T06:06:00.000-06:002015-02-20T09:27:05.206-06:00And the Winners Are...[Shortly after this post went up, <a href="http://acm-stoc.org/stoc2015/">STOC</a> announced their <a href="http://acm-stoc.org/stoc2015/acceptedpapers.html">accepted papers</a> as well]<br />
<br />
I always like that the announcement of <a href="http://www.computationalcomplexity.org/Archive/2015/accept.html">accepted papers</a> for the <a href="http://www.computationalcomplexity.org/">Computational Complexity Conference</a> happens around the time of the Academy Awards. These acceptances are the Oscars for our community that shares its name with this conference and the blog.<br />
<br />
The title that interests me is <i>Identifying an honest EXP^NP oracle among many </i>by Shuichi Hirahara since it seems closely related to some of my own research. Not only cannot I not find the paper online, I can't even find the author's email. Shuichi, if you reading this, please send me a copy of your paper.<br />
<br />
Luckily not all papers are so elusive. Murray and Williams <a href="http://eccc.hpi-web.de/report/2014/164/">show</a> that proving the NP-hardness of computing the circuit complexity would require proving real complexity class separation results. Oliveira and Santhanam <a href="http://eccc.hpi-web.de/report/2014/173/">give</a> tight lower bounds on how much you can compress majority so that you can compute it with constant-depth circuits. A different Oliveira has two papers in the conference, a solely authored paper <a href="http://www.cs.princeton.edu/~rmo/papers/small-depth-factors.pdf">showing</a> that polynomials of low individual degree with small low-depth arithmetic circuits have factors similarly computable, and a <a href="http://arxiv.org/abs/1411.7492">paper</a> with Shpilka and Volk on hitting sets for bounded-depth multilinear formula. A hitting set is a small easily and deterministically computable set that contains, for every such arithmetic circuit, an input with a non-zero output.<br />
<br />
Many more <a href="http://www.computationalcomplexity.org/Archive/2015/accept.html">interesting papers</a> and you can see them all at the conference in Portland, this year part of the <a href="http://fcrc.acm.org/">Federated Computing Research Conference</a> which includes STOC, SPAA and EC, which now stands for Economics and Computation. My tip: <a href="http://fcrc.acm.org/travel.cfm">book your hotels</a> now, they fill up fast.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-73410875245873282762015-02-17T09:43:00.003-06:002015-02-17T09:44:44.698-06:00Stephan Colbert, Jon Stewart, Andrew Sullivan, William GasarchStephan Colbert is leaving the Colbert Report<br />
<br />
Jon Stewart is leaving the Daily Show<br />
<br />
Andrew Sullivan is no longer blogging<br />
<br />
Bill Gasarch has resigned as SIGACT News Book Review Editor<br />
<br />
Where will Gasarch get his news from?<br />
<br />
Where will Colbert-Stewart-Sullivan get their reviews-of-theory-books from?<br />
<br />
<br />
Why am I stepping down? I've been SIGACT News book Review editor for 17 years (just as long as Jon Stewart has been doing The Daily Show.) That's enough (more than enough?) time. I want time to spend more time with my books and my family. I will be on sabbatical next year so I am generally cutting down on my obligations. <br />
<br />
I have enjoyed it, gotten to know some publishers, got more free books than I know what to do with. I haven't paid for a math or CS book in... probably 17 years.<br />
<br />
While writing reviews is great, figuring out who reviews other books, getting them the books, getting the review from them, editing it all into a column four times a year, can get to be routine. Though I DO like reading the reviews.<br />
<br />
Who will take over? I asked Lance who would be good and he said `someone old who still reads books'- so I asked Fred Green who agreed to take the job. I then had to get my files (of reviews, of who-owes-me-reviews, of which-books-do-I-want-reviewed, etc) in order to email to him. The usual- I wish I had cleaned up my files years ago so I could benefit from it.<br />
<br />
The main PLUS of the job was that I got to read lots of books and learn about some fields. As someone who would rather read a good book rather than produce a bad paper, the job suited me.<br />
<br />
The main NEGATIVE of the job was seeing so many books that I WANT to review but either didn't have time to (and I usually KNEW that and had someone else review it) or found myself unable to (gee that books is harder than I thought!) leave my office for someone else to review.<br />
<br />
The biggest change that Fred will encounter is e-books.Will publishers want to send out free e-books instead of hardcopy? Will reviewers want hardcopy? This is of course a very tiny part of a more profound conversation of what will happen to the book market once e-books are more common. <br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-4851228262441711002015-02-11T06:23:00.000-06:002015-02-11T06:26:46.264-06:00Richard Hamming Centenary<div class="separator" style="clear: both; text-align: center;">
</div>
<a href="http://www-history.mcs.st-andrews.ac.uk/Biographies/Hamming.html">Richard Hamming</a> was born a hundred years ago today in Chicago. He worked on the Manhattan Project during World War II, moved to Bell Labs after the war and started working with Claude Shannon and John Tukey. It was there that he wrote his seminal 1950 paper <a href="http://dx.doi.org/10.1002/j.1538-7305.1950.tb00463.x">Error detecting and error correcting codes</a>.<br />
<div>
<br /></div>
<div>
Suppose you send a string of bits where a bit might have been flipped during the transmission. You can add an extra parity bit at the end that can be used to detect errors. What if you wanted to correct the error? Richard Hamming developed an <a href="http://en.wikipedia.org/wiki/Hamming(7,4)">error-correcting code</a> (now called the Hamming code) that encodes 4 bits into 16 codewords of 7 bits each such that every two codewords differ in at least three bits (which we now call the Hamming distance). </div>
<div>
<br /></div>
<pre>0000000 1101001 0101010 1000011
1001100 0100101 1100110 0001111
1110000 0011001 1011010 0110011
0111100 1010101 0010110 1111111
</pre>
<div>
If there is a single error then there is a unique codeword within one bit of the damaged string. By having an error-correcting code you can continue a process instead of just halting when you detect a bad code.</div>
<div>
<br /></div>
<div>
The Hamming code is a linear code, the bitwise sum mod 2 of any two codewords is another codeword. This linear idea led to many more sophisticated codes which have had many applications in computer science, practical and theoretical.</div>
<div>
<br /></div>
<div>
Hamming received several awards notably the <a href="http://amturing.acm.org/award_winners/hamming_1000652.cfm">1968 ACM Turing Award</a> and the inaugural <a href="http://www.ieee.org/about/awards/medals/hamming.html">IEEE Richard W. Hamming Medal</a> in 1988 given for exceptional contributions to information sciences, systems, and technology. Hamming <a href="http://www.nytimes.com/1998/01/11/business/richard-hamming-82-dies-pioneer-in-digital-technology.html">passed away</a> in 1998. </div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-79399640390881011062015-02-08T21:24:00.000-06:002015-02-08T21:24:28.426-06:00Pros and Cons of students being wikiheadsA <i>wikihead</i> is someone who learns things from the web (not necc. Wikipedia) but either learns things that are not correct or misinterprets them. I've also heard the term <i>webhead</i> but thats ambigous since it also refers to fans of Spiderman.<br />
<br />
I like to end the first lecture of Discrete Math by talking about SAT and asking the students if they think it can be solved <i>much faster than the obvious 2^n algorithm.</i> This semester in honors DM I got the usual heuristics (look for a contradiction!) that may well help but certainly won't get down to much better than 2^n in all cases. This leads to nice discussions of worst-case vs avg-case and formal vs what-works-in-practice.<br />
<br />
I also got the following answers:<br />
<br />
SAT cannot be done better than 2^n since P ≠ NP.<br />
<br />
and<br />
<br />
SAT can be done in O(n) time with a Quantum Computer.<br />
<br />
They both made there assertions boldly! I gently corrected them. They had both <i>read it on the web.</i><br />
<br />
I suspect that the P ≠ NP person read something that was correct (perhaps a survey that said 80% of all theorists THINK P ≠ NP) and misconstrued it, while the second person read something that was just wrong (perhaps one of those <i>by the many worlds quantum theory a quantum computer can look at all possibilities at the same time</i> people).<br />
<br />
SO- they went and looked up stuff on their own (YEAH) but didn't quite understand it (BOO)<br />
or read incorrect things (BOO). But I will correct them (YEAH). But there are other people who will never get corrected (BOO). But there are others who will get interested in these things because of the false things they read (YEAH?) The quantum person might either NOT go into quantum computing since he thinks its all bogus now, or GO INTO it since he is now curious about what is really going on.<br />
<br />
SO the real question is: if people get excited about math or science for the wrong reasons, is that good?bad? Do you know of examples where incorrect but exciting science writing lead to someone doing real science?<br />
<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-43999669637588223712015-02-05T06:43:00.000-06:002015-02-05T06:43:04.226-06:00Computers Turn Good and EvilEntertainment Weekly proclaimed 2015 the year that <a href="http://www.ew.com/article/2014/12/22/aventers-ultron-terminator-genisys-artificial-intelligence">artificial intelligence will rule the (movie) world</a> with talk of the <i>Terminator</i> reboot, the new Avengers movie <i><a href="http://www.imdb.com/title/tt2395427/">Age of Ultron</a></i>, where Ultron is an attempt at a good AI robot turned evil, and <i><a href="http://www.sonypictures.com/movies/chappie/">Chappie</a></i> who saves the world. And then there is <a href="http://www.imdb.com/title/tt0470752/">Ex Machina</a>, where Domhnall Gleeson "must conduct a Turing test, the complex analysis measuring a machine’s ability to demonstrate intelligent human behavior, while wrestling with his own conflicted romantic longing for the humanoid."<br />
<br />
Let's not forget the return of the <i>Star Wars</i> droids and the hacker movie <i>Blackhat</i> that has already come and gone. On TV we have new computer-based procedurals, one for adults (<i><a href="http://www.cbs.com/shows/csi-cyber/">CSI:Cyber</a></i>) and one for kids (<i><a href="http://www.amazon.com/Buddy-Tech-Detective-HD/dp/B00RSGIAEW">Buddy: Tech Detective</a></i>).<br />
<br />
With Wired proclaiming <a href="http://www.wired.com/2015/01/ai-arrived-really-worries-worlds-brightest-minds/">AI Has Arrived, and That Really Worries the World’s Brightest Minds</a> and Uber <a href="http://bits.blogs.nytimes.com/2015/02/02/uber-to-open-center-for-research-on-self-driving-cars/">investing in technology</a> to eliminate their drivers, what is the average person to think. Let me quote the famous philosopher Aaron Rodgers and say "Relax". We still control the technology, don't we?Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-32716008087948391932015-02-02T10:35:00.001-06:002015-02-02T10:35:15.493-06:00Less elegant proofs that (2n)!/n!n! is an integer(A conversation between Bill (the writer of this post) and Olivia (14-year old daughter of a friend.) All of the math involved is <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/nchoosek.pdf">here</a>.<br />
<br />
Bill: Do you know what 10! is?<br />
<br />
Olivia: Yes, when I turned 10 I yelled out ``I AM 10!''<br />
<br />
Bill: I mean it in a different way. In math 10! is 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2.<br />
<br />
Olivia: Okay. So what?<br />
<br />
Bill: Do you think that (10)!/5!5! is an integer?<br />
<br />
Olivia: No but I'll try it. (She does) Well pierce my ears and call be drafty, it is!<br />
<br />
Bill: Do you think that (100)!/50!50! is an integer?<br />
<br />
Olivia: Fool me once shame on you, Fool me twice... uh, uh, We don't get fooled again was a great song by the Who!<br />
<br />
Bill: Who? Never mind, I'll save a whose-on-first-type blog for another day.<br />
<br />
Olivia: What?<br />
<br />
Bill: He's on second, but never mind that. It turns out that (1) (100!)/50!50! is an integer, and (2) I can prove it without actually calculating it. (Bill then goes through combinatorics and shows that n!/k!(n-k)! solves a problem in combinatorics that must have an integer solution.)<br />
<br />
Olivia: You call that a proof! That's INSANE You can't just solve a problem that must have an integer solution and turn that into a proof that the answer is an integer. Its unnatural. It is counter to the laws of God and Man!<br />
<br />
Inspired by Olivia I came up with a LESS elegant proof that (2n)!/n!n! is always an integer. Inspired by that I also came up with a LESS elegant proof that the Catalan numbers are integers. See the link above for all proofs.<br />
<br />
But realize- WE think it is OBVIOUS that (2n)!/n!n! is an integer (and for that matter n!/k!(n-k)! and the Catalan numbers) and we are right about that--- but there was a time when we would have reacted like Olivia.<br />
<br />
I've seen 5th graders who were sure there must be a fraction whose square is 2 since (1) I wouldn't have asked them if there wasn't, and (2) the concept of a problem not having a solution was alien to them. In an earlier grade the concept of having a problem whose answer was negative or a fraction was alien to them.<br />
<br />
When teaching students and daughters of friends we should be aware that what we we call obvious comes from years of exposure that they have not had.<br />
<br />
When Olivia turns 15 will she say `I AM 15!' More accurate would be `I am 15!.'GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-5638457133720775832015-01-29T06:53:00.001-06:002015-01-29T06:53:35.291-06:00Reusing Data from PrivacyVitaly Feldman gave a talk at Georgia Tech earlier this week on his recent paper <a href="http://arxiv.org/abs/1411.2664">Preserving Statistical Validity in Adaptive Data Analysis</a> with Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. This work looks at the problem of reuse of the cross-validation data in statistical inference/machine learning using tools from differential privacy.<br />
<br />
Many machine learning algorithms have a parameter that specifies the generality of the model, for example the number of clusters in a clustering algorithm. If the model is too simple it cannot capture the full complexity of what it is learning. If the model is too general it may overfit, fitting the vagrancies of this particular data too closely.<br />
<br />
One way to tune the parameters is by cross-validation, running the algorithm on fresh data to see how well it performs. However if you always cross-validate with the same data you may end up overfitting the cross-validation data.<br />
<br />
Feldman's paper shows how to reuse the cross-validation data safely. They show how to get an exponential (in the dimension of the data) number of adaptive uses of the same data without significant degradation. Unfortunately their algorithm takes exponential time but sometimes time is much cheaper than data. They also have an efficient algorithm that allows a quadratic amount of reuse.<br />
<br />
The intuition and proof ideas come from differential privacy where one wants to make it hard to infer individual information from multiple database queries. A standard approach is to add some noise in the responses and the same idea is used by the authors in this paper.<br />
<br />
All of the above is pretty simplified and you should <a href="http://arxiv.org/abs/1411.2664">read the paper</a> for details. This is one of my favorite kinds of paper where ideas developed for one domain (differential privacy) have surprising applications in a seemingly different one (cross-validation).<br />
<br />
<br />Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-10221749790728996102015-01-26T14:43:00.002-06:002015-01-26T14:43:42.125-06:00A nice problem from a Romanian Math Problem Book<br />(All of the math for this problem is <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/recipsq.pdf">here)</a><br />My Discrete Math Honors TA Ioana showed me a Romanian Math Problem book<br />(She is Romanian) and told the following problem:<br />
<br />
<br />
(All a<sub>i</sub> in this post are assumed to be natural numbers)<br />
<br />Show that for all n ≥ 6 there exists (a<sub>1</sub>,...,a<sub>n</sub>) such that 1/a<sub>1</sub><sup>2</sup> + ... + 1/a<sub>n</sub><sup>2</sup> = 1.<br />
<br />
(sum of reciprocals squared)<br />
<br />Normally my curiosity exceeds my ego and I would look up the answer.<br />But it was in Romanian! Normally I would ask her to read the answer to me.<br />But I was going out of town! Normally I would look it up the answer on the<br />web. But this is not the kind of thing the web is good at!<br />
<br />So I did the obvious thing- worked on it while watching Homeland Season 2<br />the first four episodes. And I solved it! Either try to solve it yourself<br />OR goto the link.<br /><br />Some possibly open questions come out of this<br /><br />1) I also prove that, for all k there is an n<sub>0</sub>=n<sub>0</sub>(k) such that<br /><br />all n ≥ n0 there exists (a<sub>1</sub>,...,a<sub>n</sub>) such that1/a<sub>1</sub><sup>k</sup>+ ... + 1/a<sub>n</sub><sup>k </sup>= 1.<br />
<br />
<br />(sum of reciprocal kth powers)<br />
<br />We showed above that n0(2) ≤ 6, its easy to show n<sub>o</sub>(2) ≥ 6, so n<sub>0</sub>(2)=6.<br /><br />Obtain upper and lower bounds on n0(k).<br /><br />2) What is the complexity of the following problem:<br />
<br />Given k,n find out if there exists (a<sub>1</sub>,...,a<sub>n</sub>) such that1/a<sub>1/</sub><sup>k</sup> + ... + 1/a<sub>n</sub><sup>k</sup> = 1.<br /><br />If so then find the values (a<sub>1</sub>,...,a<sub>n</sub>).<br /><br />(We know of an example where the Greedy method does not work.)<br /><br />3) What is the complexity of the following problem: Just as above<br />
but now we want to know HOW MANY solutions.<br />
<br />4) Meta question: How hard are these questions? The original one was<br />on the level of a high school or college math competition. The rest<br />might be easy or hard. I suspect that getting an exact formula for<br />n<sub>0</sub>(k) is hard. I also suspect that proving that this is hard<br />
will be hard.<br /><br /><br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-67419481688014865252015-01-22T07:03:00.002-06:002015-01-22T07:03:55.369-06:00There Should be an AlgorithmMy high school daughter Molly was reading her Kindle and said "You know how you can choose a word and the Kindle will give you a definition. There should be an algorithm that chooses the right definition to display depending on the context". She was reading a book that took place in the 60's that referred to a meter man. This was not, as the first definition of "meter" would indicate, a 39 inch tall male. A meter man is the person who records the electric or gas meter at your house. Today we would use a gender neutral term like "meter reader" if technology hadn't made them obsolete.<br />
<br />
Molly hit upon a very difficult natural language processing challenge known as <a href="http://en.wikipedia.org/wiki/Word-sense_disambiguation">word-sense disambiguation</a> with the most successful approaches using supervised machine learning techniques. If anyone from Amazon is reading this post, the Kindle dictionary would make an excellent application of word-sense disambiguation. You don't need perfection, anything better than choosing the first definition would be welcome. Small tweaks to the user interface where the reader can indicate the appropriate definition would give more labelled data to produce better algorithms.<br />
<br />
And to Molly: Keep saying "There should be an algorithm". Someday there might be. Someday you might be the one to discover it.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com7tag:blogger.com,1999:blog-3722233.post-6345130350309092172015-01-19T08:33:00.003-06:002015-01-19T08:34:39.871-06:00The two defintions of Chomsky Normal FormI have eight textbooks on Formal Lang Theory on my desk. Six of them define a CFG to be in <i>Chomsky Normal Form</i> if every production is of the form either A-->BC or A--> σ (σ a single letter). With that definition one can show that every e-free grammar can be put in Chomsky Normal Form, and using that, show that CFL ⊆ P. There is a very minor issue of what to do if the CFL has e in it.<br />
<br />
Two of the books (Sipers and Floyd-Beigel) define a CFG to be in <i>Chomsky Normal Form </i>if every rule is A-->BC or A--> σ OR S-->e and also that S cannot appear as one of the two nonterminals at the right hand side of a production of the form A-->BC. With this definition you can get that every CFL (even those with e in them) has a grammar in Chomsky Normal Form.<br />
<br />
The definitions are NOT equivalent mathematically, but they are equivalent in spirit and both aim towards the same thing: getting all CFL's in P (That's why I use them for. What did Chomsky used them for?)<br />
<br />
The first definition is correct historically- its what Chomsky used (I am assuming this since it's in the earlier books). The second one could be argued to be better since when you are done you don't have to deal with the e. I still like the first one, but its six of one, half a dozen of the other. One person's floor function is another person's ceiling function.<br />
<br />
I don't have a strong opinion about any of this, but I will say that if you use the second definition then you should at least note that there is another definition that is used for the same purpose. Perhaps make a homework out of this.<br />
<br />
There are many other cases where definitions change and the new one leads to more elegant theorems and a better viewpoint than the old one. There are even cases where the new definition IS equivalent to the old one but is better. IMHO the (∃) definition of NP is better than the definition that uses nondeterministic Poly Time TM's since this leads to the definition of the poly hierarchy. One drawback- if you want to define NL then I think you DO need nondeterministic TM's.<br />
<br />
The only problem I see with changing definitions is if you are reading an old paper and don't quite know which definition they are using. <br />
<br />
What examples of a definition changing (or an equivalent one being more used) do you approve of? Disapprove of?<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-30245621173057663562015-01-15T12:34:00.000-06:002015-01-16T20:39:56.811-06:00The Impact Factor DiseaseThe Institute of Science Information (ISI) was founded in 1960 to help index the ever growing collection of scientific journals. The founder of ISI, Eugene Garfield, developed a simple impact factor to give a rough estimate of quality and help highlight the more important journals. Roughly the <a href="http://en.wikipedia.org/wiki/Impact_factor">impact factor</a> of a journal in year x is the average number of citations each article from years x-1 and x-2 receives in year x.<br />
<br />
Thomson Scientific bought out ISI in 1992 and turned the data collection into a business. Impact factors are not only being used to measure the quality of journals but of authors (i.e. researchers) and institutions as well. In many parts of the world a person's research quality is being measured strongly or sometimes solely by their ability to publish in high impact factor journals.<br />
<br />
This is bad news for computer science since conference proceedings in our field have historically more prestige than journals. We mitigate the ISI factors pretty well in the US but in many other countries this puts computer science at a disadvantage. The need for impact factor publications is one of the reasons conferences are experimenting with a hybrid model.<br />
<br />
In a new trend I get many announcements of journals highlighting their ISI impact factor, mostly very general and previously unknown to me. Our old friends WSEAS say "The ISI Journals (with Impact Factor from Thomson Reuters) that publish the accepted papers from our Conferences are now 32" in the subject line of their email.<br />
<br />
It's the vanity journal with a twist: publish with us and you'll raise your official numerical prestige. So we get a set of journals whose purpose is to raise the value of researchers who should have their value lowered by publishing in these journals.<br />
<br />
Raise your research standing the old fashioned way: Do great research that gets published in the best venues. The numbers will take care of themselves.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-65731557766089818882015-01-13T07:23:00.002-06:002015-01-13T07:23:31.664-06:00Barrier's for Matrx Mult Lower bound<br />
Matrix Mult:<br />
<br />
The usual algorithm is O(n^3).<br />
<br />
Strassen surprised people by showing an O(n^{2.81}) algorithm. (Now its so well known that its not surprising. I try to teach it to people who don't already know its true so they'll be surprised.)<br />
<br />
Over the years the exponent came down, though there was a long time between Coopersmith and Winograd's exp of 2.3755 and the recent improvements.<br />
<br />
Are these improvements going to lead to the exp 2+epsilon?<br />
<br />
Alas the answer is prob no :-(<br />
<br />
In <a href="http://eccc.hpi-web.de/report/2014/154/">Fast Matrix Mult: Limitations of the Laser Method</a> Ambainis, Filmus, and Le Gall show that the methods that lead to the algorithms above will NOT lead to an exp of 2+epsilon.<br />
<br />
How to react to news like this? Barriers should not make us give up; however, they should make us look for new techniques, perhaps guided by the barrier. I would like to think that if you know where NOT to look then it helps you know where TO look.<br />
<br />
There have been barriers that were broken (IP=PSPACE didn't relativize, the recent 2-prover PIR used techniques NOT covered by the barrier result, and the Erdos distance problem was proven after it was known that the current techniques `wouldn't work'). I am sure there are other examples, feel free to leave some in the comments<br />
<br />
Will this result help guide researchers in the right direction? Lets hope so!<br />
<br />
Of course, its possible that 2+epsilon is false and the barrier result is a first step in that direction.<br />
<br />
Which one am I routing for? Neither- I am routing for finding out!<br />
<br />
bill g.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-8500876548183166032015-01-08T07:28:00.000-06:002015-01-08T07:28:08.648-06:00The History of the History of the History of Computer ScienceIn 2007, the science historian Martin Campbell-Kelly wrote an article <a href="http://www.thecorememory.com/THTHS.pdf">The History of the History of Software</a>, where he writes about how he initially wrote histories of the technical aspects of computer software back in the 70's but now he's evolved into writing more about the applications and implications of software technologies. He argues that the whole field of the history of software has moved in the same directions.<br />
<div>
<br /></div>
<div>
Donald Knuth made an emotional argument against this trend last May in his Stanford Kailath lecture <a href="http://kailathlecture.stanford.edu/2014KailathLecture.html">Let's Not Dumb Down the History of Computer Science</a>. If you can find an hour, this is a video well worth watching.<br />
<br /></div>
<!--
<center>
<iframe allowfullscreen="" frameborder="0" height="315" src="//www.youtube.com/embed/gAXdDEQveKw?rel=0" width="420"></iframe></center>
-->
In the January CACM Thomas Haigh gave his thoughts in <a href="http://cacm.acm.org/magazines/2015/1/181633-the-tears-of-donald-knuth/fulltext">The Tears of Donald Knuth</a>. Haigh argues that Knuth conflates the History of Computer Science with the History of Computing. Haigh says that historians focus on the latter and the History of Computer Science doesn't get enough emphasis.<br />
<br />
Let me mention two recent examples in that History of Computing category. <a href="http://www.imdb.com/title/tt2084970/">The Imitation Game</a> give a great, though slightly fictionalized, portrait of the computing and computer science pioneer Alan Turing focusing on his time at Bletchley Park breaking the Enigma code. Walter Isaacson, whose histories of Franklin, Einstein and Jobs I thoroughly enjoyed, writes <a href="http://www.amazon.com/gp/product/147670869X/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=147670869X&linkCode=as2&tag=computation09-20&linkId=VVJ6OETDXBNQXEKO">The Innovators: How a Group of Hackers, Geniuses, and Geeks Created the Digital Revolution</a> which tells the stories of computers from Ada Lovelace to Google (oddly stopping before social networks).<br />
<br />
But what can we do about the History of Computer Science, particularly for theoretical computer science? We live in a relatively young field where most of the great early researchers still roam among us. We should take this opportunity to learn and record how our field developed. I've dabbled a bit myself, talking to several of the pioneers, writing (with Steve Homer) a <a href="http://people.cs.uchicago.edu/~fortnow/papers/history.pdf">short history</a> of computational complexity in the 20<sup>th</sup> Century and a history chapter in The Golden Ticket.<br />
<br />
But I'm not a historian. How do we collect the stories and memories of the founders of the field and tell their tales while we still have a chance?Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com5tag:blogger.com,1999:blog-3722233.post-10824654589019138582015-01-05T14:38:00.000-06:002015-01-06T10:21:53.686-06:00Why do students do this?Before my midterm in ugrad Theory of Computation I gave the students a sheet of practice problems to do that I would go over before the midterm.<br />
<br />
One of them was: Let L be in DTIME(T(n)). Give an algorithm for L*. Try to make it efficient. What is the time complexity of your algorithm? (I had done that if L is in P then L^* is in P in class earlier in the term.)<br />
<br />
My intention was that they do the Dynamic Programming solution. Since it wasn't being collected I didn't have to worry about what would happen if they did it by brute force. When I went over it in class I did the Dynamic Programming Solution, which is roughly T(n)^3 time.<br />
<br />
I allow my students to bring in a sheet of notes that they make up themselves.<br />
<br />
On the exam was the problem: Let L_1 \in DTIME(T_1(n)) and L_2\in DTIME(T_2(n)).<br />
Give an algorithm for L_1L_2. What is the time complexity of your algorithm?<br />
<br />
Of my 20 students 5 of them gave me, word for word, the dynamic programming solution to the L, L* problem.<br />
<br />
Why would they do this? Speculations:<br />
<ol>
<li>They just copied it off of their cheat sheet with no understanding.</li>
<li>They wanted pity points (they didn't get any and I told the class that if a similar thing happens on the final I will give them LESS THAN zero on the problem).</li>
<li>They so hoped that the L, L* problem would be on the exam (possibly becuase it was on their cheat sheet) that they misread the problem.</li>
<li>They thought `Dr. Gasarch wouldn't have put it on the practice exam unless it was on the real exam' (or something like that), so they misread it. </li>
</ol>
The five students were not very good (they did poorly on other problems as well, and on the HW), so it was not a matter of good students being confused or getting nervous.<br />
<br />
But I ask-- (1) is this kind of thing common? For my Sophomore Dscrete Math yes, but I was very slightly surprised to see it in my senior course. (2) Do you have examples? I am sure that you do, but my point is NOT to do student-bashing, its to ask WHY they do this. GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-72807164348226903302014-12-29T12:41:00.000-06:002014-12-29T12:41:38.008-06:002014 Complexity Year in ReviewTheorem of the year goes to <a href="http://arxiv.org/abs/1407.6692">2-Server PIR with Sub-polynomial Communication</a> by Zeev Dvir and Sivakanth Gopi. In Private Information Retrieval you want to access information copied in multiple databases in a way so that no database knows what question you asked. In 1995 Chor, Kushilevits, Goldreich and Sudan <a href="http://dx.doi.org/10.1145/293347.293350">showed</a> how to use n<sup>1/3</sup> bits of communication with two databases. Razborov and Yekhanin <a href="http://dx.doi.org/10.1109/FOCS.2006.10">proved</a> that using current techniques the bound could not be broken. Dvir and Gopi<br />
developed new techniques to break that barrier using n<sup>O(√(log log n/log n))</sup> bits with two databases, less than n<sup>δ</sup> for any δ. Bill <a href="http://blog.computationalcomplexity.org/2014/08/the-n13-barrier-for-2-server-pirs.html">posted</a> more on this result back in August.<br />
<br />
And of course lots of other great work on extended formulations, circuits, algorithms, communication complexity and many other topics. We also had another round of <a href="http://blog.computationalcomplexity.org/2014/12/favorite-theorems-recap.html">favorite theorems</a> for the past decade.<br />
<br />
2014 will go down as the year computer science exploded. With a big convergence of machine learning/big data, the connectedness of everything, the sharing economy, automation and the move to mobile, we have a great demand for computer scientists and a great demand from students to become computer scientists or have enough computing education to succeed in whatever job they get. Enrollments are booming, CS departments are hiring and demand far outstrips the supply. A great time for computer science and a challenging one as well.<br />
<br />
We say goodbye to <a href="http://dmatheorynet.blogspot.com/2014/04/gm-adelson-velsky-passed-away.html">G.M. Adelson-Velsky</a>, <a href="http://bertoni.di.unimi.it/InMemoriam.html">Alberto Bertoni</a>, <a href="http://news.usc.edu/#!/article/59206/in-memoriam-edward-blum-90/">Ed Blum</a>, <a href="http://en.wikipedia.org/wiki/Ashok_K._Chandra">Ashok Chandra</a>, <a href="http://www.clrc.rhul.ac.uk/people/chervonenkis/">Alexey Chervonenkis</a>, <a href="http://www.news.cornell.edu/stories/2014/11/mathematician-eugene-dynkin-dies-90">Eugene Dynkin</a>, <a href="http://cs.illinois.edu/news/memory-clarence-ellis-1943-2014">Clarence "Skip" Ellis</a>, <a href="http://www.nytimes.com/2014/11/16/world/europe/alexander-grothendieck-math-enigma-dies-at-86.html">Alexander Grothendieck</a>, <a href="http://ferranhurtado.blogspot.com.es/">Ferran Hurtado</a>, <a href="http://www.cc.gatech.edu/news/georgia-tech-remembers-mike-stilman">Mike Stilman</a>, <a href="http://www.ae-info.org/ae/User/Stojmenovic_Ivan/OtherInformation">Ivan Stojmenovic</a>, <a href="https://agtb.wordpress.com/2014/06/30/berthold-vocking-1967-2014/">Berthold Vöcking</a>, <a href="http://rjlipton.wordpress.com/2014/07/01/remembering-ann-yasuhara/">Ann Yasuhara</a>, <a href="http://windowsontheory.org/2014/09/19/farewell-microsoft-research-silicon-valley-lab/">Microsoft Research-Silicon Valley</a> and <a href="http://en.chessbase.com/post/nyt-chess-column-dies-but-could-be-resurrected">The New York Times Chess Column</a>.<br />
<div>
<br /></div>
<div>
Thanks to our contributors <a href="http://blog.computationalcomplexity.org/2014/12/joint-center-for-quantum-information.html">Andrew Childs</a>, <a href="http://blog.computationalcomplexity.org/2014/11/guest-post-about-barbie-i-can-be.html">Brittany Terese Fasy</a> and <a href="http://blog.computationalcomplexity.org/2014/10/guest-post-by-dr-hajiaghayi-new-way-to.html">MohammadTaghi Hajiaghayi</a>.</div>
<div>
<br /></div>
<div>
Looking ahead 2015 brings the centenary of the man we know for balls and distance and the fiftieth anniversary of the paper that brought us the title of this blog. Have a great New Years and remember, in a complex world best to keep it simple.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com7