The on-line interactive Complexity Option Game allows players to test their intuition and knowledge of complexity and American options.
Its companion paper is “Pricing complexity options”, to appear in the journal Algorithmic Finance, joint with Math graduate Malihe Alikhani, and Shidler graduates Amir Pakravan and Babak Saadat.
The paper introduces a thought experiment: a financial derivative based on the complexity of a sequence of up and down ticks of a stock price.
The difficulty of succeeding in this game may be related to the phenomenon of bounded rationality, to be discussed by Lance Fortnow during the 11th International Conference on Computability, Complexity and Randomness, UH Manoa, January 4-8, 2016.
Event Sponsor
Mathematics, Manoa Campus
More Information
Bjørn Kjos-Hanssen, 9568595, bjoern.kjos-hanssen@hawaii.edu, http://math.hawaii.edu/wordpress/bjoern/software/web/complexity-option-game/
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.
Opening remarks
9:45 Erik Guentner (mathematics department chair)
9:46 Rod Downey (PC chair)
9:48 Bjørn Kjos-Hanssen (organizer)
The dinner is at Lulu’s at 6pm at the intersection of Kapahulu and Kalakaua. Note the change since an earlier version on the Google Form. M.K.’s reservation is for 20 people.
A special volume of Theory of Computing Systems is planned edited by Downey, Hirschfeldt, and Kjos-Hanssen.
Session chairs:
Monday
I Greg Igusa (alternate Rutger Kuyper)
II Mushfeq Khan (alternate Hayato Takahashi)
III Stephanie Blanda (alternate Uri Andrews)
IV Linda Brown Westrick (alternate Jake Pardo)
Tuesday
I Lance Fortnow (alternate Ron Peretz)
II Jeffrey Shallit (alternate Adam Case)
III Bjørn Kjos-Hanssen (alternate Rod Downey)
Wednesday
I Rod Downey (alternate Valentina Harizanov)
II Johanna Franklin (alternate Ruper Hölzl)
Thursday
I Dan Turetsky (alternate Linda Brown Westrick)
II Cristobal Rojas (alternate Wolfgang Merkle)
III Achilles Beros (alternate Joe Miller)
IV Kohtaro Tadaki (alternate Mariya Soskova)
Friday
I Satyadev Nandakumar (alternate Andrew Bridy)
II Benoit Monin (alternate Quinn Culver)
Wifi
Network: UHM
Username: conference@math.hawaii.edu
Password: will be written on the whiteboard
Speaker: Linda Brown Westrick.
Title: Seas of squares with sizes from a co-enumerable set
Abstract:
Three prominent classes of two-dimensional subshifts are the shifts of finite type (SFTs), the sofic shifts, and the effectively closed shifts. SFTs are obtained by forbidding finitely many local patterns. A shift is sofic if it is a factor of a SFT, meaning that it is the image of a SFT under a continuous shift-invariant map. And a shift is effectively closed if it is obtained by forbidding a c.e. set of local patterns.
In general, every SFT is sofic and every sofic shift is effectively closed, but the reverse implications do not hold. We would like to know what conditions on a c.e. set of forbidden patterns would guarantee that the resulting shift is not just effectively closed, but sofic. The primary purpose of this work is to expand our inventory of examples and techniques related to this question.
For each co-enumerable $S\subseteq \mathbb{N}$, consider a two-dimensional subshift $X_S$ on the alphabet $\{\text{black}, \text{white}\}$ whose elements consist of black squares of various sizes on a white background, where the side length of each square is in $S$. We show that each $X_S$ is sofic.
The entropy of a sofic shift is always less than or equal to the entropy of the SFT of which is is a factor. In two and more dimensions, it is an open question whether every sofic shift is the factor of a SFT of the same entropy. Our seas of squares do not provide a counterexample: we show that each $X_S$ is a factor of a SFT of the same entropy.
To prove our results, we build upon the self-similar Turing machine tiling construction of Durand, Romashchenko and Shen (2010). They showed that the following class of effectively closed shifts are sofic (this result was also obtained independently by Aubrun and Sablik). For each one-dimensional effectively closed subshift $W$, consider a two-dimensional shift $X_W$ whose elements consist of vertical stripes arranged so that the common row is an element of $W$. In other words, $X_W$ is obtained by “stretching” $W$ into two dimensions.
In their construction, arrays of Turing machines operating a multiple scales work together to “read” the common row, compute the forbidden words of $W$, and kill any elements whose common row contains a forbidden word. The “reading” process makes strong use of the fact that each bit of the common row is repeated infinitely often along an entire column, so the machines have many opportunities to work together to access it.
In our construction, a similar array of Turing machines “measures” the sizes of the squares in a potential element of $X_S$, computes the forbidden sizes, and kills the element if it sees a square of a forbidden size. However, an extra challenge is that each machine must measure and store the size of every single square in its vicinity, since sizes are not necessarily repeated and thus no machine can compensate for another machine overlooking a square. A high density of information must also be communicated between the machines, creating additional challenges.