|

This work is licensed under a
Creative Commons License.
|
Tuesday, July 27, 2010
This Post is Quite Different then Any You've Every Read!
Posted by GASARCH
I recently a letter from WETA (public TV) which I
quote from:
This letter is quite different from any we've ever sent to you.
For years we wrote to you about WETA's great programs and the need
they filled in your life.
Today, I must write to you about WETA's needs. And if friends like you
don't respond to them, there will be far less programs to enjoy.
There is something wrong with this letter: I have gotten the exact same letter
from them for about 4 years now.
Hence the statement
This letter is quite different from any we've send to you
is not just false but verifiably false.
While I expect letters to exaggerate I do not expect to have
easily verifiable lies that do not even help their cause.
So why did they do this?
I do not know. But whatever the reason, it is sheer incompetency.
Hence I will not give to them.
This raises the following question:
If a charity (or whatever Public TV is) asks for money they can exaggerate
how much they need it. Should they?
-
Some readers will say GOSH, they really need the money! I better give!
-
Some readers will say They always need money. I am not going to bother.
We also have here a societal problem. Since many (legitimate) charities exaggerate about
how dire their situation is or how serious their problem is, after a while it all gets tuned
out. We have here a a Prisoners Dilemma problem- each one thinks (correctly?) that
if they exaggerate their problems they will get more money. But if they all do it
the public gets cynical and gives less money overall. (NOTE- I do not know this to
be true, but I am curious. If anyone does know then let me know.)
How can they get out of this trap? I do not know. However, the least they can do
is to not say things that are obviously false.
There may be a well defined Game Theory or EC problem here. Or it may be a public policy
problem. We won't know until its solved.
12:04 PM
 #
19 comments
Monday, July 26, 2010
A Seventh Mil. Problem
Posted by GASARCH
Richard Lipton had a wonderful
post
asking for a seventh
Millennium Prize
now that
Poincare's conjecture
has been solved.
I posted a suggestion on his blog but got no comments. I'll expand on it
and see if I get any comments here.
HISTORY: The original proof of
VDW's theorem ,
in 1927,
yields INSANE (not
primitive recursive
) bounds
on the VDW numbers. (Shelah (1988) later got primitive recursive
bounds and Gowers (2001) got bounds you can
actually write down!)
Inspired by VDW's proof Erdos and Turan (1936), made two conjectures:
-
If A is a subset of N of positive upper density then A has arbitrarily long
arithmetic sequences.
Proven by Szemeredi in 1975
(see here for more.)
-
If &Sigmax ∈ A 1/x diverges then A has arbitrarily long arithmetic sequences.
(This conjecture implies the first one.)
A proof of either of these yields a proof of VDW theorem. The hope was
that it would lead to a proof with better bounds.
Szemeredi's proof of the first conjecture did not yield better bounds; however,
Gowers proved the first conjecture a different way that did yield better bounds on
the VDW numbers.
The second conjecture is still worthwhile since it may yield even better bounds
and because it is interesting in its own right. So, I propose the second conjecture
of Erdos-Turan as the 7th Millennium problem.
(It might need a snazzier name. The Divergence Conjecture? The k-AP Conjecture?
Suggestions are welcome!)
-
Greene and Tao have already shown that the primes have arbitrarily large arithmetic progressions.
-
The work that has gone into Szemeredi's theorem and the Greene-Tao theorem spanned
many areas of mathematics. Hence this is not just an isolated problem.
-
The problem has been open since 1936. Hence it is a hard problem.
-
Will more connections to other parts of math be made? Is the problem too hard?
A NO answer to both of these would make it not that good a problem.
-
The converse to the conjecture is not true. Note the following set:
A = &cupk&isin N {2^k + i : 0 &le i < k }
The set A has arbitrarily long arithmetic sequences but
If &Sigmax ∈ A 1/x converges.
-
Is there a plausible condition that characterizes the sets that have
arbitrarily long arithmetic sequences?
-
There is already (I think) a 3000 dollar bounty on the second conjecture. So the Clay Math Institute
will have to just give 997,000 dollars.
11:35 AM
 #
2 comments
Friday, July 23, 2010
CRA Snowbird Part II
Posted by Lance
Considerable discussion about funding at CRA Snowbird. Ken Gabriel, Deputy Director of
DARPA, talked
about how DARPA is restructuring its programs to become
more university-friendly. They've made great progress though there are
still some sticky issues of project-oriented proposals and security clearances. On a related note DARPA recently announced a new Crypto
Program that may be of interest to the theory community.
Peter Harsha, the CRA director of public affairs, talked about NSF
funding and how the renewal of the COMPETES act almost got derailed
over pornography. NSF and CISE in particular
did well in the administration's budget request but there is some
uncertainty as we head into the fall elections.
The best part of the snowbird meeting is networking, talking to a number of CS leaders especially at the meals and breaks. The
last session was small group meetings with current deans on how to
deal with our own deans. Even though I'm not a chair I do find myself
dealing with my dean and his staff quite often and we were able to
get some good advice on quite a range of specific issues. Our group
got lucky in matching up with Dan Huttenlocher, Dean of Computing and Information Science at Cornell, and
Martha Pollack, former Dean of the School of Information at
Michigan. The best general advice: have a good working relationship
with your dean and don't just ask or complain but really make the case
on how the particular resource you need will benefit your school.
I'll be mostly on vacation and off the net for the next couple of
weeks. Be nice to Bill while I'm gone.
7:05 AM
 #
