Lower bounds for monotone span programs

Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs, and contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. We prove a lower bound of (m ^2.5) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.     

On lower bounds for the complexity of polynomials and their multiples

We prove a theorem giving arbitrarily long explicit sequences of algebraic numbers such that any nonzero polynomial f(X) satisfying has nonscalar complexity for some positive constant C independent of s. A similar result is shown for rapidly growing rational sequences. Received: April 6 1999.     

Function-algebraic characterizations of log and polylog parallel time

The main results of this paper are recursion-theoretic characterizations of two parallel complexity classes: the functions computable by uniform bounded fan-in circuit families of log and polylog depth (or equivalently, the functions bitwise computable by alternating Turing machines in log and polylog time). The present characterizations avoid the complex base functions, function constructors, anda priori size or depth bounds typical of previous work on these classes. This simplicity is achieved by extending the tiered recursion techniques of Leivant and Bellantoni & Cook.     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

On the size of randomized OBDDs and read-once branching programs for k-stable functions

In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described.?As an application of this technique, a generic lower bound on the size of randomized OBDDs with bounded error is established for a class of functions which has been studied in the literature on branching programs for a long time. These functions have been called “k-stable” by Jukna. It follows that several standard functions are not contained in the analog of the class BPP for OBDDs. Furthermore, exponential lower bounds on the size of randomized kOBDDs are presented.?It is well known that k-stable functions with large k are hard for deterministic read-once branching programs. This is no longer true in the randomized case. It is shown here that a certain k-stable function due to Jukna, Razborov, Savicky, and Wegener has randomized branching programs of polynomial size, even with zero error. It follows that for the analogs of these classes defined in terms of the size of read-once branching programs. Received: September 3, 1998.     

An n1.618 lower bound on the time to simulate one queue or two pushdown stores by one tape

To simulate two pushdown stores, or one queue, on-line by a one-head tape unit requires Ω(n^1.618) time.     

Volume Maximization and Orthoconvex Approximation of Orthogons

Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks such that the volume of their union becomes maximum. VMP is shown to be -hard in the 2-dimensional case and polynomially solvable for the line via a constrained critical path problem (CCPP) in an acyclic digraph. This CCPP leads to further well solvable special cases of the maximization problem. In particular, the following approximation problem (OAP) becomes polynomially solvable: given an orthogon P (i.e., a simple polygon in the plane which is a union of blocks) and a positive integer q, find an orthoconvex orthogon with at most q vertices and minimum area, which contains P. Received: September 7, 1998     

A Constructive Finite Field Method for Scattering Points on the Surface of <Emphasis Type="Italic">d</Emphasis>-Dimensional Spheres

d +1 variables over finite fields to scatter points on the surface of the unit sphere S ^d , d≥1. Applications are given for spherical t designs and generalized s energies. Received May 2, 2001; revised October 2, 2001 Published online February 18, 2002     

A high quality and small shadow size visual secret sharing scheme based on hybrid strategy for grayscale images

Many secret sharing schemes for digital images have been developed in recent decades. Traditional schemes typically must deal with the problem of computational complexity, and other visual secret sharing schemes come with a higher transmission cost and storage cost; that is, each shadow size is m times as big as the original secret image. The new (2,n) secret sharing scheme for grayscale images proposed in this paper is based a combination of acceptable image quality using block truncation coding (BTC), high compression ratio discrete wavelet transform (DWT) and good subjective performance of the vector quantization (VQ) technique. Experimental results confirm that our proposed scheme not only generates a high quality reconstructed original image but also generates small, random-like grayscale shadows.     

A study of Gaussian mixture models of color and texture features for image classification and segmentation

The aims of this paper are two-fold: to define Gaussian mixture models (GMMs) of colored texture on several feature spaces and to compare the performance of these models in various classification tasks, both with each other and with other models popular in the literature. We construct GMMs over a variety of different color and texture feature spaces, with a view to the retrieval of textured color images from databases. We compare supervised classification results for different choices of color and texture features using the Vistex database, and explore the best set of features and the best GMM configuration for this task. In addition we introduce several methods for combining the ‘color’ and ‘structure’ information in order to improve the classification performances. We then apply the resulting models to the classification of texture databases and to the classification of man-made and natural areas in aerial images. We compare the GMM model with other models in the literature, and show an overall improvement in performance.