Abner's Postgraduate Days

The blog, [Lowerbounds, Upperbounds], is to build a community among the Theory group members of CMU.

There are two entries catching my eyes. The first one is the Theory Seminar 2007-02-16: Adaptive Analysis of Algorithms, Erik D. Demaine, MIT.

It is common sense that worst-case analysis of algorithms is not good enough, and Average-case analysis is hard to do.

verage-case analysis gives a better sense about possible performance, but requires some knowledge about the distribution of inputs, making results more specific. In contrast, adaptive analysis parameterizes the input space by one or more additional parameters beyond the problem size, and the goal becomes to optimize simultaneously for all values of those parameters, which is a substantially stronger form of worst-case analysis. When possible, strong adaptive bounds give a fine sense of the intrinsic difficulty of inputs and a better sense of which algorithms are better than which others.

The most promising direction might be "Smoothed Analysis". However it seems also tough and doesn't get the corresponding success.(I am not sure!?)

Erik D. Demaine talked about adaptive analysis of algorithms that I didn't hear before, but there is no slides and bibliography in such entry. I found some articles, that seem to be related to adaptive analysis, on prof. Demaine's homepage.

Ref.: Ilya Baran and Erik D. Demaine, ``Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve,'' in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9-11, 2004, pages 220-229.

Ref.: Ilya Baran, Erik D. Demaine, and Dmitriy A. Katz, ``Optimally Adaptive Integration of Univariate Lipschitz Functions,'' in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20-24, 2006, pages 142-153.



The other is Theory Seminar 2007-02-23: The Price of Privacy and the Limits of LP Decoding, Kunal Talwar, Microsoft Research.

But there is no material, too. But this result is accepted for presentation in STOC 2000.

Nature has a short article about Brain Drain of Italian. And two italian researchers Luca Trevisan and Luca Aceto gave comments "The Runaway Brains" and "Brain Drain and Brain Gain", respectively.

It discuss the bad phenomenon that Italian universities and research institutions can't keep the good Italian researchers and appeal foreign researchers.

Taiwan got the same problem. We all need introspections!

Currently I am writing a draft for the 24th workshop on combinatorial mathematics and computation theory.

I found that the author ordering tradition of TCS, i.e., alpha-by-author ordering, is not always satisfied.

Ref.: Machine Learning (Theory) Best Practices for Collaboration

I found a new journal ``Internet Mathematics'' which publishes research papers that address fundamental problems in dealing with large complex information networks such as the Internet.

This journal seems not famous yet, but its Editorial Board impresses me. Many big heads on it such as Fan Chung Graham, Noga Alon, Jon Kleinberg.

It has short history, but there are many interesting papers:

Volume 1 (2003¡V2004)

• Coupling Scale-Free and Classical Random Graphs by Bela Bollobas and Oliver Riordan
• Graph Clustering and Minimum Cut Trees by Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis
• Coupling Online and Offline Analyses for Random Power Law Graphs by Fan Chung and Linyuan Lu
• Network Applications of Bloom Filters: A Survey by Andrei Broder and Michael Mitzenmacher

Volume 2 (2005¡V2006)

• Lower Bounds and Algorithms for Dominating Sets in Web Graphs by Colin Cooper, Ralf Klasing, and Michele Zito

Volume 3

• Estimating Entropy and Entropy Norm on Data Streams by Amit Chakrabarti, Khanh Do Ba, and S. Muthukrishnan
• Concentration Inequalities and Martingale Inequalities: A Survey by Fan Chung and Lincoln Lu

Prof. Tang required me to prepare the slides about hashing for the course Data Structure. Actually the idea of hashing is applied to many different fields, e.g., Cryptography, Error correction, Identification and verification.

Wikipedia:: The origins of the term

The term "hash" comes by way of analogy with its standard meaning in the physical world, to "chop and mix." Knuth notes that Hans Peter Luhn of IBM appears to have been the first to use the concept, in a memo dated January 1953; the term hash came into use some ten years later.

The following is some resources about hashing

• Linear hash From Wikipedia, the free encyclopedia
• Trie From Wikipedia, the free encyclopedia
• Dynamic hash tables, Communications of the ACM
• Hash Functions and Block Ciphers
• Distributed hash table From Wikipedia, the free encyclopedia
• Hash table From Wikipedia, the free encyclopedia
• MapReduce From Wikipedia, the free encyclopedia
• Powerpoint presentations for Fundamentals of Data Structures in C++, Second Edition, prepared by Prof Sartaj Sahni using Powerpoint 2000.
• J. Rufino, A. Pina, Albano Alves and J. Exposto, Distributed Paged Hash Tables, "5th International Meeting on High Performance Computing for Computational Science (VECPAR '02) - Selected Papers and Invited Talks, Springer, 679-692, Porto, Portugal, June 2002
• M. Bienkowski, M. Korzeniowski, and F. M. auf der Heide. Dynamic load balancing in distributed hash tables. Manuscript, 2004.
• Routing Networks for Distributed Hash Tables, Gurmeet Singh Manku
• Bloom filter From Wikipedia, the free encyclopedia

And Here is the slides I made.