0 comments
Thursday, July 22, 2010
CRA Snowbird Part I
Posted by Lance
I just returned home from my first trip to the CRA Snowbird Conference, the biennial meeting of CS chairs and other leaders in the CS community. I really enjoyed the short meeting and saw many old friends who are now chairs, some people I've only known by email and many I've talked to for the first time. There are a few theorists who have become chairs and deans, and, in the case of Jeff Vitter, provost at Kansas. Unlike theory conferences where I am usually one of the old people, most CS chairs are just about my age.
I, as I had to remind most people I met, am not a chair. I attended as a speaker on the Peer Review in Computing Research panel giving my usual spiel on how the current publication culture hurts the community-building aspects of conferences. Jeannette Wing made a great argument of how our deadline-driven research and conservative program committees may lead our field to lose its "vibrancy, excitement and relevance".
A number of people talked about the big projects they work on which make me almost rethink having gone into theory. Almost. The need for better algorithms shows up in many of these talks. Yoky Matsuoka from U. Washington talked about the artificial hand her group developed that has the full range of motions of a human hand but they lack the algorithms to have the hand do even some simple natural tasks. Illah Nourbakhsh from CMU talked about building electric cars and his ideas of using a supercapacitor as an energy cache for batteries so the batteries become smaller and cheaper but hits challenging cache optimizing issues. The group is running a contest, best algorithm wins an electric car.
Sally Fincher from the University of Kent gave a surprisingly strong talk Why Can't Teaching Be More Like Research? We get judged by our research based on how we compare to the global community but teaching is much more local and Sally talked about the implications of this distinction.
Most disappointing was the discussion on the NRC Rankings. Charlotte Kuh, who served on the NRC committee putting together the "soon" to be released report, said it will not give a specific ranking of each department but rather a range, like University of Southern North Dakota is ranked between 8th and 36th. And not just one range but five ranges based on different weights of the various criteria. And you can create other rankings based on your own choice of weights. All based on 2005-6 data. And they used citation data from the ISI which doesn't include most CS conferences. The CRA board talked them out of that but now the CS data and rankings will use no citation information at all. But even outside of CS, with multiple ranking ranges and old data, the NRC report will be of little value.
7:44 AM
 #
7 comments
Wednesday, July 21, 2010
Do you want to review a book
Posted by GASARCH
I will be sending my next book review column for
SIGACT NEWS off on July 28, 2010.
It has LOTS of books on its BOOKS I WANT REVIEWED list.
YOU get a chance to look at the book list and request one to
review before the list goes out (if you do this then I will
modify the list).
Here is a link to the list of books I want reviewed
HERE.
If you see a book you want then email me at
gasarch@cs.umd.edu
the name of the book and your postal address.
We will then work out details over email-
when the review is due, and whether me or the
publisher sends it to you.
I would like you to email me before July 28 so I can take those books
off the list, but if you email after that date and the book you want
is still available, that will be fine.
Before volunteering you should read my
advice for reviewers.
Here is a
LaTeX Template.
10:15 AM
 #
