Pavol Duris

MFCS Conference 2020 Conference Paper

Randomization in Non-Uniform Finite Automata

• Pavol Duris
• Rastislav Královic
• Richard Královic
• Dana Pardubská
• Martin Pasen
• Peter Rossmanith

The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization.

MFCS Conference 2001 Conference Paper

On the Computational Complexity of Infinite Words

• Pavol Duris
• Ján Manuch

Abstract This paper contains answers to several problems in the theory of the computational complexity of infinite words. We show that the problem whether all infinite words generated by iterating dgsm’s have logarithmic space complexity is equivalent to the open problem asking whether the unary classes of languages in P and in DLOG are equivalent. Similarly, the problem to find a concrete infinite word which cannot be generated in logarithmic space is equivalent to the problem to find a concrete language which does not belong to DSPACE( n ). Finally, we separate classes of infinite words generated by double and triple D0L TAG systems.

MFCS Conference 1994 Invited Paper

E-Complete Sets Do Not Have Optimal Polynomial Time Approximations

• Pavol Duris
• José D. P. Rolim

Abstract The p-levelability of intractable sets that are, for example, honestly paddable, or monotone self-reducible in certain restricted way, or complete for deterministic time classes is known, more particularly, all E-complete sets are p-levelable[5]. However, the extension of these results to a more general “unsafe” approximation notion has remained as a challenge for a few years. In this paper we address these questions; our main result can be stated as follows. Let k be any natural number. Then each E-complete set is levelable as well as Δ -levelable with density n k. This result extends the corresponding result mentioned above to “unsafe” approximation model and moreover it characterizes “density” of levelability for both models, “safe” and “unsafe” as well. In this paper, we also compare levelability with Δ -levelability and we show in this context that there are sets A, B and C in E-P such that A is levelable as well as Δ -levelable with exponential density, B is not levelable but it is Δ -levelable with exponential density, and C is not levelable and if C is Δ -levelable with a density f(n) then f(n) ≤log * n + 1 for all n. Our proof technique is not based on paddability — it is based on diagonalization against all algorithms and polynomial time bounds.

I&C Journal 1987 Journal Article

Lower bounds on communication complexity

• Pavol Duris
• Zvi Galil
• Georg Schnitger

We prove the following four results on communication complexity: (1) For every k ≥ 2, the language of encodings of directed graphs of out-degree one that contain a path of length k + 1 from the first vertex to the last vertex can be recognized by exchanging O(k log n)1 bits using a simple k-round protocol and requires the exchange of Ω( n 1 2 (k4 log 3 n) ) bits by any (k − 1)-round protocol. (2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets L k n ⊆ {0, 1}2n that can be recognized by exchanging O(k log n) bits using a k-round protocol, and any (k − 1)-round protocol recognizing L k n requires the exchange of Ω( n k ) bits. (3) Given a set L ⊆ {0, 1}2n, there is a set L ⊆ {0, 1}8n such that any (k-round) protocol recognizing L can be transformed to a (k-round) fixed-partition protocol recognizing L with the same communication complexity, and vice versa. (4) For every integer function f, 1 ≤ f(n) ≤ n, there are languages recognizable by a one-round deterministic protocol exchanging f(n) bits, but not by any nondeterministic protocol exchanging f(n) − 1 bits. The first two results show in an incomparable way an exponential gap between (k − 1)-round and k-round protocols, settling a conjecture by Papadimitriou and Sipser. The third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function f, 1 ≤ f(n) ≤ n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any deterministic protocol exchanging f(n) − 1 bits.

FOCS Conference 1987 Conference Paper

Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)

• Pavol Duris
• Zvi Galil

We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.

STOC Conference 1984 Conference Paper

Lower Bounds on Communication Complexity

• Pavol Duris
• Zvi Galil
• Georg Schnitger

We prove the following four results on communication complexity: 1) For every k ≥ 2, the language L k of encodings of directed graphs of out degree one that contain a path of length k+1 from the first vertex to the last vertex and can be recognized by exchanging O(k log n) bits using a simple k-round protocol requires exchanging Ω(n 1/2 /k 4 log 3 n) bits if any (k-1)- round protocol is used. 2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets L n k @@@@ {0,1} 2n that can be recognized by exchanging O(k log n) bits using a k-round protocol, and any (k-1)-round protocol recognizing L n k requires exchanging Ω(n/k) bits. 3) Given a set L @@@@ {0,1} 2n , there is a set L@@@@{0,1} 8n such that any (k-round) protocol recognizing L@@@@ can be transformed to a (k-round) fixed partition protocol recognizing L with the same communication complexity, and vice versa. 4) For every integer function f, 1 ≤f(n) ≤ n, there are languages recognized by a one round deterministic protocol exchanging f(n) bits, but not by any nondeterministic protocol exchanging f(n)-1 bits. The first two results show in an incomparable way an exponential gap between (k-1)-round and k-round protocols, settling a conjecture by Papadimitriou and Sipser. The third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function f, 1 ≤ f(n) ≤ n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any deterministic protocol exchanging f(n) - 1 bits.

STOC Conference 1983 Conference Paper

Two Nonlinear Lower Bounds

• Pavol Duris
• Zvi Galil
• Wolfgang J. Paul
• Rüdiger Reischuk

TCS Journal 1982 Journal Article

Fooling a two way automation or one pushdown store is better than one counter for two way machines

• Pavol Duris
• Zvi Galil

We define a language L and show that it cannot be recognized by any two way deterministic counter machine. It is done by fooling any given such machine; i. e. showing that if it accepts L' ⊇ L, then L' − L ≠ Ø. For this purpose, an argument stronger than the well-known crossing sequence argument needs to be introduced. Since L is accepted by a two-way deterministic pushdown automation, we consequently show that one pushdown stack is more powerful than one counter for deterministic two way machines.

STOC Conference 1982 Conference Paper

Two Tapes are Better than One for Nondeterministic Machines

• Pavol Duris
• Zvi Galil

FOCS Conference 1981 Conference Paper

A Time-Space Tradeoff for Language Recognition

• Pavol Duris
• Zvi Galil

We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.

STOC Conference 1981 Conference Paper

Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)

• Pavol Duris
• Zvi Galil