ICS 2010
|
|
Welcome to ICS2010
Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 1-19,
978-7-302-21752-7
Tsinghua University Press
Computation in the physical world is restricted by the following spatial locality constraint: In a single unit of time, information can only travel a bounded distance in space. A simple computational model which captures this constraint is a cellular automaton: A discrete dynamical system in which cells are placed on a grid and the state of each cell is updated via a local deterministic rule that depends only on the few cells within its close neighborhood. Cellular automata are commonly used to model real world systems in nature and society. Cellular automata were shown to be capable of a highly complex behavior. However, it is not clear how fast this complexity can evolve and how common it is with respect to all possible initial config-urations. We examine this question from a computational perspective, identifying “complexity” with computational intractability. More concretely, we consider an n-cell automaton with a random initial configuration, and study the minimal number of computation steps t = t(n) after which the following problems can become computationally hard: • The inversion problem. Given the configuration y at time t, find an initial configuration x which leads to y in t steps. • The prediction problem. Given an arbitrary sequence of ℓ > n intermediate values of cells in the computation, predict some value in the sequence based on the previous values with a significant advantage over guessing. These two problems capture the natural goals of inferring the past from the present and predicting the future based on partial observations of the past. Our main results show that, under widely believed con-jectures, there are cellular automata for which both problems become hard even after a single computa-tion step. This is done by constructing cryptographic one-way functions and pseudorandom generators which are computed by a single step of a cellular automaton. Our results support the view that computa-tional forms of complexity can emerge from simple local interactions in a very common and immediate way.Our results build on and strengthen previous results of Applebaum et al. (FOCS 2004, CRYPTO 2007) on the parallel complexity of cryptography. These previous works implement cryptographic primitives by circuits with constant depth, constant fan-in and constant fan-out, but inherently fail to satisfy the strong spatial locality requirement. Preview: 
|
Copyright 2009-2010, Institute for Computer Science, Tsinghua University, All Rights Reserved.