Computational Complexity

Wednesday, July 28, 2004

 
Journal Rankings

Posted by Lance

An assistant professor writes

In case you need a topic for your weblog: what about journal rankings for theoretical computer science journals? I was looking for something like that for my tenure portfolio. The only web-info I found on the topic was here whose reliability is hard to judge.

Thanks, I am always looking for topics. Journal rankings do not have as strong a perceived ranking in computer science due to the import we give to conferences. Nevertheless, deans like to classify journal articles in computer science like they do for other fields and ask for a ranking.

Here's how I rank theory journals.

1. Journal of the ACM.
2. SIAM Journal on Computing.
3. A large equivalence class of every other major theory journal.
4. Information Processing Letters which publishes short articles that don't merit publication in the above.

Any ordering of journal consistent with this list is okay though even here we have considerable fluctuation. In most theory journals the editor-in-chief rarely overrules the associate editors recommendations and thus have about the same average acceptance criteria. JACM has the tightest quality controls but still occasionally publishes some weaker papers and quite a few mediocre papers appear in SICOMP though I still rate it higher than the rest.

Special issues rank higher, especially those devoted to the best papers of a strong conference. On the other hand, I put no faith on the quality of theory papers that appear in non-theory and especially non-CS journals no matter how they are ranked in their respective field. More than a few rather weak CS papers have appeared in Science, the gold standard for many other scientific disciplines.

3:03 PM #

Tuesday, July 27, 2004

 
NSF Budget

Posted by Lance

The US House Appropriations committee has passed the NSF budget at a 2% ($111 Million) cut. There are still many more phases in the budget process to go but this cannot be viewed as good news for science. For various reasons, the NSF is lumped in the same budgetary group as Veteran's Affairs and the veterans lobby better than scientists.

The American Institute of Physics has a detailed report and perspective. Here also is a statement from the Coalition for National Science Funding and some comments from the Computing Research Policy Blog.

6:36 AM #

Sunday, July 25, 2004

 
Favorite Theorems: Superlinear Bounds on Branching Programs

Posted by Lance

June Edition

Branching programs give us a nice way to model time and space bounds for Boolean functions in a simple non-uniform model. A branching program is a directed acyclic graph where every non-leaf node is labeled by a variable and has two edges labeled One and Zero. All of the leaves are labeled Accept or Reject. Given an input, one follows a path taking the One edge on a node labeled i if the ith input bit is one and the Zero edge otherwise.

The depth (length of the longest path) of the branching program represents time and log of the size represents space. Lower bounds on branching programs give us lower bounds on unrestricted computation.

In 1999, Miklós Ajtai gave the first polynomial-time computable Boolean function for which any subexponential-size deterministic branching program requires superlinear length.

A Non-Linear Time Lower Bound for Boolean Branching Programs by Miklós Ajtai In other words there exists a specified easily computable function that cannot be solved in linear-time unless one uses nearly linear space.

Ajtai creates a function based on quadratic forms and builds on techniques used in his slightly earlier paper.

For more details I recommend the paper Time-space tradeoff lower bounds for randomized computation of decision problems by Beame, Saks, Sun and Vee which gives a nice history of the problem and the techniques to solve it and generalizes Ajtai's work to the probabilistic setting.

7:49 AM #

Thursday, July 22, 2004

 
Carl Smith 1950-2004

Posted by Lance

Maryland Professor Carl Smith passed away last night losing his year and a half battle with brain cancer. He was an expert in inductive inference and an active member of the computational learning community. He traveled extensively making many connections in Holland, Germany, Japan and especially Latvia where he is a foreign member of the Latvian Academy of Science.

Carl Smith also played an important role in the computational complexity community. He organized conferences in the early 80's at Perdue and Maryland on Recursion Theoretic Aspects of Computer Science, precursors to the current IEEE Conference on Computational Complexity. He also co-organized the third Complexity (then called Structures) conference in Georgetown in 1988.

