Information markets have taken a blow in the past few days. The US Department of Defense has cancelled a program that would have set up limited futures markets on securities based on terroristic activities. They bowed to pressure from senators who consider it morally wrong to bet on events on future terrorist attacks. I understand their concerns but computer scientists and economists have produced what could have been a powerful tool in controlling terrorism and it is quite a shame to see it discarded so easily.
Wednesday, July 30, 2003
Monday, July 28, 2003
Thursday, July 24, 2003
Now making the move back to Chicago is not nearly so simple. We have houses to sell and buy. Getting our kids ready for a new school. Real estate agents, lawyers, mortgage and insurance people to deal with. Meanwhile there is academic work that needs to get done before the real move. Conference and grant deadlines don't move to accommodate my move.
So this weblog might get a little spotty until I get settled into Chicago, sometime in mid-September. I'll try to find some time for some posts during that time but don't expect too much. If you are having complexity weblog withdrawal check out the archives. Nice thing about complexity--old stuff doesn't (usually) get stale.
Monday, July 21, 2003
Back when I was young (those 80's) we had a different name for a function that depends on a constant number of variables: NC0, a specification of NCk, functions computable in constant fan-in circuits of depth O(logk n). If k = 0 we have constant fan-in and constant depth, which means it depends on a constant number of variables.
Digression: NC stands for "Nick's Class" named by Steve Cook in honor of Nick Pippenger. Pippenger repaid the favor with the class SC but enough of that for now.
Juntas are just one example I'm seeing of a trend of new names and definitions of concepts defined years ago. Makes me feel old. Of course back then we likely studied concepts were thought were new but might not have been. Just part of the great circle of math.
Wednesday, July 16, 2003
With the changes at NEC, I often get asked what will happen to Citeseer. Don't worry--Citeseer will soon have a new safe home and will continue to provide computer scientists with an easy way to track down papers.
Monday, July 14, 2003
Let me try to put this in context while avoiding quantum mechanics. Advice is method for encoding a different program for each input length. We define the class P/poly as those languages computable in polynomial time with access to a polynomially-long advice string an where the string an depends only on the length of the input. P/poly is equivalent to those problems having nonuniform polynomial-size circuits.
Quantum advice is a bit more tricky, since it can be in a superposition of regular advice strings. Formally, quantum advice is an exponentially long vector of numbers βa where βa is the amplitude of advice string a. For simplicity let us assume those numbers are real and we'll also have the restriction that the sum of the squares of the amplitudes is one.
You can see there are far more ways to give quantum advice than classical advice. But the quantum machines are limited in how they can use the advice. Harry Buhrman asked whether one can give any limit at all to what one can do with quantum advice. Scott Aaronson gives an answer: No better than classical advice as long as you are allowed (classical) exponential time.
Ideally one would like that efficient quantum algorithms with quantum advice can be simulated with efficient quantum algorithms with classical advice. Still Aaronson's result shows that even with fully entangled advice one cannot get all the information out of it.
Friday, July 11, 2003
We say A is good is every nonempty row has m/r elements and every nomempty column has m/c elements of A. A rectangle has this property, as does a diagonal. We say A is k-good if every nonempty row has at most km/r elements and every nonempty column has at most km/c elements. A is good if it is 1-good.
Vereshchagin's Theorem: There is a constant c such that for all finite subsets B of N×N with n = log |B| there is a partition of B into at most nc sets each of which is nc-good.
Vereshchagin asks whether there is a purely combinatorial proof of this theorem. If you know of one let me know.
For those who know some Kolmogorov complexity, let me sketch the proof: We label each point (x,y) of B with the following five values: KB(x,y), KB(x), KB(y), KB(x|y) and KB(y|x). We partition the points into sets with the same labels. Standard counting arguments from Kolmogorov complexity show that each partition is nc-good for some c.
Wednesday, July 09, 2003
This year we had one of the best rump sessions ever with five really neat results, listed below. Don't worry if you don't immediately understand the results, I will talk about some of them in more detail in future posts. All but Vereshchagin are students.
- Nikolai Vereshchagin: A combinatorial theorem proven by Kolmogorov complexity with no known direct combinatorial proof.
- Troy Lee: For every finite set A and x in A, CNDA(x) ≤ log |A| + O(log3|x|). CND is the nondeterministic version of Sipser's distinguishing complexity.
- Scott Aaronson: Everything efficiently quantumly computable with a polynomial amount of arbitrarily entangled quantum advice can be simulated in exponential time with a polynomial amount of classical advice.
- Kristoffer Hansen: Constant-width planar circuits compute exactly ACC0, constant depth circuits with a mod gate for some fixed composite.
- Samik Sengupta: If co-NP has an Arthur-Merlin game with a polylogarithmic number of rounds then co-NP is in NP with quasipolynomial advice and the exponential hierarchy collapses at the third level.
Monday, July 07, 2003
During the rest of the year I attend some conferences in broader areas or in areas that are not in my major focus. But coming to Complexity is coming home, and it always feels great to be back where I belong.
Thursday, July 03, 2003
Last year, the first abstracts editor, Bill Gasarch, resigned his job after 11 years of collecting the abstracts. Personally I thought that in this new internet age, with sites like ECCC, the Complexity Abstracts were no longer as valuable a resource. But at the business meeting of last year's conference the Abstracts were greatly supported and Steve Fenner volunteered to take on the job of editor.
Fenner's first collection has just been posted ahead of the Complexity Conference next week in Denmark.
Wednesday, July 02, 2003
"Both?" said the doctor and the lawyer. "Yes," said the mathematician, "That way the wife thinks I'm with the girlfriend, the girlfriend thinks I'm with the wife and I can do some math."
The greatest lovers of math though are not the famous mathematicians at places like Berkeley and Harvard. Rather the mathematicians who take low-paying jobs with high teaching loads at less-strong colleges or move from visiting position to visiting position just to have some occasional time to do math. They have a dedication (or perhaps an addiction) I can never fully appreciate.