All posts by admin

Semantic distance using search engines

Google Distance Between Words (with Alberto J. Evangelista).
Frontiers in Undergraduate Research, University of Connecticut, Spring 2006.
arXiv: 0901.4180 [cs.CL]
The normalized Google distance of Cilibrasi and Vitanyi was studied. An explicit example of the failure of the triangle inequality was found:
\[d(\text{Rolling Stones}, \text{salmonflies})>d(\text{Rolling Stones}, \text{Beatles})+d(\text{Beatles}, \text{salmonflies}).\]
(This is probably due to people misspelling “beetles”.)

Surprisingly (?) this paper was cited by:
Wu, Lin, and Liu: An exploratory study of navigating Wikipedia semantically: model and application (published in LNCS, Online Communities and Social Computing: 4th International Conference).

Worawitphinyo, Gao and Jabeen: Improving Suffix Tree Clustering with New Ranking and Similarity Measures (published in LNCS, Advanced Data Mining and Applications
7th International Conference, ADMA 2011, Beijing, China, December 17-19, 2011, Proceedings, Part II)

Lee Jun Choi,; Rashid, Nur’Aini Abdul;
Adapting normalized google similarity in protein sequence comparison (This paper appears in: Information Technology, 2008. ITSim 2008. International Symposium on)

Khushboo Thakkar et al. / International Journal on Computer Science and Engineering (IJCSE): Test Model for Text Categorization and
Text Summarization

http://efreedom.com/Question/9-19264/Determining-Similarity-Words

Kolmogorov Complexity in perspective Part II: Classification, InformationProcessing and Duality, by Marie Ferbus-Zanda (published in Synthese)

The language specialisation of the Google search
engine, by Volker Schatz

Fall 2011 Teaching

Math 244

HW1: 14.1: 2,4,15,19,23,25
HW2: 14.2: 3,12,15, 20,23,33, 52, 54,55,58
HW3: 14.3: 8,9,14,18 and
14.4:3,12,13,25,30,32,36
HW4: 14.5: 13, 16, 18, 22, 23, 24, 30, 40, 41, 43
HW5: 14.6: 2, 8, 10, 13, 14, 17, 18, 20
HW6: 14.7: 4, 8, 12, 35, 45, 53, 56, 60, 62, 76 and
14.8: 4, 13, 15, 20, 21
HW7: 15.1: 2, 8, 18, 19, 28, 31
15.2: 2, 8, 13, 21, 26, 34, 39, 43, 45
HW8: 15.3: 7, 16, 18, 20, 25, 33, 34, 36
HW9: 15.4: 1, 3, 9, 20, 22, 30, 33, 37
HW10: 15.5: 1, 8, 12, 19, 22, 25, 28, 36, 41, 42
HW11: 15.6: 11, 13, 14, 18, 21, 24, 37, 38, 42
HW12: 15.7: 2, 4, 7, 22, 25 and
15.8: 2, 8, 9, 21, 23, 30

Each homework set is worth the same amount. The top 10 out of 12 homeworks count 1.5% of the course each for a total of 15% for homework. The two best out of three midterms count 20% each. The final counts 45%.

Math 244 Course calendar

Math 471

Midterm III

HW1: Chapter 1:
2,3,4,13,15,19,23,25,26,35,37,40,43,46
HW2: Chapter 1: 51, 56 and Chapter 2:
8,9,18,21,23,30,33,35,40,41,44,45,49,56,62,67,68,70,71,79,80,85
HW3: Chapter 3:
11,12,13,14,18,19,21,24,29,37,38,42,43,44,46,50,59,60,66
HW4: Chapter 5: 1,3,7,9,20,22,23
HW5: Chapter 5: 28, 33, 36, 39
HW6: Chapter 6: 2,6,8,11,12,19,21,25,28,30,31,39,42
Each homework set is worth the same amount. The top 5 homeworks count 2% of the course each. The two best out of three midterms count 25% each. The final counts 45%.

Math 471 Course calendar

2011-2013 Teaching

Here’s what I may be teaching in the next couple of years (if enrollment is high enough). Current teaching information is here.

n Fall n Spring n+1 Annual number of courses
2012
Stochastic Calculus (Shidler School of Business)
Set theory (454)
Mathematical logic (455)

Calculus (24X)
4
2011
Calculus IV (244)
Probability (471)
Statistical Inference (472)
Transition to Advanced Math (321)
4

Kolmogorov complexity and the recursion theorem

Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). Transactions of the American Mathematical Society363 (2011) no. 10, 5465—5480.
arXiv:0901.3933. Preliminary version in STACS 2006, Lecture Notes in Computer Science,
vol. 3884, Springer, Berlin, 2006, pp. 149—161.

The groundwork for this paper was laid in Berkeley in 2004 while Merkle and I were both stopping by there. The paper fits in a long line of results saying “DNR is equivalent to…”, in this case to computing a real whose initial segment complexity is sufficiently high.

A strong law of computationally weak subsets

A strong law of computationally weak subsets

Journal of Mathematical Logic 11 (2011) no. 1, 1—10.
DOI: 10.1142/S0219061311000980
Electronic Colloquium on Computational Complexity, Report No. 150 (2010).

This paper establishes a new statistical law, namely that for each random sequence
$$0111011101101101101\ldots$$
it is possible to replace some of the 1s by 0s (in other words, form a subset of 1s) in such a way that no random sequence can be recovered by computational means.

To illustrate, imagine that the new sequence looks like
$$0111010101101000101\ldots$$

Technically the result is that each 2-random set has an infinite subset computing no 1-random set. It is perhaps the main result obtained under Prof. Kjos-Hanssen’s grant NSF DMS-0901020 (2009-2013).
Joseph S. Miller at U. of Wisconsin has established a strengthening of this result replacing 2-random by 1-random, but that result is so far unpublished.

Dr. Bjørn Kjos-Hanssen is a professor at the University of Hawai‘i at Manoa in the Department of Mathematics. His research deals with the abstract theory of computation, computability, randomness and compression algorithms.

Kjos-Hanssen is the author of more than 20 papers in journals including the prestigious Mathematical Research Letters and Transactions of the American Mathematical Society, and has a PhD from UC Berkeley in the subject Logic and the Methodology of Science.