Carl was a colleague and a good friend. We both had sabbaticals in Amsterdam in 1996-7, wrote some papers together and often visited each other afterwards. We shared a love of beer and baseball; I would plan my trips to Maryland around the Orioles home schedule.

I always enjoyed the time I spent with Carl and the many interesting discussions we've had. I, my family, and the entire theory community will miss him greatly.

11:31 AM #

Wednesday, July 21, 2004

 
Extracting Randomness

Posted by Lance

In this post I will describe some recent results in extracting randomness in terms of Kolmogorov complexity since I (and some others) find Kolmogorov complexity more intuitive than entropy. If you would like a background in Kolmogorov complexity, here are some notes from a short course I taught a few years ago. I have not verified that the Kolmogorov results listed below actually follow from the extractor results but it should be straightforward.

Let K(x) be the smallest program generating x. We say a string x is random if K(x)≥|x|. For this post we ignore O(log n) additive factors to avoid various coding issues.

The optimal extractor paper of Lu, Reingold, Vadhan and Wigderson gives us the following. Let n=|x| and K(x)≥k. For all α>0, there is a polynomial-time computable f such that f(x) outputs a polynomial list of strings of length (1-α)k such that most of these strings are random. Using probabilistic constructions of extractors, if one only requires f to be computable, we can set α=0 for k≤n/2.

Barak, Impagliazzo and Wigderson have a new result (mentioned here) on extracting randomness from independent sources. For any constant δ>0, there exists a k polynomial in 1/δ and a polynomial-time computable f such that if we have x₁,…,x_k with

