The great Andrew Yao invites and many famous researchers come - what a great event, I'm very glad to have the opportunity to listen to interesting talks at the China Symposium on Theoretical Computer Science.
A brief summary of day 1.
A lot of history and high-level in the morning.
Ronald Graham gave a history of Steiner Trees. His introduction was in Chinese, very impressive, I didn't understand a word though... Next surprise, I didn't know that we don't even know whether Euclidean MST is in NP!
Christos Papadimitriou presented 6 to 8 examples where Computer Science proves its influence to other sciences. A very interesting one was the question whether an optimal system can have an internal conflict (Livnat Pippenger answer this question with yes in 2006), regarding the many internal conflicts in our brain... Then, he made a point that genetic algorithms don't prove useful for combinatorial problems as sexual reproduction favors low risk medium payoff such that we can mate with whoever we want to (Livnat, Papadimitriou 2007).
Avi Wigderson talked about reductions and the history of the PCP theorem.
The afternoon was more concrete.
Sanjeev Arora surveyed SDP and connections to high dimensional geometry. I understood the beginning, became tough towards the end.
Avrim Blum talked about Learning and Clustering. The properties of the similarity measure influence the algorithm to use to get a good clustering. Some problems in clustering are hard but they might be hard because of the model, while the actual problem might be a bit easier.
Maurice Herlihy showed that Renaming is Weaker than Set Agreement (a weaker form of consensus)
And finally, Nir Shavit showed Hashing for Multicore Architectures. It looks like the software will be the bottleneck in the future, hardware switches to Multicore Architectures and software cannot handle the synchronizations. We'll see. Maybe noone will buy the new hardware if the speed-off is too small.
The Recursive Split Ordering reminded me of something I've heard at NII, more to come about that.
2008/10/13
Local Testability and Decodability of Sparse Linear Codes
Long time no post...
Madhu Sudan gave an interesting talk at Tsinghua University.
paper (Kaufman, Sudan)
Some of my notes.
fixed error correcting code, oracle access, check whether correct word resp. not too corrupt, local correction if close to a word, local testing and local correction
example: Hadamard code
code C
linear: x,y \in C => x+y \in C
sparse: t-sparse if C <= n^t (only polynomially many codewords, quite restrictive) large distance: \gamma large distance if for all code words distance at least 1/2-n^-\gamma, as close to 1/2 as possible if these conditions, then k-locally testable (if in addition balanced, k-locally correctible) linear code: dual: all words orthogonal to all code words, dual code also linear => pick a word of dual code, check whether it is orthogonal, that's the check. word should be of low weight (weight k) to allow for a k-local test
corrector to correct coordinate i needs a low-weight word in the dual where coordinate i is 1 and the rest is roughly uniform
=> does dual code have low weight words? roughly uniform even with restriction coordinate i is 1?
weight distribution of primal code: C_i = number of codewords in C with weight i
actually want distribution of dual code C_k^\perp
from primal to dual code weight distributions: MacWilliams identities, hold if we know C_i EXACTLY
C_k^\perp = 1/C \sum C_i P_k(i)
where P_k(i) = \sum (-1)^j (i choose j) (n-i choose k-j) is Krawtchouk Polynomial
the codeword 0 (C_0={0}) contributes most to the sum, polynomial has high value there, low value at all other C_k, as not too many codewords it does not cancel out the highly weighted 0 word
doesn't work for unbalanced because low weight words in dual not guaranteed
and: don't know how to find these words...
Madhu Sudan gave an interesting talk at Tsinghua University.
paper (Kaufman, Sudan)
Some of my notes.
fixed error correcting code, oracle access, check whether correct word resp. not too corrupt, local correction if close to a word, local testing and local correction
example: Hadamard code
code C
linear: x,y \in C => x+y \in C
sparse: t-sparse if C <= n^t (only polynomially many codewords, quite restrictive) large distance: \gamma large distance if for all code words distance at least 1/2-n^-\gamma, as close to 1/2 as possible if these conditions, then k-locally testable (if in addition balanced, k-locally correctible) linear code: dual: all words orthogonal to all code words, dual code also linear => pick a word of dual code, check whether it is orthogonal, that's the check. word should be of low weight (weight k) to allow for a k-local test
corrector to correct coordinate i needs a low-weight word in the dual where coordinate i is 1 and the rest is roughly uniform
=> does dual code have low weight words? roughly uniform even with restriction coordinate i is 1?
weight distribution of primal code: C_i = number of codewords in C with weight i
actually want distribution of dual code C_k^\perp
from primal to dual code weight distributions: MacWilliams identities, hold if we know C_i EXACTLY
C_k^\perp = 1/C \sum C_i P_k(i)
where P_k(i) = \sum (-1)^j (i choose j) (n-i choose k-j) is Krawtchouk Polynomial
the codeword 0 (C_0={0}) contributes most to the sum, polynomial has high value there, low value at all other C_k, as not too many codewords it does not cancel out the highly weighted 0 word
doesn't work for unbalanced because low weight words in dual not guaranteed
and: don't know how to find these words...
Subscribe to:
Posts (Atom)