All posts by admin

IMG_2913
Lance Fortnow, overview, tutorial

Post proceedings

Video

Announcement: Post Proceedings CCR 2016

CCR 2016 was a very successful meeting with lots of new ideas in algorithmic randomness and computability theory. We plan a post-proceedings volume in the journal Theory of Computing Systems.

Editors R. Downey, D. Hirschfeldt, and B. Kjos-Hanssen.

Deadline: 1 July 2016.

Papers related to the theme of the conference (not only from those who attended) will be considered. Normal TOCS standards of acceptance are applied. Early submission is encouraged and such papers will processed at time of submission. Submissions should be original research but high quality survey articles may be considered provided that they also contain significant original research.

Papers should be submitted to the site

‘www.editorialmanager.com/tocs/’

using the article type

“S.I. : CCR 2016 – By Invitation Only”.

Please contact the Vithyaa Bathman (Vithyaa.Bathman [at] springer.com), if you have any queries regarding the submission process.

Uncategorized

Arrival tips

Upon arrival at Honolulu International Airport, withdraw cash from an Automated Teller Machine (ATM) before leaving the secure area. There are no such machines outside the secure area.

If staying in Lincoln Hall, take a taxi to East-West Center by the UH Manoa campus. If arriving late, check in at Hale Manoa down the street from Lincoln Hall.
In Hale Manoa there are cash-based vending machines in case you get hungry. If you anticipate being hungry the night of your arrival you may also consider buying food before leaving the secure area at the airport.

Transportation info:
http://www.math.hawaii.edu/~khan/CCR/Transportation.pdf

Map:
http://www.math.hawaii.edu/~khan/CCR/map-annotated-paths.png

stock-market
Lance Fortnow

Bounding rationality with computation

Tutorial speaker:
Lance Fortnow
Georgia Institute of Technology

Title: Bounding Rationality With Computation

Abstract:
Traditional microeconomic theory treats individuals and institutions as completely understanding the consequences of their decisions given the information they have available. These assumptions might require these agents to solve hard computational problems to optimize our choices. What happens if we restrict the computational power of economic agents?

There has been some work in economics treating computation as a fixed cost or simply considering the size of a program. This series of talks, based on the work of the speaker and others, will explore a new direction bringing the rich tools of computability and computational complexity into economic models.

We show how to incorporate computability and computational complexity into a number of economic models including game theory, prediction markets, forecast testing, preference revelation and awareness. We will suggest a number of further directions worth exploring.

We will not assume any background in economics or computational complexity.

2048px-Lorenz_attractor_yb.svg
Cristobal Rojas

Random perturbations of dynamical systems

Title: Computability and complexity of random perturbations of dynamical systems
Speaker: Cristobal Rojas

A discrete-time dynamical system is specified by a function $f$ from a space $X$ to itself.
One of the most important problems in the study of dynamical systems is to understand the limiting or
asymptotic behavior of such systems; in particular, the limiting distribution of the sequence of iterates
$$
x, f(x), f(f(x)), \dots
$$
Combinations of such distributions give rise to the invariant measures of the system,
which describe the asymptotic behavior in statistical terms.
In this talk we will discuss recent results on computability and complexity of such invariant measures.
In particular, we will present tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system, affected by Gaussian random perturbations.

2000px-Venn0110.svg
Rutger Kuyper

Preservation of randomness under symmetric differences

Speaker: Rutger Kuyper

Joint work with Joseph S. Miller

Title: Preservation of randomness and genericity under symmetric differences

Abstract:

Given a class $\mathcal U$ of subsets of the natural numbers, let us say that a subset $A$ of the natural numbers is $\mathcal U$-stabilising if the symmetric difference (or bitwise addition) $A+X$ of $A$ and $X$ is an element of $\mathcal U$ for every element $X$ of $\mathcal U$.

Several people have asked, using varying terminology, to characterise the Martin-Löf-stabilising sets, i.e. the sets $A$ such that $X+A$ is Martin-Löf random for every Martin-Löf random set $X$. We show that the Martin-Löf-stabilising sets are exactly the $K$-trivial sets.

We also show that the 1-generic-stabilising sets are exactly the computable sets, using an argument which (surprisingly) makes use of Kolmogorov complexity and facts about the $K$-trivial sets.

LFSR_Fibonacci_8_bits
Satyadev Nandakumar

Pseudorandomness and dimension

Speaker: Satyadev Nandakumar

Abstract:
In computational complexity theory, a probability distribution on a
finite set of finite strings is said to be pseudorandom if no
polynomial-size circuit is able to distinguish it from the uniform
distribution on the same set. In this talk, we give an overview of a
recent attempt to apply the theory of effective fractal dimension to
define how close an arbitrary distribution is to being pseudorandom
and relate it to known computational analogues of entropy. We also
study the problem of whether it is possible to extract pseudorandom
bits from a general distribution, analogous to the problem of
extracting random bits from a pseudorandom source.