Arrow Research search

Author name cluster

Janos Simon

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
2 author rows

Possible papers

19

TCS Journal 2004 Journal Article

Bounding the firing synchronization problem on a ring

  • André Berthiaume
  • Todd Bittner
  • Ljubomir Perković
  • Amber Settle
  • Janos Simon

In this paper we improve the upper and lower bounds on the complexity of solutions to the firing synchronization problem on a ring. In this variant of the firing synchronization problem the goal is to synchronize a ring of identical finite automata. Initially, all automata are in the same state except for one automaton that is designated as the initiator for the synchronization. The goal is to define the set of states and the transition function for the automata so that all machines enter a special fire state for the first time and simultaneously during the final round of the computation. In our work we present two solutions to the ring firing synchronization problem, an 8-state minimal-time solution and a 6-state non-minimal-time solution. Both solutions use fewer states than the previous best-known minimal-time automaton, a 16-state solution due to Culik. We also give the first lower bounds on the number of states needed for solutions to the ring firing synchronization problem. We show that there is no 3-state solution and no 4-state, symmetric, minimal-time solution for the ring.

Details DOI

TCS Journal 2002 Journal Article

Smaller solutions for the firing squad

  • Amber Settle
  • Janos Simon

In this paper we improve the bounds on the complexity of solutions to the firing squad problem, also known as the firing synchronization problem. In the firing synchronization problem we consider a one-dimensional array of n identical finite automata. Initially all automata are in the same state except for one automaton designated as the initiator for the synchronization. Our results hold for the original problem, where the initiator may be located at either endpoint, and for the variant where any one of the automata may be the initiator, called the generalized problem. In both cases, the goal is to define the set of states and transition rules for the automata so that all machines enter a special fire state simultaneously and for the first time during the final round of the computation. In our work we improve the construction for the best known minimal-time solution to the generalized problem by reducing the number of states needed and give non-minimal-time solutions to the original and generalized problem that use fewer states than the corresponding minimal-time solutions.

Details DOI

TCS Journal 2000 Journal Article

On the bottleneck counting argument

  • Janos Simon
  • Shi-Chun Tsai

Both the bottleneck counting argument (Haken, Theoret. Comput. Sci. 39 (1985) 297–308; Proc. 36th Symp. of Foundations of Computer Science, 1995, pp. 36–44) and Razborov's approximation method (Alon and Boppana, Combinatorica 7(1) (1987) 1–22; Andreev, Soviet Math. Dokl 31(1985) 530–534; Rayborov, Soviet Math. Dokl 31 (1985) 354–357) have been used to prove exponential lower bounds for monotone circuits. We show that under the monotone circuit model for every proof by the approximation method, there is a bottleneck counting proof and vice versa. We also illustrate the elegance of the bottleneck counting technique with a simple self-explained example: the proof of a (previously known) lower bound for the 3- CLIQUE n problem by the bottleneck counting argument.

Details DOI

FOCS Conference 1986 Conference Paper

Complexity classes in communication complexity theory (preliminary version)

  • László Babai
  • Peter Frankl
  • Janos Simon

We take a complexity theoretic view of A. C. Yao's theory of communication complexity. A rich structure of natural complexity classes is introduced. Besides providing a more structured approach to the complexity of a variety of concrete problems of interest to VLSI, the main objective is to exploit the analogy between Turing machine (TM) and communication complexity (CC) classes. The latter provide a more amicable environment for the study of questions analogous to the most notorious problems in TM complexity. Implicitly, CC classes corresponding to P, NP, coNP, BPP and PP have previously been considered. Surprisingly, pcc = Npcc ∩ coNPcc is known [AUY]. We develop the definitions of PSPACEcc and of the polynomial time hierarchy in CC. Notions of reducibility are introduced and a natural complete member in each class is found. BPPcc ⊆ Σ2cc ∩ Π2cc [Si2] remains valid. We solve the question that BPPcc ⊉ NPcc by proving an Ω(√n) lower bound for the bounded-error complexity of the coNPcc- complete problem "disjointness". Similar lower bounds follow for essentially any nontrivial monotone graph property. Another consequence is that the deterministically exponentially hard "equality" relation is not NPcc-hard with respect to oracle-protocol reductions. We prove that the distributional complexity of the disjointness problem is O(√n log n) under any product measure on {0, 1}n × {0, 1}n. This points to the difficulty of improving the Ω(√n) lower bound for the B2PP complexity of "disjointness". The variety of counting and probabilistic classes appears to be greater than in the Turing machine versions. Many of the simplest graph problems (undirected reachability, planarity, bipartiteness, 2-CNF-satisfiability) turn out to be PSPACEcc-hard. The main open problem remains the separation of the hierarchy, more specifically, the conjecture that Σ2cc ≠ Π2cc. Another major problem is to show that PSPACEcc and the probabilistic class UPPcc are not comparable.