1. |x_i|=n for all i,
2. K(x_i)≥δn for all i, and
3. K(x₁x₂…x_k)=K(x₁)+K(x₂)+…+K(x_k) (the x_i's are independent)

then f(x₁…x_k) is a random string of length n.

Even more recently Barak, Kindler, Shaltiel, Sudakov and Wigderson have even a stronger result in this direction (mentioned here). For any constant δ>0, there exists a ε>0 and a polynomial-time computable f such that if we have x₁,…,x₇ with

1. |x_i|=n for all i,
2. K(x_i)≥δn for all i, and
3. K(x₁x₂…x₇)=K(x₁)+K(x₂)+…+K(x₇) (the x_i's are independent)

then f(x₁…x₇) is a random string of length εn.

3:35 PM #

Monday, July 19, 2004

 
Some Links and Random Thoughts

Posted by Lance

Michael Nielsen is in the midst of a long series of posts on Principles of Effective Research. Much of what he says seems obvious but the obvious often needs to be pointed out. Update 7/27: Complete Principles now available.

Nielsen mentions a new Erdös number eBay auction. We shouldn't use eBay to get people to pay us to do our research; that's what we have graduate students for.

A couple of computational geometers Suresh Venkatasubramanian and Jeff Erickson have been quite active on their weblogs. Check them out.

Finally for some music to prove theorems by, the BBC has put the entire Beethoven sonata cycle with Portuguese pianist Artur Pizarro online.

8:55 AM #

Thursday, July 15, 2004

 
Why are CS Conferences so Important?

Posted by Lance

In nearly every scientific discipline conferences play a minor role. Most conferences have a few plenary speakers mixed with massive parallel sessions where nearly everyone who wants to present can present. The vetting of papers occurs in journals and the quality of one's research is measured much by which journal the work appears.

Computer science conferences are much more selective and the quality of one's work is measured by which conference the work appears. Journals play a far lesser role and many important papers never appear in a journal at all. Why is computer science different?

The answer is technological, namely airplanes. Before air travel conferences were much more difficult to attend and drew from a much more regional audience. Those who made the great effort and time to attend a conference were allowed to present. But presenting your paper at such a conference would not reach the majority of your colleagues. Journals were the most efficient way to broadly publicize your research and took on the more important role and have kept that role for historical reasons.

Computer science started as a field during the jet age. Many more people from a wider geographical base could attend a conference. One could now widely disseminate their research through conferences well before a paper appeared in a journal. Journals still played an important role for refereeing, editing and archiving but never held the importance in computer science as conferences do.

Since then we've seen another technological revolution and the internet easily trumps conferences for quickly distributing your results. Perhaps some new scientific field starting today would have a different internet-based system for judging research. But conferences will remain the primary focus for computer science as journals do for the older scientific disciplines.

6:49 PM #

Wednesday, July 14, 2004

 
Time and Space Hierarchies

Posted by Lance

What the world needs are the time and space hierarchies clearly spelled out in one place.

A function t is time-constructible if there is a Turing machine M such that on input 1ⁿ outputs 1^t(n) in time O(t(n)). Space constructible functions are defined similarly. All the natural functions are time and space constructible.

DTIME(t(n)) are the set of problems computable by a multi-tape Turing machine in deterministic time O(t(n)) on inputs of length n. NTIME (nondeterministic time), DSPACE and NSPACE are defined similarly.

Let t₁ and t₂ be time-constructible functions and s₁ and s₂ space-constructible function. We let "⊂" denote strict subset. A function f(n)=o(g(n)) if lim_n→∞f(n)/g(n)=0.

1. If t₁(n)log t₁(n)=o(t₂(n)) then DTIME(t₁(n))⊂DTIME(t₂(n)).
2. If t₁(n+1)=o(t₂(n)) then NTIME(t₁(n))⊂NTIME(t₂(n)).
3. If s₁(n)=o(s₂(n)) then DSPACE(s₁(n))⊂DSPACE(s₂(n)).
4. If s₁(n)=o(s₂(n)) then NSPACE(s₁(n))⊂NSPACE(s₂(n)).

The DSPACE hierarchy is straightforward diagonalization. For DTIME the proof is similar but we lose log t₁(n) in the simulation of a k-tape machine by a 2-tape machine.

Straightforward diagonalization does not work directly for nondeterministic computation because one need to negate the answer. For NSPACE we easily get around this problem by using Immerman-Szelepcsényi.

The NTIME hierarchy has the most interesting proof that leads to requiring the "+1" in t₁(n+1). This can make a big difference for t₁(n) larger than 2ⁿ².

An NTIME hierarchy was first proved by Cook and in the strongest form by Seiferas, Fischer and Meyer. We sketch a simple proof due to Zàk.

Let M₁,… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1ⁱ01^m01^k:

• If k<m^t₁(m) then simulate M_i on input 1ⁱ01^m01^k+1 for t₂(|w|) steps.
• If k=m^t₁(m) then accept if 1ⁱ01^m0 rejects which we can do quickly as a function of the current input size.

This machine uses time O(t₂(n)). If NTIME(t₁(n))=NTIME(t₂(n)) then there is an equivalent machine M_i using time O(t₁(n)).

Since t₁(n+1)=o(t₂(n)) we have for sufficiently large m,

1ⁱ01^m0 in L(M) ⇔ 1ⁱ01^m01 in L(M) ⇔ … ⇔ 1ⁱ01^m01^mt₁(m) in L(M) ⇔ 1ⁱ01^m0 not in L(M) a contradiction.

8:40 AM #

Monday, July 12, 2004

 
Bringing Families to Conferences

Posted by Lance

When we have a conference or a workshop in a tourist location, like Banff, many of the participants bring their non-computer scientist spouses and sometimes their whole families. I rarely do so. The main purpose in attending conferences and workshops is not the talks but to meet with your fellow researchers. The main purpose of a family vacation is to spend time with the family. These conflicting goals would make me feel guilty during the whole conference no matter how I split my time. Sometimes I will bring the wife or the family a week before or after or between conferences but conference time is science time.

Still I cannot fault my fellow scientists who bring their families to conferences. I would much rather they attend the conference with their families than not come at all. Every professional has a major challenge in balancing family and work life and they need to find the right mix that works for them.

9:00 AM #

Sunday, July 11, 2004

 
Final Notes from Banff

Posted by Lance

Some final notes from the Banff workshop. First a few lemmas used in Wigderson's talk.

Lemma 1: Let G=(V,E) with n vertices and m edges and m≥4n. Let cr(G) be the number of edge crossings in any planer layout of G. Then cr(G)≥m³/64n².

Lemma 2 (Trotter-Szemérdi): Suppose we have a set of points P and lines L in the plane. Let n=|P| and m=|L|. Let I be the number of indices, i.e. the number of pairs (p,l) with p in P, l in L and line l contains the point p. Then |I| ≤ 4((mn)^2/3+m+n).

Guy Kindler talked about a brand new set of results with Barak, Shaltiel, Sudakov and Wigderson. Among other things they improve on the Barak-Impagliazzo-Wigderson result I mentioned earlier by showing that for any constant δ>0, one can take seven independent sources of n bits each with δn min-entropy and combine them to get O(δn) bits of randomness.

Mario Szegedy talked about his recent work showing that the quantum hitting time of a symmetric ergodic Markov chains is the square root of the classical hitting time, a result that becomes a powerful tool in developing quantum algorithms.

Update 7/12: Group Photo now online.

8:50 AM #

Wednesday, July 07, 2004

 
RESULTAPHOBIA!

Posted by Lance

A Guest Post by Bill Gasarch and Brian Postow

In the 1970's there was some hope that deep techniques from Computability theory might crack P vs NP. Some nice results came out of this (e.g., Ladner's theorem that if P ≠ NP then there is a set inbetween). Then the oracle results seemed to say these techniques (whatever that means) would not work.

In the 1980's there was some hope that deep techniques from Combinatorics might crack P vs NP. Some nice results came out of this (e.g., PARITY not in AC₀, and the monotone circuits lower bounds). Then the Natural Proofs framework seemed to say these techniques (whatever that means) would not work.

So where are we now? Fortnow and Homer's paper on the History of Complexity Theory seems to say that we have no ideas at this time. A recent talk at Complexity seemed to say "we didn't work on this aspect of the problem since, if we solved it, we would have P ≠ NP."

We as a community seemed to be afraid of big separation results. We are almost scared of working on hard problems since they might not pan out. Is this wise? There are stories (some apocryphal some not) about people solving problems because they didn't know they were hard. (Examples below)

I recognize that working on problems with little hope of success is dangerous. But to shy away from a line of research BECAUSE it may lead to a big result seems... odd.

EXAMPLE ONE: Neil Immerman tells a story about Robert Szelepcsényi. Szelepcsényi's result that Context Sensitive Languages are closed under complement was announced in an issue of EATCS (in the same issue, two other articles mentioned Immerman's own proof that NSPACE is closed under complement, an effectively equivalent result). Szelepcsényi was an undergrad at the time, and his adviser gave him the famous problem as a challenge, probably not really expecting him to actually solve it. He did solve it, perhaps because he was never told that it was an old open problem that others had failed to solve.

