Péter Gács

STOC Conference 2002 Conference Paper

Clairvoyant scheduling of random walks

• Péter Gács

Two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. About 10 years ago, Peter Winkler asked the question: for which graphs are two independent walks compatible with positive probability. Up to now, no such graphs were found. We show in this paper that large complete graphs have this property. The question is equivalent to a certain dependent percolation with a power-law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially.

STOC Conference 2001 Conference Paper

Compatible sequences and a slow Winkler percolation

• Péter Gács

FOCS Conference 1997 Conference Paper

Reliable Cellular Automata with Self-Organization

• Péter Gács

In a noisy cellular automaton, even if it is infinite, it is non-trivial to keep a bit of information for more than a constant number of steps. A clever solution in 2 dimensions has been applied to a simple 3-dimensional fault-tolerant cellular automaton. This technique did not solve the following problems: remembering a bit of information in 1 dimension; computing in dimensions lower than 3, or with non-synchronized transitions. With a more complex technique using a hierarchy of simulations, we construct an asynchronous one-dimensional reliable cellular automaton, which is also "self-organizing". This means that if the input information has constant size, the initial configuration can be homogenous: the hierarchy organizes itself. An application to information storage in positive-temperature Gibbs states is also given.

STOC Conference 1993 Conference Paper

Thermodynamics of computation and information distance

• Charles H. Bennett
• Péter Gács
• Ming Li 0001
• Paul M. B. Vitányi
• Wojciech H. Zurek

SODA Conference 1992 Conference Paper

On Playing "Twenty Questions" with a Liar

• Aditi Dhagat
• Péter Gács
• Peter Winkler 0001

STOC Conference 1985 Conference Paper

A Simple Three-Dimensional Real-Time Reliable Cellular Array

• Péter Gács
• John H. Reif

We build a three-dimensional array of unreliable cellular automata that can simulate a universal Turing machine (more generally, a one-dimensional universal iterative array) reliably. This is the first reliable real-time simulation. The encoding is simple repetition, and no decoding is needed. The construction is based on Toom's work.

TCS Journal 1983 Journal Article

On the relation between descriptional complexity and algorithmic probability

• Péter Gács

Several results in Algorithmic Information Theory establish upper bounds on the difference between descriptional complexity and the logarithm of ‘a priori probability’. It was conjectured that these two quantities coincide to within an additive constant. Here, we disprove this conjecture and show that the known overall upper bound on the difference is exact. The proof uses a two-person memory-allocation game between players called User and Server. User sends incremental requests of memory space for certain structured items, Server allocates this space in a write-once memory. For each item, some of the allocated space is required to be in one piece, in order to give a short address. We also present some related results.

STOC Conference 1983 Conference Paper

Reliable Computation with Cellular Automata

• Péter Gács

FOCS Conference 1981 Conference Paper

On the Relation between Descriptional Complexity and Algorithmic Probability

• Péter Gács

Several results in Algorithmic Information Theory establish upper bounds on the difference between descriptional complexity and the logarithm of "apriori probability". It was conjectured that these two quantities coincide to within an additive constant. Here, we disprove this conjecture and show that the known overall upper bound on the difference is exact. The proof uses a memory-allocation game between two players called User and Server. User sends incremental requests of memory space for certain structured items, Server allocates this space in a write-once memory. For each item, some of the allocated space is required to be in one piece, in order to live a short address. We also present some related results.