Details

FOCS Conference 1984 Conference Paper

Probabilistic Communication Complexity (Preliminary Version)

  • Ramamohan Paturi
  • Janos Simon

We study (unbounded error) probabilistic communication complexity. Our new results include -one way and two complexities differ by at most 1 - certain functions like equality and the verification of Hamming distance have upper bounds that are considerably better than their counterparts in deterministic, nondeterministic, or bounded error probabilistic model - there exists a function which requires /spl Omega/(logn) information transfer. As an application, we prove that a certain language requires /spl Omega/(nlogn) time to be recognized by a 1-tape (unbounded error) probabilistic Turing machine. This bound is optimal. (Previous lower bound results [Yao 1] require acceptance by bounded error computation. We believe that this is the first nontrivial lower bound on the time required by unrestricted probabilistic Turing machines.

Details

FOCS Conference 1983 Conference Paper

Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version)

  • Piotr Berman
  • Janos Simon

It is likely that reliable and fast space-bounded probabilistic acceptors are less powerful than nondeterministic ones. We consider a restricted model of space-bounded probabilistic computation, the random analog of a model studied in [CR]. We show that maze traversal (a complete problem for nondeterministic space log n) requires space Ω(log2n/loglogn) by random machines, even if 'fast' is relaxed to mean only 'subexponential'. In particular, the lower bound on space holds for the time complexity of Savitch's algorithm (which can be simulated in the model).

Details

FOCS Conference 1983 Conference Paper

Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version)

  • Ramamohan Paturi
  • Janos Simon

We study probabilistic on-line simulators for several machine models (or memory structures). The simulators have a more constrained access to data than the virtual machines, but are allowed to use probabilistic means to improve average access time. We show that in many cases coin tosses can not make up for inadequate access.

Details

STOC Conference 1982 Conference Paper

Space-Bounded Hierarchies and Probabilistic Computations

  • Walter L. Ruzzo
  • Janos Simon
  • Martin Tompa

This paper studies two aspects of the power of space-bounded probabilistic Turing machines. Section 2 presents a simple alternative proof of Simon's recent result [13] that space-bounded probabilistic complexity classes are closed under complement. Section 3 demonstrates that any language in the log n space hierarchy can be recognized by an log n space-bounded probabilistic Turing machine with small error; this is a generalization of Gill's result that any language in NSPACE(log n) can be recognized by such a machine

Details

TCS Journal 1981 Journal Article

On tape-bounded probabilistic Turing machine acceptors

  • Janos Simon

A probabilistic Turing machine acceptor is a Turing machine acceptor that flips unbiased coins to decide what its next move will be and accepts its input if the probability of reaching a final accepting is greater than 1 2. We show that deterministic and probabilistic tape complexities are polynomially related.

Details DOI

FOCS Conference 1979 Conference Paper

Division Is Good

  • Janos Simon

We study the power of RAM acceptors with several instruction sets. We exhibit several instances where the availability of the division operator increases the power of the acceptors. We also show that in certain situations parallelism and stochastic features ('distributed random choices') are provably more powerful than either parallelism or randomness alone. We relate the class of probabilistic Turing machine computations to random access machines with multiplication (but without boolean vector operations). Again, the availability of integer division seems to play a crucial role in these results.

Details
v2026.09.13