11 comments
Monday, July 19, 2010
Factors for getting a job- Arbitrary, random, and complex
Posted by GASARCH
The Job Market in Theory (likely in all of academia) has more
randomness and arbitrariness (are those the same?) then
people may realize. Especially young PhD's who have never
been to a faculty meeting where these things are discussed.
The process is quite complex (is that the same as random and arbitrary?).
I am NOT saying that merit plays no role. I am saying that
its very hard to make a clean statement like
Person X got a job an school Y because of Z.
With that in mind, I list out some criteria I have heard played
a role in a hiring decision.
My point is NOT to help you game the system (note that some of the
factors I've heard cut both ways) nor to argue that the system is good, bad, or ugly.
My point is only that the process is more arbitrary-random-complex then you might
think. While its not all merit, its also not all who-you-know or politics.
I invite you to give leave comments on factors you have heard of, but
to keep it civil please do not mention the people or schools involved.
-
Merit: This is itself ambiguous. More papers? Longer papers?
Co-authors? How about take a sum where each summand is
(number of citations)*(importance of paper)*(number of pages)/(number of coauthors).
And then there is grant potential.
-
Does a postdoc have a better chance then a fresh PhD?
A postdoc has had more time to increase his weighted sum mentioned
under Merit, but the school KNOWS he has had more time.
-
Two-body-problems can be GOOD or BAD.
Often a school does not have two positions.
-
Being a women can be GOOD or BAD (for getting a job).
-
I would like to say Being black can be GOOD or BAD (for getting a job)
however since there are so few black PhD's in computer scientists applying
for academic jobs, I have not heard any stories about this.
(NOTE- I use the term black instead of African American
since they need not be American.)
-
Being socially inept can be GOOD or BAD.
How could it be good? It plays to the stereotype.
He's so socially inept, he must be a genius.
I DO NOT recommend pretending you are socially inept.
-
Speaking your mind can be GOOD or BAD.
He'll be a leader in the community or
He'll be a pain in the ass
-
Having a Blog- the jury is still out on this one. I have heard of a case where having
a blog helped someone get an interview.
(It was a serious blog about the field he was in. I can't imagine that complexity blog
would help me get a job if I was looking.)
-
Spending too much time deciding what to have for lunch can be a negative.
If he can't figure out what to have for lunch then how can he formulate a
coherent research plan.
-
Area can be a factor- does a school need or want someone doing area X?
This is sometimes formalized, for example the school has money targeted
to hire someone who does, a particular area.
(Side topic- Targeted positions- Good or Bad? Good in that you are not
going to have to compare people in diff areas. Bad in that there may
be someone really good in another area who you want to hire but can't.)
-
Subarea is a factor- for example, we want the kind of theorist who can
talk to our people in systems.
-
Having a champion in the dept who is helping push your case HELPS
unless the person doing the pushing is a jerk or not good at
pushing a case.
-
Being an ex-convict probably hurts.
If there was a theory genius who served 10 years in jail, that might be a negative. Might be mitigated
if he could pull in some serious grant money.
However, if the jail term was for embezzling grant money, then maybe not.
Actually, the whole question might depend on what he was in jail for and is
he now reformed.
-
A very big factor is how good is the job market when you get out.
This may be a much bigger factor than anything else on this list.
11:09 AM
 #
65 comments
Friday, July 16, 2010
How I Find Homework Problems
Posted by Lance
What do you get out of this paragraph (from Charlie Stross' The Atrocity Archives via Daniel Lemire)
The [Turing] theorem is a hack on discrete number theory that simultaneously disproves the Church-Turing hypothesis (wave if you understood that) and worse, permits NP-complete problems to be converted into P-complete ones. This has several consequences, starting with screwing over most cryptography algorithms—translation: all your bank account are belong to us—and ending with the ability to computationally generate a Dho-Nha geometry curve in real time.
I get a new homework question.
Show that NP-complete = P-complete if and only if NP = L.
Wave if you solve it.
8:48 AM
 #
14 comments
Thursday, July 15, 2010
Sparse problems in NP thought to not be in P
Posted by GASARCH
(This post is similar to
this old post.
I am posting this anyway since when I first posted I made fundamental mistake. I fixed it
the point I was trying to make get lost.)
About once a semester I get asked
What are the natural problems that are in NP,
not known to be in P, and not known to be NPC?
What is known about them?
And I give the standard answers:
-
Graph Isomorphism. If its NPC then PH collapses
so it is though to NOT be NPC. There is no real consensus about
its status with respect to P.
-
Factoring. If its NPC then NP=coNP so it is thought to NOT be NPC.
Most people think that it is NOT in P since people really want to solve
this one and have not been able to. This is not a rigorous argument.
Factoring is in QP.
If quantum computers are ever practical then we may need to rethink
how we think about these things.
-
Discrete Log. Actually, are there reasons to think this is NOT NPC?
The answer above are standard and I suspect most of my readers know them.
However, there is a large source of problems that are in NP, likely not NPC,
likely not in P, that people don't seem to talk about much: SPARSE PROBLEMS
that are thought to be hard. The ones I know about are from Ramsey Theory.
I give one example but there are many like it:
{(1n,1m,c) : the n×m grid can be c-colored and not have any mono squares}
-
This is clearly in NP since the coloring itself is the witness.
-
Since this is a sparse set it is not NPC unless P=NP.
(Actually it can be coded as a tally set.)
-
I want to say People think this is hard. You may ask
Name Three of Them! Indeed, the number of people who work on Computational Ramsey Theory
is fairly small. However, Ramsey Theory itself has many people working on it and
nobody has anything close to a result indicating that this problem is in P.
I personally think that it is hard.
-
For a fixed c there is a finite number of grids G1,...,Gp
such that the n×m grid is c-colorable iff none of G1,...,Gp can fit inside the n×m grid.
Hence, for fixed c, the problem is in P.
(So the problem is Fixed Parameter Tractable.)
-
Everything said above holds if you replace squares with rectangles or other configurations in the above.
Questions:
-
Are there other sparse problems in NP that we think are NOT in P?
(that is, ones that DO NOT come from Ramsey Theory).
-
Should we be teaching these in our complexity classes as examples of possible
intermediary problems? The proof that they are likely not NPC is easy.
However, to argue that these problems are likely not in P is hard.
Also, these problems may appear unnatural to some students.
(They may appear unnatural to some of my readers.)
-
It is easy to argue that Factoring is probably not in P since you can point
to the fact that people REALLY want to solve it quickly and so far have not.
This is not a rigorous argument but I do count it as evidence.
Is there a similar argument for GI?
Is there a similar argument for my Ramsey Problems?
-
Is there a mathematical reason to think that Factoring, GI, or my Ramsey Problems
are not in P?
10:20 AM
 #
10 comments
|