|

This work is licensed under a
Creative Commons License.
|
Thursday, February 04, 2010
The more things change the more things change
Posted by GASARCH
There have been some articles on how much things have changed
because of technology.
One from the Washington Post Magazine, titled
Going, Going, ..., Gone
lists out items that are fading out of our lives
Here are a few:
-
Cash: When is the last time you used cash in a transaction that was
over 20 dollars? Over 10?
-
Slide rules: I thought they were already gone gone gone.
You can buy them off the web
here.
The site does not seem to think of them as antiques.
-
Truly blind dates: In my day we couldn't Google our dates ahead of time.
-
FAX machines: Not sure they are really going going gone. If they had
come out earlier they would be far more popular.
If they had come out later they would have been far less popular.
Are they here to stay?
-
Secretaries: I can't imagine having someone type my papers for me or book
a trip for me.
-
Tonsillectomies: I actually got one when I was 8. I hope that wasn't a mistake.
However, nothing demonstrates how
things have changed better than this unaired Pilot of the TV
show 24 from 1994
here.
~
9:00 AM
 #
13 comments
Wednesday, February 03, 2010
Time Space Tradeoffs for SAT- good resuls but...
Posted by GASARCH
This is a real conversation between BILL and STUDENT (a Software Engineering Masters Student
who knows some theory). As such there are likely BETTER arguments BILL or STUDENT could give
for there point of view. I invite you to post such as comments. (ADDED LATER: Some of the comments below DO give
VERY GOOD arguments for why the results are interesting.
I URGE anyone reading this now to read the comments.
They are an integral part of this post, more than usual.)
BILL: In 2007 the best student paper award at COMPLEXITY went to
Ryan Williams for proving that SAT cannot be done in time O(n1.801...)
and O(no(1)) space!!
The constant 1.801 is actually 2cos(π/7).
(The paper is
Time Space Tradeoffs for Counting SAT mod P.
Note that the space is n to the little-o(1) which would include log space.)
STUDENT: Doesn't everyone think SAT is not in P?
BILL: YES.
STUDENT: So what's the big deal in proving that SAT is not in
time O(n1.801...) and not much space?
BILL: Its a stepping stone towards better lower bounds!
STUDENT: Are better lower bounds using these techniques likely?
BILL: Well, it is thought that these techniques cannot possibly get beyond
SAT not in O(n2).
STUDENT: So... why is it such a good result?
BILL: Actually he proved more than that. He proved that, for all but one prime p, finding the number of satisfying
assignments mod p requires O(n1.801) time if you insist on
O(no(1)) space.
STUDENT: Is the number of satisfying assignments mod p problem a problem people care about?
BILL: Complexity Theorists care about it!
STUDENT: I meant real people!
BILL: Um, ur...
STUDENT: Are there any interesting upper bounds on the
number of satisfying assignments mod p problem so that the lower bounds are a
counterpoint to them?
BILL: YES! There are some poly upper bounds are known for planar read-twice monotone formulas mod 7.!
(see this paper by Valiant.)
STUDENT: Do people care about the number of solutions of planar read-twice monotone formulas mod 7?
BILL: Complexity Theorists care about it!
STUDENT: I mean real people! Oh. Are we entering an infinite loop?
BILL: The planar read-twice-monotone-formulas-mod-7 result is an example of
a very powerful framework for algorithms.
STUDENT: So that paper may be important, but why is the SAT time-space tradeoff paper
important?
I like these results, but STUDENT raises a good question:
Are Time Space Tradeoffs for SAT important?
IS SAT mod p important?
I would argue YES since they are absolute lower bounds and
there techniques combined with something else
may yield more interesting results.
However, if you have better arguments please leave comments.
Should Time Space Tradeoffs for SAT be taught in a grad theory course?
There is one in Arora-Barak that is not hard. Hence it likely will be taught.
If you teach it I hope you have students challenge you as STUDENT challenged me.
It will mean they are awake and care.
However, be prepared to answer them.
When this was taught in seminar recently the question arose:
In the paper
Time space Lower bounds for Satisfiability
by Fortnow, Lipton, van Melkebeek, Viglas showed the following:
For all c < φ
(the golden ratio)
there exists d such that SAT cannot be solved in time O(nc)
and space O(nd).
The techniques are such that it could have been proven in the 1970's.
So why wasn't it? The seminar speculates that back then people were not so pessimistic about
lower bounds to consider this a problem worth looking at.
Now people do.
10:13 AM
 #
