Category Archives: research

Cannot reduce meet to join

Here is an argument from Culver’s MA thesis from 2010.

Suppose the sequence $(A_0\wedge A_1,A_2\wedge A_3,\ldots)$ is $\vee$-reducible to $A$.
Let’s look at the use of the $\vee$-truth-table reduction for computing $A_8\wedge A_9$.
We claim that after seeing only $A_0,\ldots,A_7$ we can rule out one possibility for $(A_8,A_9)$, thereby making money on $A$ and thus showing $A$ is not random.

If the use is only $A_0,\ldots,A_7$ then let’s say the reduction predicts $A_8\wedge A_9=1$. Then we can rule out the pair $(0,1)$. If the reduction predicts $0$ we can rule out $(1,1)$.

If the use is only $A_0,\ldots,A_8$ then based on us looking at $A_0,\ldots,A_7$ we can determine that the reduction predicts $1\wedge A_9=1$ or we can determine that the reduction predicts $1\wedge A_9=0$. Then we can rule out the pair $(1,0)$, or $(1,1)$, respectively.

Finally, if the reduction uses all of $A_0,\ldots,A_9$ then based on us looking at $A_0,\ldots,A_7$ we can determine that the reduction predicts $1\wedge 1=1$ and we can determine that the reduction predicts $1\wedge 0=1$ and… the reduction cannot correctly predict the whole $\wedge$ function or else $\wedge$ would be an element of the clone $\{\vee\}$.

Transition to Advanced Math: Take-home midterm

Do the following problems from Humphreys and Prest:
1.4#2
2.2#5
2.4#6

For the next and last two problems refer to the page Automaton complexity.

Prove that
4. $A(x_1,\ldots,x_k)\le k+1$ for all $k$.
5. $A(x_1,\ldots,x_k)\le k$ for $k\ge 3$.

6. Extra credit (up to 4% of the course): improve some of the $\le$ estimates on the table of complexities.

(I proved in class that $A(x_1,\ldots,x_k)\le k+2$ for all $k$.)

It is essential to write legibly and show your work. If your work is absent or illegible, and
at the same time your answer is not perfectly correct, then no partial credit can be awarded.
Completely correct answers which are given without justification may receive little or no credit.

During this exam, you are permitted to use calculators, notes, or books.

You are not allowed to collaborate with others, except on the extra credit problem.

Special Session on Computability and Complexity

Cameron Freer and I organized a special session at the AMS meeting at UH during March 3-4, 2012.

Program

Speakers

Logan Axon (Gonzaga University, Washington)Axon’s slides
Jennifer Chubb Reimann (University of San Francisco)
Denis Hirschfeldt (University of Chicago)Hirschfeldt’s slides
John Hitchcock (University of Wyoming)
Greg Igusa (UC Berkeley)Igusa’s slides
Joseph S. Miller (University of Wisconsin, Madison)Miller’s slides
Mia Minnes (UCSD) Minnes’ slides
Pavel Semukhin (Pacific Institute for Mathematical Sciences (PIMS), University of Regina, Saskatchewan, Canada)Semukhin’s slides


View Special Session speakers in a larger map

Abstracts

1078-03-400 Algorithmic Randomness and Computational 13-dec-2011
Learning.
John M Hitchcock*, jhitchco@cs.uwyo.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-400.pdf

1078-03-399 Cupping with random sets. 13-dec-2011
Joseph S. Miller*, jmiller@math.wisc.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-399.pdf

1078-03-377 Algorithmic randomness and complexity 13-dec-2011
via automata.
Mia Minnes*, minnes@math.ucsd.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-377.pdf

1078-03-363 The reverse mathematics of homogeneous 13-dec-2011
models.
Denis R. Hirschfeldt*, drh@math.uchicago.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-363.pdf

1078-03-354 Effective properties of approximable 13-dec-2011
functions.
Jennifer Chubb Reimann*, jcc31@psu.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-354.pdf

1078-03-313 Martin-L\”of random closed sets. 12-dec-2011
Logan Axon*, axon@gonzaga.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-313.pdf

1078-03-237 Nonexistence of Minimal Pairs for 10-dec-2011
Generic Computation.
Gregory Igusa*, igusa@math.berkeley.edu
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-237.pdf

1078-03-127 Automatic models of first-order theories. 01-dec-2011
Pavel Semukhin*, pavel@semukhin.name
Frank Stephan
http://www.ams.org/amsmtgs/2190_abstracts/1078-03-127.pdf

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

Nearest walk to Brownian motion

Mathematics 472 (Statistical Inference), University of Hawaii at Manoa, Spring 2009.
This project concerns the distribution of the nearest walk of length \(n\) to a randomly chosen walk of length \(m>n\),
where the walks have step size \(1/n\) on the \(x\)-axis and \(1/\sqrt n\) on the \(y\)-axis.
It is well known that the distribution of such walks converges to Brownian motion.

Two of the groups in the class found that strings of the form \(1^a0^b\) and \(0^a 1^b\) were the least likely nearest walks, whereas strings of the form \(0101\ldots\) or \(1010\ldots\) were the most likely. Strings of the form \(000\ldots\) or \(111\ldots\) were the second least likely.

math overflow questions:

Blurb

I work in mathematical logic, computability theory and algorithmic randomness.

In algorithmic randomness we try to determine what it takes to produce randomness, and what you can do with it once you have it.

Logic and computability deal with the borders between the complete and the incomplete, the decidable and the undecidable, the computable and the non-computable. A fundamental result in the area is Gödel’s 1931 incompleteness theorem, which is a precise version of the following sentiment of Ishmail in Moby Dick.

I promise nothing complete; because any human thing supposed to be complete, must for that very reason infallibly be faulty.

Some open problems are available in a Banff research station archive file.