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.
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.
TCS Journal 2008 Journal Article
The replication number of a branching program is the minimum number R such that along every accepting computation at most R variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0 (read-once programs) and the total number n of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R = o ( n / log n ). We improve this to R ≤ ϵ n for a constant ϵ > 0. This also gives an alternative and simpler proof of an exponential lower bound for ( 1 + ϵ ) n time branching programs for a constant ϵ > 0. We prove these lower bounds for quadratic functions of Ramanujan graphs.
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].
MFCS Conference 1997 Conference Paper
Abstract It is known that if a Boolean function f in n variables has a DNF and a CNF of size ≤ N then f also has a (deterministic) decision tree of size exp( O (log n log 2 N )). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp ( Ω (log 2 N )) where N is the total number of monomials in minimal DNFs for f and - f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen-Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Whereas other examples have the additional property that f is in AC°.
FOCS Conference 1993 Conference Paper
We present a top-down lower bound method for depth 3 AND-OR-NOT circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular we prove that depth 3 AND-OR-NOT circuits that compute PARITY resp. MAJORITY require size at least 2/sup 0. 618/. .. /spl radic/n/ resp. 2/sup 0. 849/. .. /spl radic/n/. This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits. >
MFCS Conference 1988 Conference Paper
Abstract A general approximation technique to get lower bounds for the complexity of combinational circuits over an arbitrary algebras of operations is presented. The technique generalizes recent methods for monotone circuits and yields some new results. This report contains an exp(Ω(log 2 n)) lower bound for the complexity of realization of non-monotone Boolean functions by circuits over the basis (&, V, -) computing sufficiently many prime implicants, and of three-valued functions by circuits over some incomplete three-valued extensions of (&, V, -).
MFCS Conference 1986 Conference Paper