EXAMPLE TWO: A prominent researcher (who told me about this, so its verified) was working on Σ₂-SPACE(n) = Π₂SPACE(n) but stopped since it might lead to the absurd result that Σ₁-SPACE(n)=Π₁=SPACE(n).

DEBUNKING: There is a RUMOR that Umesh Vazarani would have had Quantum factoring in P but didn't get it since it was obviously false. He has denied this. (I put this in so that someone doesn't post a comment about it.)

Are there more cases of either people solving a problem because they didn't know it was open OR of people NOT working on a problem because they thought it was hard (and it wasn't that hard)? I'm sure there there are. If you know of any that have been verified please post to comments or email to gasarch@cs.umd.edu and postow@acm.org.

10:59 PM #

Tuesday, July 06, 2004

 
Gems of Additive Number Theory

Posted by Lance

Yesterday Avi Wigderson gave a talk entitled Gems of Additive/Combinatorial Number Theory where he presented three interesting results about the sizes of sets when you add all the possible numbers from one set with another.

Let A and B be subsets of an Abelian group G and define A+B = {a+b | a in A and B in B}. We define AxB as the same with multiplication when we work over a field. Let |A|=|B|=m.

1. Erdös-Szemerédi: Let A be a subset of the reals. Either |A+A|≥m^5/4 or |AxA|≥m^5/4.
2. Ruzsa: For all k, if |A+B|≤km then |A+A|≤k²m.
3. Gowers: Let E be a set of pairs (a,b) with a in A and b in B. Let A+_EB be the set of values a+b with (a,b) in E. For any δ and k, if |E|≥δm² and |A+_EB|≤km then there is an A'⊆A and B'⊆B with |A'|,|B'|≥δ²m and |A'+B'|≤mk³/δ⁵.

