Author name cluster
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.
TCS Journal 2016 Journal Article
We prove a general lower bound on the size of switching-and-rectifier networks over any semiring of zero characteristic, including the ( min , + ) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum operations are allowed.
SODA Conference 2011 Conference Paper
TCS Journal 2011 Journal Article
Already 30 years ago, Chvátal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules. We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution.
I&C Journal 2010 Journal Article
We study the most important probabilistic computation modes for pushdown automata. First we show that deterministic pushdown automata (pda) are weaker than Las Vegas pda, which in turn are weaker than one-sided-error pda. Next one-sided-error pda are shown to be weaker than (nondeterministic) pda. Finally bounded-error two-sided error pda and nondeterministic pda are incomparable. To show the limited power of bounded-error two-sided pda we apply communication arguments; in particular we introduce a non-standard model of communication which we analyze with the help of the discrepancy method. The power of randomization for pda is considerable, since we construct languages which are not deterministic context-free (resp. not context-free) but are recognizable with even arbitrarily small error by one-sided-error (resp. bounded-error) pda. On the other hand we show that, in contrast to many other fundamental models of computing, error probabilities can in general not be decreased arbitrarily: we construct languages which are recognizable by one-sided-error pda with error probability 1 2, but not by one-sided-error pushdown automata with error probability p < 1 2. A similar result, with error probability 1 3, holds for bounded-error two-sided error pda.
TCS Journal 2009 Journal Article
In contrast to the minimization of deterministic finite automata (DFA’s), the task of constructing a minimal nondeterministic finite automaton (NFA) for a given NFA is PSPACE-complete. Moreover, there are no polynomial approximation algorithms with a constant approximation ratio for estimating the number of states of minimal NFA’s. Since one is unable to efficiently estimate the size of a minimal NFA in an efficient way, one should ask at least for developing mathematical proof methods that help to prove good lower bounds on the size of a minimal NFA for a given regular language. Here we consider the robust and most successful lower bound proof technique that is based on communication complexity. In this paper it is proved that even a strong generalization of this method fails for some concrete regular languages. “To fail” is considered here in a very strong sense. There is an exponential gap between the size of a minimal NFA and the achievable lower bound for a specific sequence of regular languages. The generalization of the concept of communication protocols is also strong here. It is shown that cutting the input word into 2 O ( n 1 / 4 ) pieces for a size n of a minimal nondeterministic finite automaton and investigating the necessary communication transfer between these pieces as parties of a multiparty protocol does not suffice to get good lower bounds on the size of minimal nondeterministic automata. It seems that for some regular languages one cannot really abstract from the automata model that cuts the input words into particular symbols of the alphabet and reads them one by one using its input head.
TCS Journal 2007 Journal Article
The construction of an ε -free nondeterministic finite automaton (NFA) from a given NFA is a basic step in the development of compilers and computer systems. The standard conversion may produce an ε -free NFA with up to Ω ( n 2 ⋅ | Σ | ) transitions for an NFA with n states and alphabet Σ. To determine the largest asymptotic gap between the minimal number of transitions of NFAs and their equivalent ε -free NFAs has been a longstanding open problem. We show that there exist regular languages L n that can be recognized by NFAs with O ( n log 2 n ) transitions, but ε -free NFAs need Ω ( n 2 ) transitions to accept L n. Hence the standard conversion cannot be improved drastically. However, L n requires an alphabet of size n, but we also construct regular languages K n over { 0, 1 } with NFAs of size O ( n log 2 n ), whereas ε -free NFAs require size n ⋅ 2 c ⋅ log 2 n for every c < 1 / 2.
TCS Journal 2005 Journal Article
One-way two-counter machines represent a universal model of computation. Here we consider the polynomial-time classes of multicounter machines with a constant number of reversals and separate the computational power of nondeterminism, randomization and determinism. For instance, we show that polynomial-time one-way multicounter machines, with error probability tending to zero with growing input length, can recognize languages that cannot be accepted by polynomial-time nondeterministic two-way multicounter machines with a bounded number of reversals. A similar result holds for the comparison of determinism and one-sided-error randomization, and of determinism and Las Vegas randomization.
I&C Journal 2004 Journal Article
We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the degree of non-obliviousness is established by proving that, using k +1 partitions instead of k may decrease the communication complexity from Θ (n) to Θ (log k). 2. Certain linear codes are hard for k-partition protocols even when k may be exponentially large (in the input size). On the other hand, one can show that all characteristic functions of linear codes are easy for randomized OBDDs. 3. It is proved that there are subfunctions of the triangle-freeness function and the function ⊕Clique 3, n that are hard for multi-partition protocols. As an application, strongly exponential lower bounds on the size of nondeterministic read-once branching programs for these functions are obtained, solving an open problem of Razborov [Proceedings of eighth FCT NCS 529, Springer, 1991, pp. 47–60].
I&C Journal 2002 Journal Article
While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows: 1. Deterministic communication complexity provides lower bounds on the size of nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way. 2. There is a family of languages KON k 2 with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by B. Ravikumar and O. Ibarra (1989, SIAM J. Comput. 18, 1263–1282) and H. Leung (1998, SIAM J. Comput. 27, 1073–1082).
I&C Journal 2001 Journal Article
The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, ordered binary decision diagrams, and finite automata. (i) For the one-way communication complexity of two-party protocols we show that Las Vegas communication can save at most one half of the deterministic one-way communication complexity. We also present a language for which this gap is tight. (ii) The result (i) is applied to show an at most polynomial gap between determinism and Las Vegas for ordered binary decision diagrams. (iii) For the size (i. e. , the number of states) of finite automata we show that the size of Las Vegas finite automata recognizing a language L is at least the square root of the size of the minimal deterministic finite automaton recognizing L. Using a specific language we verify the optimality of this lower bound.
TCS Journal 2001 Journal Article
The investigation of the computational power of randomized computations is one of the central tasks of complexity and algorithm theory. While for one-way finite automata the power of different computational modes was successfully determined, one does not have any nontrivial result relating the power of determinism, Las Vegas and nondeterminism for two-way finite automata. The main results of this paper are as follows. (i) If, for a regular language L, there exist small two-way nondeterministic finite automata for both L and Lʗ, then there exists a small two-way Las Vegas finite automaton for L. (ii) There is a quadratic gap between nondeterminism and Las Vegas for two-way finite automata. (iii) For every k∈ N, there is a regular language Sk such that Sk can be accepted by a two-way Las Vegas finite automaton with O(k) states, but every two-way deterministic finite automaton recognizing Sk has at least Ω(k2/log 2k) states.
MFCS Conference 1997 Invited Paper
Abstract The communication complexity of two-party protocols introduced by Abelson and Yao is one of the most intensively studied complexity measures for computing problems. This is a consequence of the relation of communication complexity to many fundamental (mainly parallel) complexity measures. This paper focuses on the relation between communication complexity and the following three complexity measures of sequential computation: the size of finite automata, the time- and space-complexity measures of Turing machines and the time- and space-complexity for data structure problems. We present a survey of the known relations between communication complexity and these three problem areas and formulate several open problems for further research.
TCS Journal 1996 Journal Article
The methods “Rank” and “Fooling Set” for proving lower bounds on the deterministic communication complexity of Boolean functions are compared. The main results are as follows. 1. (i) For almost all Boolean functions of 2n variables the Rank method provides the lower bound n on communication complexity, whereas the Fooling Set method provides only the lower bound d(n) ⩽ log 2 n + log 2 10. A specific sequence {ƒ2n}n = 1 ∞ of Boolean functions, where ƒ2n has 2n variables, is constructed such that the Rank method provides exponentially higher lower bounds for ƒ2n than the Fooling Set method. 2. (ii) A specific sequence {h 2n } n = 1 ∞ of Boolean functions is constructed such that the Fooling Set method provides a lower bound of n for h 2n, whereas the Rank method provides only (log2 3) 2 · n ≈ 0. 79 · n as a lower bound. 3. (iii) It is proved that lower bounds obtained by the Fooling Set method are better by at most a factor of two compared with lower bounds obtained by the Rank method. These three results together solve the last problem about the comparison of lower bound methods on communication complexity left open in Aho et al. (1983). Finally, it is shown that an extension of the Fooling Set method provides lower bounds that are tight (up to a polynomial) for all Boolean functions.
STOC Conference 1996 Conference Paper
MFCS Conference 1994 Conference Paper
Abstract The methods “Rank” and “Fooling Set” for proving lower bounds on the deterministic communication complexity of Boolean functions are compared. The main results are as follows. (i) The Rank method provides the lower bound n on communication complexity for almost all Boolean functions of 2 n variables, whereas the Fooling Set method provides only the lower bound d(n) ≤ log 2 n + log 2 10. A specific sequence of Boolean functions { f 2n } ∞ n=1 of 2 n variables, is constructed, such that the Rank method provides exponentially higher lower bounds for f 2 n than the Fooling Set method. (ii) A specific sequence of Boolean functions { f 2 n } ∞ n=1 is constructed such that the Fooling Set method provides a lower bound of n for h 2 n, whereas the Rank method provides only (log 2 3)/2 · n ≈ 0. 79 · n as a lower bound. (iii) It is proved that lower bounds obtained by the Fooling Set method are better by at most a factor of two compared with lower bounds obtained by the Rank method. These three results together solve the last problem about the comparison of lower bound methods on communication complexity left open in (Aho, A. V. , Ullman, J. D. , Yannakakis, M. , On notions of information transfer in VLSI circuits, in: Proc. 15th ACM STOC 1983, pp. 133–139). Finally, it is shown that an extension of the Fooling Set method provides lower bounds which are tight (up to a polynomial) for all Boolean functions.
I&C Journal 1992 Journal Article
We show that for some positive constant c it is not feasible to approximate Independent Set (for graphs of n vertices) within a factor of n c, provided Maximum 2-Satisfiability does not have a randomized polynomial time approximation scheme. We also study reductions preserving the quality of approximations and exhibit complete problems.
NeurIPS Conference 1992 Conference Paper
We compare activation functions in terms of the approximation power of their feedforward nets. We consider the case of analog as well as boolean input.
FOCS Conference 1991 Conference Paper
The power of constant depth circuits with sigmoid (i. e. , smooth) threshold gates for computing Boolean functions is examined. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size Boolean threshold circuits (i. e. , circuits with Boolean threshold gates). On the other hand it turns out that, for any constant depth d, polynomial size sigmoid threshold circuits with polynomially bounded weights compute exactly the same Boolean functions as the corresponding circuits with Boolean threshold gates. >
TCS Journal 1991 Journal Article
This paper contains the first concrete lower bound argument for Turing machines with one worktape and a two-way input tape (“one-tape off-line Turing machines”): an optimal lower bound of Ω(n·l/⌈( log(l) p ) 1 2 ⌉) for transposing an I × l-matrix with elements of bit length p on such machines is proved. (The length of the input is denoted by n.) A special case is a lower bound of Ω( n 3 2 (log n) 1 2 ) for transposing Boolean l × l-matrices (n = l 2) on such Turing machines. The proof of the matching upper bound (which is nontrivial for p<logl) uses the fact that one-tape off-line Turing machines can copy strings slightly faster than if the straightforward method is used. As a corollary of the lower bound it is shown that sorting n (3 log n) strings of 3 log n bits each takes Ω( n 3 2 (log n) 1 2 )steps on one-tape off-line Turing machines. Further corollaries give the first non-linear lower bound for the version of the two-tapes-versus-one problem concerning one-tape off-line Turing machines, and separate one-tape off-line Turing machines from those Turing machines with one input tape, one worktape, and an additional write-only output tape.
I&C Journal 1990 Journal Article
We show the following results for rounds/time trade-offs in the two person pebble game: 1. 1. For every R and n (R = O( n logn )), there is a bounded degree graph of n vertices for which the Pebbler can win in R rounds only in time Ω( n logR ). 2. 2. There is a graph that exhibits almost tight round/time trade-offs for all rounds. 3. 3. There is no graph with tight round/time trade-offs for all rounds. As a consequence, we improve the simulation of bounded fan-in circuits by unbounded fan-in circuits, extending the size/depth trade-off of Paterson and Valiant.
STOC Conference 1988 Conference Paper
I&C Journal 1987 Journal Article
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.
STOC Conference 1987 Conference Paper
STOC Conference 1984 Conference Paper
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.
FOCS Conference 1983 Conference Paper
For each ε(0 ≤ ε ≪ 1) a family Gn =(V(Gn), E(Gn)) of a cyclic digraphs can be constructively defined having the following properties: (a) #V(Gn) ≤ n · 2n+2 (b) degree (Gn) ≤ constant (c) it is necessary to remove Ω(n · 2n) edges in order to reduce the depth of Gn to (2n)ε. It is then shown: For suitable constants c1, C2 ≫ 0, there are (fn, n)- grates (see Definition 1) of size linear in n, where fn(x): = c1 · n2 x ≤ c2 ≤'; n/0 otherwise
TCS Journal 1982 Journal Article
A family of directed acyclic graphs Gn with 2 n+1−1 nodes, n · 2 n edges and depth 2 n+1−2 is constructed having the property: For any ε (0⩽ε<1) it is necessary to remove ω(n · 2 n ) edges in order to reduce the depth of Gn to (2 n ) ε.
FOCS Conference 1982 Conference Paper