Update 7/10: NSF Theory Program Director Richard Beigel makes available a Sample Report (Dan Spielman) and Sample Findings (Mihir Bellare).
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, June 30, 2009
The NSF Annual Report
Monday, June 29, 2009
Re-request/when to include a known proof in a paper?
- Method of differences due to Pascal
- discrete calculus analog of the fact that the nth degree Taylor expansion of a polynomial is the polynomials.
- The first lemma is a direct consequence of the method of finite differences; it says that the nth forward difference of a polynomial of degree n-1 is identically zero. The inner summation in the second identity is basically computing the coefficients of the Newton Form of the polynomial, although you seem to be using a slightly different basis. Nevertheless, these results are quite standard.
REQUEST:
Authors of those comments (and others who know stuff)--- please email me more exact references. I found some things on Google but it would be good to know what to read and what is a good source to reference. Preferable online.QUESTION: In a paper if you are using a result that is known how much detail should you put in?
- Clearly put in that it is known and provide a references. I would not want to frustrate my readers with This is easily derived from the method of differences. without providing a reference. In this day and age an online reference if you can mange it.
- If the result is not quite written down anywhere but your readers could easily derive it using known techniques, then you do not need to supply a proof. But this is not as clear a statement as it sounds- it depends on how you define readers, easily, known, and technique.
- If the result is known but you have a cute proof of it which seems new (hard to tell) then what do you do?
- If the proof is short then I am more inclined to include it. If its an e-journal than length matters less. (This topic has been raised in a different form before---if Conferences proceedings are CD's then why have a page limit?)
- If there are no online references then I am more inclined to include a proof.
- My only real point here is that its a QUESTION- what is the cutoff for what is worth including? There is no one answer.
Friday, June 26, 2009
Tales of Two Theories
Thursday, June 25, 2009
Complexity Report from DNA 15
I attended DNA 15, the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-11, 2009, at the University of Arkansas. The co-chairs of the organizing committee were Rusell Deaton and Jin-Woo Kim, who I thought did a great job. The research presented, and the backgrounds of the attendees, were diverse from experimental nanochemistry to theoretical computer science. I'll highlight a few elements of the program that had TCS and complexity flavor.
Jim Aspnes and Kenichi Morita gave TCS plenary talks. Aspnes introduced the audience to the computational theory of “population protocols” (see here for a survey) a theory of computation over a large network of agents who each possess very limited computational power. This theory can model ad hoc wireless networks, and (potentially) smart molecules interacting in solution. Morita surveyed results on reversible cellular automata and presented animations that showed the inner workings of several such devices. A reversible computation device is one in which each noninitial configuration has exactly one preceding configuration. Many models of natural computing are reversible models.
NP-completeness of the Direct Energy Barrier Problem Without Pseudoknots, due to Manuch et al., was presented by Anne Condon. The Energy Barrier Problem is decision problem about molecular folding. Given a structure in some initial configuration, does there exist a pathway through subsequent configurations to a final configuration, such that the step from each configuration to the next requires at most energy k, for some fixed k. The paper reduces a simplified version of the Energy Barrier Problem to 3-Partition, a known NP-complete problem.
Several papers discussed the theory and practice of building DNA-based circuits. I would like to focus on Signal Propagation and Propagation Delays in Molecular Circuits by Seelig and Soloveichik, as it puts forth the thesis that circuit depth is not the correct measure of time complexity for chemical circuits (in contrast to electronic circuits, or classical circuit complexity). They present a theoretical model to capture something that has been observed in the lab: when there are just a few molecules of a certain species in solution, the reactions that depend on them will be slow, because the species will interact with low probability, since contact with it is so rare. As a result, stepping through a circuit is not a linear process. Approach to completion of a circuit becomes increasingly slow the deeper the circuit is, because the later layers require the output of all the earlier layers. One possible fix for this is to catalyze the reactions in question, so the reactions occur quickly even if there is only a small amount of species present. The drawback to this is leakage: if a chemical species is not fully consumed at an earlier stage, its presence can build exponentially at later stages, leading to the circuit providing incorrect answers. All in all, an intriguing model that raises a lot of questions.
DNA 16 will take place in Hong Kong, and DNA 17 will be organized by Erik Winfree at CalTech. I'm looking forward to them both!
Wednesday, June 24, 2009
Two requets: A sum and a reference
First: We (Bill Gasarch, Clyde Kruskal, Justin Kruskal) have in a paper of ours a summation that we proved. Is it new? Here is the summation: (It uses a sum that I previously inquired about here and got useful information, including that it was originally proved by Euler.)
Let p(x) &isin Z[x] be a polynomial of degree n with constant term 0.Our proof is here.
p(s) - &sum_{k=1}^{n}(s+k-1 choose k)&sum_{i=0}^{k-1}(k-1 choose i)(-1)^{i} (p(s+i+1) - p(s+i)) = 0
(Side Request: How do you do a choose-sign in html?)
Second: I am, as always, tracking down lower bounds on the VDW numbers. I need the article An application of the Lovasz Local Lemma, a new lower bound for the Van der Warden numbers by Zoltan Szabo, Random Structures and Algorithms, 1990. Electronic preferred, but will take what you got. SO, if someone has it please email me article or pointer or whatnot. (Pointer might not work if your library has access to this journal, since ours does not have it in electronic or hardcopy.)
Tuesday, June 23, 2009
Annoucing YATB (Yet Another Theory Blog)
We've put it on our blogroll.
What will it be about? To quote Jon himself:
The blog will cover random topics, but especially crypto. It was started because there are currently no (active) crypto blogs and I hope this will become, to paraphrase Lance, a meeting place for the crypto community where we would have some discussions, sometimes quite heated, over the issues of concern to our communitySome advice for Jon and any new blogger:
- In your technical posts try to have the first paragraph so that if someone doesn't want to read the rest of it they still get something out of.
- Spellcheck!
- Will you post every day but almost never make comments on the blog (Bill and Lance model)? Will you post once a week but make lots of comments on your own blog (Scott Aaronson model)? Will you post class notes? (Luca does that. Scott sometimes.) Will you be controversial or stear clear of controversy? (I'll let you guess who does what, it varies at times.) Do you have guest posts? What is your policy on anonymous commenters? There are no right and wrong answers; however, you should have answers.
- If you have an idea for a blog try to write it up as soon as possible while you still are enthused about it. If it doesn't work then put it aside--- it may combine well with another idea later.
- Keep a backlog of blogs that are timless.
- Don't get upset at lack of comments, stupid comments, comments that misinterpret your post, or off-topic comments. You will get all of these.
- If you try to make each blog perfect you will have a hard time getting anything out.
- Technical posts are harder to write then others and may get tiring (though Lipton's doing just fine with them). Pace yourself on those.
Monday, June 22, 2009
SIGACT
Friday, June 19, 2009
The Story of the Blog
Thursday, June 18, 2009
Nondeterministic Parallelism
Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.
- Processor i (1 ≤ i ≤ n) guesses the ith bit of a potential satisfying assignment and writes it in memory location i.
- Processor j (1 ≤ j ≤ m) checks whether this assignment makes clause j true.
- If all processors in the second round accept than accept (which takes another log m rounds).
Wednesday, June 17, 2009
Do laypeople know what Prisoner's Dilemma is? Now they might
This is a continuation of the topic in this blog entry.
In the June 17, 2009 issue of The New Republic, in an article called Plan of Attack, the term Prisoner's Dilemma was used and not explained. Does the public know what the term means? Are they supposed to learn what it means from context? I am asking these questions non-rhetorically. Here is the context and exact quote.
Context: Bob Woodward is going to do a book about the Obama White house. If you work in the White house, do you cooperate with him or not?
He (Bob Woodward) flashes a glimpse of what he knows, shaded in a largely negative light, with the hint of more to come, setting up a series of prisoner's dilemmas in which each prospective source faces a choice: Do you cooperate and elaborate in return for (you hope) learning more and earning a better portrayal-- for your boss and yourself? Or do you call his bluff by walking away in the hope that your reticence will make the final product less authoritative and therefore less damaging? If no one talks, there is no book. But if someone talks--- then everyone-- always talks.
- Do people who are not involved with game theory on some level know what The Prisoner's Dilemma is? Some do, but I wonder how many.
- Does it matter? Are writers freer to use terms the audience might not know since the writers know the readers can look it up easily. This is even more true if you are reading online and the writer provides links. However, in that case you may get distracted and not finish the article.
- Will writers do this more often and will this educate the public?
- I have also seen this on TV. If a show mentions some fact I didn't know, I might look it up. Sometimes its fictional, but sometimes its true. And sometimes you may get a skewed view of the issue: I once saw the 25th amendment used three times in one month of TV (West Wing, 24, and a repeat of 24) and always in a dramatic fashion. I looked it up and now know it; however, in real life, it has never been used in a dramatic fashion.
- The article right after the Woodward one was about what to do with the detainees at Gitmo. The name of the article: Prisoner's Dilemma
Tuesday, June 16, 2009
Cond. Cvg Sequences in R^d AND real applications!
Recall that a summation &sum_{i=0}^{&infin} a_{i} Conditionally Cvgs if it cvg but &sum_{i=0}^{&infin} |a_{i}| does not cvg.
Recall the following theorem.
Cond Cvg Thm: Let &sum_{i=0}^{&infin} a_{i} be a cond. cvg sum. Let A &isin R. Then there exists a way to rearrange the summation such that it cvg to A.What happens if instead of reals you have points in R^{d}? For this we need Steinitz's Lemma which we state below. For a nice proof and discussions of variants of it see Imre Barany's paper On the power of linear dependencies (Also available here in case it goes away from his website.)
Steinitz's Lemma Let d be a natural number, B be the unit ball in R^{d}, and V be a finite subset of B such that &sum_{v&isin V} v = 0. Then there is an ordering v_{1}, v_{2}, ..., v_{n} of the elements of V such thatThis can be used to show the following:v_{1} &isin dB
v_{1}+v_{2} &isin dB
v_{1}+v_{2}+v_{3} &isin dB
etc.
v_{1}+...+v_{n} &isin dB
End of Statement of Steinitz's Lemma
d-dim version of Cond Cvg Theorem If a_{1}, a_{2}, a_{3},... &isin R^{d} and &sum_{i=0}^{&infin} a_{i} conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of R^{d}.
This looks like a question and answer in pure math. But wait! there are applications of this sort of thing! And I don't mean applications to other parts of pure math! I don't even mean applications to complexity theory! There are applications to algorithms! Here are four references from Imre Barany's article. Only one was online (alas). If you find links to the other articles then send me link AND article and I will modify this post.
- A vector sum theorem and its application to improving flow shop guarantees. By I. Barany. Math. Oper. Res. Volume 6, 1981, 445-452. downloadhere or if it goes away or does not work then here
- Bibliography: Series of vectors and Riemann sums. By I. Halperin and T. Ando. Sapporo, Japan, 1989
- On approximate solutions of a scheduling problem. by S.V. Sevastyanov. Metody Diskr. Analiza Volume 32, 1978, 66-75. (In Russian).
- On some geometric methods in scheduling theory: a surey, Discrete Applied Math, Volume 55, 1994, 59-82.
Monday, June 15, 2009
Conference Proceedings should have final version in Journal! (Guest Post)
I have noticed that even though in the 80's and 90's a large number of FOCS, STOC, and SODA papers eventually appeared in journals (David Johnson even kindly edited a book that gave pointers to the journal versions of FOCS and STOC papers), the percentage appears to have declined significantly (I have not done a systematic analysis, but when I look for papers I often find that no journal version appeared.)
Most conference papers (even the top conferences) are not reviewed extremely carefully for correctness. The PC has a limited amount of time, and a large volume of papers to review.
What is the reason for this decline?
Are we so desperate to publish papers that we do not want to do a thorough job writing up the proofs after "staking our claim"?
Its very frustrating when when you are reading a paper and details are omitted or missing. Worse still, sometimes claims are made with no proof, or even proofs that are incorrect. Are we not concerned about correctness of results any more? The reviewing process may not be perfect, but at least its one way to have the work scrutinized carefully.
Now that proceedings are on CD's do we still need a strict 10 page limit on the conference version? Is this limit there to simply encourage people to submit to journals? If so, I am not sure its working.
What can we as a community do to ensure that results get properly reviewed and published in full in journals after they are published at a conference?
Friday, June 12, 2009
Math on Kindle DX
Thursday, June 11, 2009
The Great Oracle Debate of 1993
Wednesday, June 10, 2009
Can we make this problem FUN?
Alice, Bob, and Carol each have a number between 0 and 1,000,000,000,000 on their forehead. Everyone can see the numbers that are NOT on their own forehead. Call the three numbers x,y,z. They wish to determine if x+y+z is divisible by 1,000,000,000,000. There is an easy solution: Alice can just say Bob, your number is .... This would take 13 digits of communication. Can they do better?Chandra, Furst, and Lipton showed that if instead of 1,000,000,000,000 was replaced by 2^{n}, and if n is large, then do this in roughly \sqrt n bits. They were more interested in the k-party lower bound of &omega(1) since this leads to lower bounds on branching programs. (NOTE: They studied a variant of the the problem above, but everything they did applies hear also.) See their paper or my writeup for JUST the upper bound or my writeup of the upper and lower boundand its application to branching programs for more information.
The problem stated above with people having numbers on their foreheads sounds like it could be a fun problem for the layperson. BUT: The problem with this problem for the layperson is two fold: (1) The original problem involves 3-free sets. While our community might say Wow, an application of stuff coming out of van der Waerden's theorem (or at least I would say that), the layperson would not think of it or care. (2) Frankly, I don't know if 13 digits numbers are big enough for the asymptotics to kick in and give a better answer than 13.
SO- here is my challenge: Is there a solution to this problem (or perhaps one with larger numbers) where the solution is non-trivial--- that is, you do not communicate all of the numbers, but is also FUN! FUN means you can tell it to your non-mathematical-nephew, or perhaps your 10-years-old-great-niece-who-likes-math. Quite okay if its far worse than \sqrt(n).
Tuesday, June 09, 2009
Fifty Years of Mathmagic Land
My 11-year old daughter talked about using straight lines and angles to improve her mini-golf game. That reminded me of the billiard ball scene in a Donald Duck math movie I saw many times over during my grade school years. Off to YouTube where we watched Donald in Mathmagic Land which coincidentally turns fifty years old this month.
Holds up pretty well after fifty years though the modern music, art, architecture and technology aren't so modern any more. Catch the Turing machine (reel-to-reel computer) near the end.
It was this movie and a Time-Life book on mathematics (which had a really cool chapter on probability) that got me excited by the fun of math which, of course, helped shape my future academic career.
The movie has a scene where Donald tries to open some locked doors that the narrator says represents knowledge yet to be discovered. Cool to think that I have now witnessed many of those door opened, some with my own hands.
Monday, June 08, 2009
Are there any longstanding conjectures that ended up being false?
- Fermat's last theorem should have been called a conjecture. It was proven. I don't think any serious mathematician ever thought it was false.
- Baudet's' Conjecture is now VDW's Theorem.
- The Modell Conjecture is now Faltings Theorem.
- I could list more, so could you.
- Hilbert's 10th problem asked for an algorithm that would, given a poly in many variables over Z, determine if it has a Diophantine solution. We now know this cannot be done. While this may have surprised Hilbert, he was aware of this sort of thing happening. See the preface to his problems, or better see his entire address here.
- Same with the Ind of CH from ZFC. Hilbert thought it was true. More to the point, Hilbert certainly thought it had an answer. Now we know that it does not. Or at least that its ind of ZFC.
- NL=coNL surprised alot of people.
- In 1986 most people thought that P\ne BPP (hard to believe!). One notable exception was Mike Sipser. Now most people think that P=BPP. Of course, not resolved yet.
I doubt that any of the Clay problems will end up being false. I doubt that any serious mathematician thinks that any will end up being false. That might be self-correcting: if someone did we would label him (perhaps unfairly) non-serious.
Saturday, June 06, 2009
Rajeev Motwani
I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away Thursday night in a swimming pool accident at his home. He will be remembered by the large number of professional colleagues, faculty colleagues, and students whose education and lives have been enriched tremendously by his.
Friday, June 05, 2009
Not about STOC/Funny Stuff people have send me
People often send me funny short math things and say this would be great for your blog!. Here is a collection of things people send me over the last year. XKCD comics:
A song about Mandelbrot Sets, although one of the comments on it claims that the song is actually about Julia sets. The person who send it was amused that there is a curse word in it. But he's young and easily amused--- he's 32.
Thursday, June 04, 2009
A Failure of Social Networks?
- No one thought to create a market for the number of flu cases over a couple of thousand.
- Prediction markets require a verifiable outcome so they were based on CDC confirmed cases. But after the flu turned out not to be that dangerous, the CDC stopped confirming most cases and there were less than 7500 confirmed cases by the end of May.
Wednesday, June 03, 2009
Thoughts from STOC
I missed the Valiant celebration but it brought a large number of senior theorists who don't often attend STOC/FOCS. I enjoyed seeing and talking with them. Still, despite a relatively easy to reach location (say compared with last year's Victoria), STOC only attracted about 260 attendees, nearly half students. We just don't get draw many non-local attendees who don't have papers in the conference. Though David Johnson told me he's attended every STOC since the early 70's.
I don't attend many talks at STOC, I prefer to hang in the hallways chatting with people, about research, politics, gossip and baseball. The talks I did attend usually had about five or so good minutes of motivation and results followed by technical details for experts in that particular area. That's probably the right way to give those talks but I was rarely one of those experts.
And then I see a talk as amazing as Moser's and I realize: This is why I love theory.
Tuesday, June 02, 2009
A Kolmogorov Complexity Proof of the Lovász Local Lemma
Here is a sketch of Moser's proof written as a Kolmogorov complexity argument. This is not the full Lovász Local Lemma but captures the main principle.
Theorem: Suppose we have a k-CNF formula φ with n variables and m clauses and each clause shares a variable with at most r other clauses. Then there is a constant d such that if r < 2^{k-d} then φ is satisfiable. Moreover we can find that assignment in time polynomial in m and n.
Here's the algorithm:
Solve(φ)
Pick a random assignment of φ
While there is an unsatisfiable clause C
Fix(C)
Fix(C)
Replace the variables of C with new random values
While there is clause D that shares a variable with C that is not satisfied
Fix(D)
Assume Fix(C) always terminates. Every clause that was satisfied before we called Fix(C) will still remain satisfied and C will also now be satisfied. So Solve makes at most m calls to Fix.
We need to show all the Fix(C) terminate. Suppose the algorithm makes s Fix calls including all the recursive ones. We will show s is bounded and thus the algorithm terminates.
Fix a Kolmogorov random string x of length n+sk (random relative to φ, k, s, r, m and n) and assume the algorithm uses the first n bits as the initial assignment and k bits each to replace the variables in each Fix call.
If we know which clause is being fixed, we know the clause is violated so we know all the bits of this clause and thus we learn k bits of x. We then replace those bits with another part of x.
So we can describe x by the list of clauses we fix plus the remaining n bits of the final assignment. We can describe the C such that Fix(C) is called by Solve by m log m bits and the remaining fixed clauses by log r + O(1) bits because either it is one of r clauses that intersects the previous clause or we indicate the end of a recursive call (keeping track of the recursion stack).
So we must have m log m + s(log r+O(1))+n ≥ n+sk or s(k-log r-O(1)) ≤ m log m.
To show s is bounded, we need k-log r-O(1) to be positive or r<2^{k-d} for some constant d.
Note this in fact shows s = O(m log m) so the algorithm runs in polynomial time. We choose the x randomly which with high probability will be Kolmogorovly random. QED
In the talk, Moser gives the bound r<2 ^{k-3} and in follow-up work with Gábor Tardos shows r<2 ^{k}/e (e = 2.71…) which is the best that comes out of the original Lovász Local Lemma.
Monday, June 01, 2009
STOC
- Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem, Chris Peikert (SRI International)
- A Constructive Proof of the Lovász Local Lemma, Robin A. Moser (ETH Zürich)
- FOCS 2009 will be in Atlanta October 24-27.
- STOC 2010 will be in Cambridge, Massachusetts June 6-8. Complexity will also be held in Cambridge immediately afterwards.
- STOC 2011 will be part of FCRC June 4-11 which will also include Complexity, COLT, SPAA and EC.
- Silivio Micali announced a new conference, Innovations in Computer Science to be held January 4-7, 2010 in Beijing.
- Russell Impagliazzo publicly announced the Barriers Workshop, August 25-29, 2009.