The 11th International Conference on Computability, Complexity and Randomness is held in Physical Science Building 217, University of Hawaii at Manoa, January 4–8, 2016.
The conference is supported by the National Science Foundation under Grant No. 1545707.
Title: Automatic sequences and curves over finite fields
Abstract:
A theorem of Christol states that a power series $y$ over the finite field $\mathbb{F}_q$ is an algebraic function if and only if its coefficient sequence can be produced by a finite automaton that reads the base-$q$ expansions of positive integers.
The proof uses combinatorics and linear algebra, but hidden in the theorem there is geometric information about a curve that contains $y$ in its function field.
I make this explicit by demonstrating a precise link between the complexity of the automaton and the geometry of the curve.
Joint work with Ferit Toska.
Title: The Principle of Typicality
Abstract:
This is a sequel to our presentation at CCR 2014. The notion of probability plays a crucial role in quantum mechanics. It appears as the Born rule. In modern mathematics which describes quantum mechanics, however, probability theory means nothing other than measure theory, and therefore any operational characterization of the notion of probability is still missing in quantum mechanics. At CCR 2014 we presented an alternative rule to the Born, using the notion of Martin-Löf randomness with respect to Bernoulli measure for specifying the property of the results of quantum measurements in an operational way. This alternative rule is about pure states. In this talk we generalize this alternative rule over mixed states. We then show that all of our new rules about quantum measurements based on algorithmic randomness, including the alternative rule to the Born rule about pure states and its generalization over mixed states, can be derived from a single postulate, called the principle of typicality, in a unified way.
Title: Bounding rationality with computation
8:00-12:20 Keller Hall 302 (leave by 12:20 to make space for a class at 12:30)
12:30-3:45 Keller Hall 301
Potential times for sessions
Local organizers Khan, Kjos-Hanssen, Beros, Ross will be teaching at some times.
Monday
8:30 – 9:20
9:30 – 10:20 (Khan teaching)
10:30 – 11:20
11:30 – 12:20 (Kjos-Hanssen teaching; Ross teaching logic)
12:30 – 1:20 (Khan teaching)
1:30 – 2:20 (Kjos-Hanssen teaching; Ross teaching logic)
2:30 – 3:20