Later Russell Impagliazzo showed how to use finite field versions of these results in his upcoming FOCS paper with Barak and Wigderson. They show how to convert poly(1/δ) independent sources of distributions with δn min entropy to n nearly uniform random bits.

7:42 AM #

Sunday, July 04, 2004

 
Howdy from Banff

Posted by Lance

Another fourth of July out of the states, this time at the Banff International Research Station (BIRS), a Canadian mathematical conference center similar in spirit to Oberwolfach and Dagstuhl. BIRS is hosting a workshop on Advances in Complexity Theory with a pretty impressive collection of researchers.

Today's talks focused on PCPs and their applications. Guy Kindler gave an interesting presentation on his work with Khot, Mossel and O'Donnell showing that under a few believable assumptions, the Goemans-Williamson Max-Cut approximation is optimal.

Took some time off to see Greece win Euro2004. Sorry Luis.

10:21 PM #

Friday, July 02, 2004

 
JCSS To Pay Editors, Possibly Referees

Posted by Lance

The Elsevier owned Journal of Computer and System Sciences will pay an honorarium of $100 to a cognizant editor for each paper handled. According to Editor-in-Chief Ed Blum the intent "is to establish the practice of compensating editors for their scholarly contribution to scientific publication and is a partial response to the complaint that we scholars do all the work and the publishers reap all the rewards. This practice will apply to Guest Editors of Special Issues. I am aware that it does not address the problem of journal pricing. I am still working on that. I am pretty sure that we can also give a $50, honorarium to referees, but am awaiting a final OK [from Elsevier] on that." (Thanks to Bill Gasarch for this information.)

Update 8/7/04: JCSS is rescinding this new policy of awarding honoraria for papers handled.

5:56 PM #

Thursday, July 01, 2004

 
Lessons from Economics

Posted by Lance

Rakesh Vohra pointed me to some interesting takes on journals in economics. Economics runs on a different model than computer science; conferences are less selective and economists are judged more on the quality of the journals where their papers appear.

The Berkeley Electronic Press offers an electronic subscription-based system for their journals. Look at the B.E. Journals in Theoretical Economics. Here you submit to all four journals at once and your paper gets accepted to one with the highest quality rating that the editors decide is appropriate for your paper.

NAJ Economics is Not A Journal but offers reviews of economics papers. One cannot submit papers but a strong rotating editorial board just finds papers freely available on the internet and post reviews of those they feel are worthy. From the FAQ:

The purpose of NAJ Economics is to work towards replacing the existing commercial system of scientific publication. Because papers published in printed journals are less available than working papers, which are freely available on the Internet, publication in the traditional sense inhibits scientific communication. It also generates additional costs as most printed journals charge high subscription fees, in particular to libraries. However, it does serve the useful purpose of certifying the scientific quality of published work. It also assures that articles remain available regardless of the idiosyncrasies of individual websites and links. Our immediate goal is to provide some of the useful certification functions of current journals at a negligible cost by reviewing papers that we think have substantial merit.

I have some quibbles about the service. Without submissions a lesser known author might have trouble getting his paper reviewed. The editors will have a nightmare keeping links up to date, especially since they seem to link to papers on people's homepages. They also don't have the ability to force improvements in the papers they review the way a journal can.

But perhaps in this age of the internet one needs to separate the refereeing and distribution aspects of a journal. NAJEcon is an interesting step in that direction.

7:02 AM #

Archives