Share to FacebookShare to TwitterShare by Email

Recently Added

  • Workload characterization of the shared/buy-in computing cluster at Boston University 

    Klausner, Yonatan; Liao, Christopher; Simhon, Eran; Bestavros, Azer; Starobinski, D. (2016)
    Computing clusters provide a complete environment for computational research, including bio-informatics, machine learning, and image processing. The Shared Computing Cluster (SCC) at Boston University is based on a ...
  • Algorithmic tests and randomness with respect to a class of measures 

    Bienvenu, Laurent; Gacs, Peter; Hoyrup, Mathieu; Rojas, Cristobal; Shen, Alexander (MAIK NAUKA/INTERPERIODICA/SPRINGER, 2011-10-01)
    This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the ...
  • Uniform test of algorithmic randomness over a general space 

    Gacs, Peter (Elsevier Science BV, 2005-09-05)
    The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. ...
  • Clairvoyant embedding in one dimension 

    Gacs, Peter (Wiley-Blackwell, 2015-10-01)
    Let v, w be infinite 0‐1 sequences, and urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0001 a positive integer. We say that urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0002 is urn:x-wiley:10429832:media:rsa20551 ...
  • Compatible sequences and a slow Winkler percolation 

    Gacs, Peter (Cambridge University Press, 2004-11-01)
    Two infinite 0–1 sequences are called compatible when it is possible to cast out $0\,$s from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two ...
  • Information distance 

    Bennett, Charles H.; Gacs, Peter; Li, Ming; Vitanyi, Paul M.B.; Zurek, Wojciech H. (IEEE, 1998-07-01)
    While Kolmogorov (1965) complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distance between two individual objects, ...
  • Reliable cellular automata with self-organization 

    Gacs, Peter (SPRINGER, 2001-04-01)
    In a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information indefinitely is nontrivial, even in an infinite automaton. Still, there is a ...
  • Deterministic computations whose history is independent of the order of asynchronous updating 

    Gács, Péter (2001)
    Consider a network of processors (sites) in which each site x has a finite set N(x) of neighbors. There is a transition function f that for each site x computes the next state \xi(x) from the states in N(x). But these ...
  • The clairvoyant demon has a hard task 

    Gacs, Peter (CAMBRIDGE UNIV PRESS, 2000-09-01)
    Consider the integer lattice L = ℤ2. For some m [ges ] 4, let us colour each column of this lattice independently and uniformly with one of m colours. We do the same for the rows, independently of the columns. A point of ...
  • A Toom rule that increases the thickness of sets 

    Gács, Peter (Plenum Publishing Corporation, 1990-04-01)
    Toom's north-east-self voting cellular automaton ruleR is known to suppress small minorities. A variant,R+, is also known to turn an arbitrary initial configuration into a homogeneous one (without changing the ones that ...

View more