18 comments
Tuesday, February 02, 2010
Naming and Ranking
Posted by GASARCH
Martin Kruskal
invented Soliton Waves which were a very important concept in
Physics.
(NOTE- one of the comments clarifies this statement.)
Rebecca Kruskal (Martin's Granddaughter): Daddy, how come they are not called Kruskal Waves?
Clyde Kruskal (Martin's Son, Rebecca's Father): You can't name things after yourself.
Rebecca Kruskal: Why not?
Rebecca raises a good question.
In academia the etiquette has evolved that you simply do not name things
after yourself. Why is this? Is it a good thing?
How did this tradition get started?
Have people tried to name things after themselves?
What happens in other endeavors?
On a related topic: if you are asked to give a list of the top items in
your field then is it okay to list some of your own?
In THE NEW BOOK OF LISTS by Wallechinsky (spell check wanted me to change the name to
Lewinsky) and Wallace they have several lists where
an expert in X lists his favorite things in X. Some include their own work:
-
Johnny Cash's 10 Favorite Country Songs of all Time includes
his own I Walk the Line (at number 1) and
Folsom Prison Blues (at number 4).
To be fair, they are awesome songs!
-
Oliver Stone's 12 Best Political Films of all Time actually lists
10 movies (films?) but then says
Stone Notes: And two more with apologies: 11-12. JFK and Salvador.
Because I never thought either could be made, much less be appreciated by a large
audience.
This strikes me as a good way of doing it- since 10 is the usual number on a list
make it 12 and include two of your own and apologize for it.
However, the movie JFK was way too long.
The point of the movie was made more concisely
here
-
Federico Fellini's 10 All Time Favorite Films include his own 8 1/2 as
number 10.
-
Lucille Ball's 10 Favorite TV Series has as item 10
and of course I Love Lucy.
-
Charles M. Schultz's 10 Greatest Cartoon Characters includes,
at number 1, Charlies Brown and Snoopy.
If I was asked for my favorite theorems
and I had one that I thought was reasonable
I wouldn't put it on the list.
But I would add at the end something like
With apologies I include .....
I think it is unfair to compare your own work with others.
9:10 AM
 #
14 comments
Monday, February 01, 2010
Travel Support for Grad Students who GOTO STOC 2010
Posted by GASARCH
If you are a grad student and want to goto STOC 2010
there is travel support money that you can apply for.
See
here
for details.
What is the best way to get this information out?
What is the best wayy to get any kind of information out?
-
Websites. For STOC there is an obvious website, and indeed
it is there under Travel Support.
This works for conferences.
It does not work if the info is hidden deep in a non-obvious
place OR if its not there and should be.
This happens more than it should.
Big Plus: Posting on a website is NOT intrusive like email.
-
Blogs: There are so many blogs and its not clear who reads which ones.
Also, some do not do annoucements like this.
However, blogs are not intrusive and some people who did not know
the info now do.
-
Email: We all get too much and ignore lots of it. Not reliable.
See
this blog entry
for more on that.
-
Twitter: There are still people who don't get tweets. I am one of them.
Though I do read Lance's Tweets on the Complexity Home Page---to see how
he tweets my posts.
-
Facebook: There are still people who don't do facebook. I am one of them.
I may have to at some point. See
here.
10:33 AM
 #
1 comments
Thursday, January 28, 2010
Referees'''' reports
Posted by GASARCH
A commenter a LOOOOONG time ago left the following:
Tell me, Gasarch, how in the world do you get your
papers published when you consistently skip the
apostrophe in it's and that's?
Do referees notice these things anymore, or are
you simply careless in blogs.
This commenter unintentionally raised some good questions:
-
Do referees notice these things anymore...
This indicates that there was a time when referees were
real referees, and men were real men, and women were real women,
and little blue fuzzballs from alpha-8 were
real little blue fuzzballs from alpha-8.
Was there such a time? Or is this is really case of
nostalgia for a time that never was? If anything I think
referees are more demanding
of changes then in a past time since they know that with word processors
such changes are easy to make.
-
What should referees look for?
Ian Parberry has a good paper on this
that is linked to from our website.
Informally, here is what I think the
order should be
(1) Are the results true/important/interesting?`
(2) Are they well presented?
See next item for expansion on (2).
-
Being well presented also has a priority
ordering:
(1) Are the results well motivated?
(2) Are the proofs presented in a way that the reader can see the intuition?
(3) Grammar.
(4) Spelling.
(5) Apostrophes.
-
A referee's job is not just to accept or reject a paper.
Its also to offer advice on a paper to make it better
Are referees now more demanding than they used to be?
less? This splits into many questions: concern with
truth, importance, interest, motivation, intuition, grammar,
spelling, apostrophes. I do not claim to know the answers.
9:09 AM
 #
14 comments
Wednesday, January 27, 2010
Guest post on ICS 2010 (x of y for some x and y)
Posted by GASARCH
(Another Guest post about ICS 2010. From Aaron Sterling.
Is he on his way to break the MOST GUEST POSTS IN A YEAR record?
I doubt it- I think I hold it from before I became a co-blogger,
and I think its at least 10.)
Bill asked me if I thought the ICS conference truly was innovative, and in particular how I thought the
content compared to that of STOC or FOCS. I've never been to either STOC or FOCS
(though I've read some papers and seen some videotaped presentations from those conferences),
so I don't consider myself qualified to answer that question directly. However, something
related has been on my mind, and I think it's important enough to share with the larger community.
I do believe it is innovative and politically significant that ICS literally represents
another country heard from -- and that the derivatives paper appeared there,
not in either STOC or FOCS. Compare the derivatives paper to
Gentry's
homomorphic encryption paper.
Gentry's result is of course a stunning breakthrough in an area that had remained
wide-open for many years; and, to my (brief) reading, it contains more profound
mathematics than the derivatives paper. However, it's quite possible that the
derivatives paper will spark changes in the regulation of the multi-trillion-dollar
financial product industry. If that happens, it would be reasonable to argue that the
derivatives paper would be one of the most influential TCS papers ever.
That comparison, to me, captures the value new concepts can add to the field.
US consumers would only have to save $10 million on financial services for Uncle Sam to be
100% repaid for his investment in an Intractability Center.
I don't it's a coincidence that that Center's director is a co-author of the derivatives paper,
and also a co-author of
this CACM position paper
on how computer scientists should represent their field to better raise money.
I've had the last two paragraphs of that paper on my office door for a few months now,
because I got sick of people complaining to me that there was nothing to be done about
financial woes. I'll reproduce those paragraphs here.
One wonders if the failure of computer scientists to articulate the intellectual excitement
of their field is not one of the causes of their current funding crisis in the U.S.
Too often, policymakers, and hence funding agencies, treat computer science as a provider
of services and infrastructure rather than as an exciting discipline worth studying on its own.
Promises of future innovation and related scientific advances will be more credible
to them if they actually understand that past and current breakthroughs arose from
an underlying science rather than from a one-time investment in 'infrastructure.
It is high time the computer science community began to reveal to the public
its best kept secret: its work is exciting science -- and indispensable to society.
I also believe it is no coincidence that both co-authors of that paper are on the Steering Committee of ICS. There's nothing like a conference that encourages innovation to demonstrate "promises of future innovation and scientific advances."
A generation or two ago, aerospace contractors used the Space Race
as a fundraising tactic. I got the impression from some comments on my first
ICS blog post that people were threatened by the idea that China might
be a major TCS player, and would prefer if I hadn't even mentioned the possibility.
I think that attitude is foolish, and, rather, China's presence on the world
TCS stage should be embraced, and used as a reason it is that much more
important for the US to invest in theory. After all, if Washington allows
things to continue as they are, in ten years, it could be facing a Square Root of Log N Gap!
Okay, that last phrase made me laugh when it popped into my head, so I figured I'd share it.
My point, however, is a serious one. A handful of Ph.D's will get postdocs this year at
IAS or through the Simons Fellowship. Most people won't, even if they're good.
If the CI Fellows program isn't renewed, that means pretty much everyone else is
going abroad. In fact, when I was at ICS, a senior researcher told me that he was
advising students and recent grads to go abroad, not just for postdocs but also
for assistant professorships, and only to return to the US for tenure.
That is not a recipe for maintaining scientific prominence in a field, especially
if one's "major competitor" is investing heavily in recruitment of theorists.
I will end with a question to consider, if I may.
How can we better communicate that computer science, and, in particular,
theoretical computer science, is indispensable to society? The government
of China doesn't seem to have any trouble understanding this.
What about the government of the United States?
10:30 AM
 #
42 comments
Tuesday, January 26, 2010
The First pseudorandom generator- probably
Posted by GASARCH
(The following was told to be by Ilan Newman at Dagstuhl 2009.
His source was the book
The Broken Dice and other mathematical tales of chance.)
What was the first pseudorandom number generator? Who did it?
While these type of questions are hard to really answer,
the book The Broken Dice by Ivar Ekeland gives a very good candidate.
Brother Edvin (a monk), sometime between 1240 and 1250 AD, was preparing
a case for the sainthood of King Olaf Haraldsson, who had been the King of Norway.
There was a well documented story (that could still be false) that King Olaf and the King of Sweden
needed to determine which country owned the Island the Hising.
They agreed to determine this by chance.
They were using normal 6-sided dice.
The King of Sweden rolled two dice and got a 12.
Then King Olaf rolled and got a 12 AND one of the dice
broke (hence the name of the book) and he got an additional 1 for a 13.
Some attributed this event to divine intervention, which
strengthened his case for sainthood.
Brother Edvin got interested in the general question of
how you can generate a random number so that nobody
could manipulate it.
He may have phrased it as a way to know what was divine intervention
as opposed to human intervention.
-
There are two players and they want to pick a random number between 0 and 5.
They want the process to be such that neither
player can bias the outcome.
Each picks a natural number in secret. They are revealed, added, and
then the remainder upon division by 6 is taken.
Brother Edvin noted that the players really only need pick
numbers between 0 and 5; however, he thought it best not to
tell the players this since they will think they have more choice
then they do.
-
What if its only one person. It is too easy to bias things.
But Brother Edwin proposed the following in modern notation.
-
Pick a 4-digit number x.
-
Compute y1=x2,
-
y1 will be 7 or 8 digits. Remove the two leftmost digits
and one or two rightmost digits to obtain a 4-digit number z1.
-
Repeat this process four times to obtain z=z4.
-
Divide z by 6 and take the remainder.
The hope is that it is very hard for a human to bias the results by
picking a particular original 4-digit number.
Brother Edvin did note that some choices for x make the final choice choice
obvious and hence not random
(e.g., 1001). Brother Edvin proposed some
solution: make sure the initial x has no 0's and no repeated digits.
He also suggesting taking more initial digits or more times that you iterate
the process.
But he does realize that this might not work.
The method was rediscovered by von Neumann in a different context.
He wanted to generate long random-looking sequences of numbers.
His idea was to take a 4-digit number x1, square it, and take the
middle 4 digits, repeat some number of times (say 4) to obtain x2
then repeat to get more and more numbers. It was abandoned since the
periods weren't that large. People used
linear congruential generators
instead.
(Are they still used?)
However, Brother Edvin does deserve LOTS OF credit. Given the math known in his
day it is impressive that he asked these questions and got some reasonable
answers.
10:33 AM
 #
7 comments
Monday, January 25, 2010
When is a theorem really proven?
Posted by GASARCH
One of the comments on
this blog pointed out correctly that for a theorem
to be accepted by the community is not a Eureka Moment.
It is a social process. The author of the comment was probably alluding
to an excellent article by DeMillo and Lipton that I blogged
about here.
I highly recommend reading the article that blog points to.
We often say or write things like
-
In 1978 Yao proved that if you store n elements of U in a table of size
n then (for large U) membership requires log n probes (Ref FOCS 78).
-
In 1981 Yao proved that if you store n elements of U in a table of size
n then (for large U) membership requires log n probes (Ref JACM 81).
Personally I try to include both the conference and the journal version
in a citation. That solves the citation problem.
However, what does prove mean? It could be that Yao proved this
in 1977. The exact time/day/year when something is proved is not
that well defined. The original post was about the Fund Lemma
where the paper was written in 2004 and accepted in 2009.
What was its status in 2006? Proven or unproven?
Is there a better way to say these things?
-
In his FOCS 1978 paper (see also Journal version in JACM 1981)
Yao proved the following:
-
In his JACM 1981 paper (original in conference version in FOCS 1978)
Yao proved the following:
These both sound awkward. I am willing to live with using
proved even though its not quite right.
Does someone have an alternative?
Was Time Magazine right to say that the Fund Lemma was one of
the big Science Stories of 2009 even though the paper was
written in 2004? I think so- acceptance in a journal
seems like a good time to declare YES THIS IS TRUE.
And I do not know an alternative.
9:04 AM
 #
20 comments
|