12090072
Polynomials that Sign Represent Parity and Descartes’ Rule of Signs
Abstract.A real polynomial P(X1, ... , Xn) sign represents f : An → {0, 1} if for every (a1, ... , an) ∈ An, the sign of P(a1, ... ,an) equals $$(-1)^{f(a_{1}, \ldots ,a_{n})}$$. Such sign representations are well-studied in computer science and have applications to computational complexity and computational learning theory. The work in this area aims to determine the minimum degree and sparsity possible for a polynomial that sign represents a function f. While the degree of such polynomials is relatively well-understood, far less is known about their sparsity. Known bounds apply only to the cases where A = {0, 1} or A = {−1, +1}.In this work, we present a systematic study of tradeoffs between degree and sparsity of sign representations through the lens of the parity function. We attempt to prove bounds that hold for any choice of set A. We show that sign representing parity over {0,... , m − 1}n with the degree in each variable at most m − 1 requires sparsity at least mn. We show that a tradeoff exists between sparsity and degree, by exhibiting a sign representation that has higher degree but lower sparsity. We show a lower bound of n(m − 2) + 1 on the sparsity of polynomials of any degree representing parity over {0,... ,m − 1}n. We prove exact bounds on the sparsity of such polynomials for any two element subset A. The main tool used is Descartes’ Rule of Signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. As an application, we use bounds on sparsity to derive circuit lower bounds for depth-two AND-OR-NOT circuits with a Threshold Gate at the top.
18808745
An improved algorithm for quantifier elimination over real closed fields
We give a new algorithm for quantifier elimination in the first order theory of real closed fields that improves the complexity of the best known algorithm for this problem till now. Unlike previously known algorithms the combinatorial part of the complexity of this new algorithm is independent of the number of free variables. Moreover, under the assumption that each polynomial in the input depend only on a constant number of the free variables, the algebraic part of the complexity can also be made independent of the number of free variables. This new feature of our algorithm allows us to obtain a new algorithm for a variant of the quantifier elimination problem. We give an almost optimal algorithm for this new problem, which we call the uniform quantifier elimination problem and apply it to solve a problem arising in the field of constraint databases. No algorithm with reasonable complexity bound was known for this latter problem till now. We also point out interesting logical consequences of this algorithmic result, concerning the expressive power of a constraint query language over the reals. Moreover, our improved algorithm for performing quantifier elimination immediately leads to improved algorithms for several problems for which quantifier elimination is a basic step, for example, the problem of computing the closure of a given semi-algebraic set.
32812813
Design of CAECC-Cellular Automata Based Error Correcting Code
A new scheme for designing error detecting and error correcting codes around cellular automata (CA) is reported. A simple and efficient scheme for generating SEC-DED codes is presented which can also be extended for generating codes with higher distances. A CA-based hardware scheme for very fast decoding (and correcting) of the codewords is also reported. >
33624885
On the combinatorial and topological complexity of a single cell
The problem of bounding the combinatorial complexity of a single connected component (a single cell) of the complement of a set of a geometric objects in R/sup k/, each object of constant description complexity, is an important problem in computational geometry which has attracted much attention over the past decade. It has been conjectured that the combinatorial complexity of a single cell is bounded by a function much closer to O(n/sup k-1/) rather than O(n/sup k/) which is the bound for the combinatorial complexity of the whole arrangement. Till now, this was known to be rule only for k/spl les/3 and only for some special cases in higher dimensions. A classic result in real algebraic geometry due to Oleinik-Petrovsky, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. However, till now no better bounds were known if we restricted attention to a single connected component of a basic semi-algebraic set. In this paper, we show how these two problems are related. We prove a new bound on the sum of the Betti numbers of one connected component of a basic semi-algebraic set which is an improvement over the Oleinik-Petrovsky-Thom-Milnor bound. This also implies that the topological complexity of a single cell, measured by the sum of the Betti numbers, is bounded by O(n/sup k-1/).
24764914
Computing the Betti numbers of arrangements via spectral sequences
In this paper, we consider the problem of computing the Betti numbers of an arrangement of n compact semi-algebraic sets, S1,...,Sn ⊂ Rk, where each Si is described using a constant number of polynomials with degrees bounded by a constant. Such arrangements are ubiquitous in computational geometry. We give an algorithm for computing lth Betti number, β(∪i=1n Si), 0 ≤ l ≤ k - 1 using O(nl+2) algebraic operations. Additionally, one has to perform linear algebra on integer matrices of size bounded by O(nl+2). All previous algorithms for computing the Betti numbers of arrangements, triangulated the whole arrangement giving rise to a complex of size O(n2k) in the worst case. Thus, the complexity of computing the Betti numbers (other than the zeroth one) for these algorithms was O(n2k). To our knowledge this is the first algorithm for computing βl(∪i=1n Si) that does not rely on such a global triangulation, and has a graded complexity which depends on l.
8618090
Computing the first Betti number and the connected components of semi-algebraic sets
In this paper we describe the first singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. We also describe algorithms for obtaining semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set. Singly exponential algorithms for computing the zero-th Betti number, and the Euler-Poincaré characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zero-th one.
121785
Generation of All Counter-Examples for Push-Down Systems
We present a new, on-the-fly algorithm that given a push-down model representing a sequential program with (recursive) procedure calls and an extended finite-state automaton representing (the negation of) a safety property, produces a succinct, symbolic representation of all counter-examples; i.e., traces of system behaviors that violate the property. The class of what we call minimum-recursion loop-free counter-examples can then be generated from this representation on an as-needed basis and presented to the user. Our algorithm is also applicable, without modification, to finite-state system models. Simultaneous consideration of multiple counter-examples can minimize the number of model-checking runs needed to recognize common root causes of property violations. We illustrate the use of our techniques via application to a Java-Tar utility and an FTP-server program, and discuss a prototype tool implementation which offers several abstraction techniques for easy-viewing of generated counter-examples.
13887054
A resource management framework for interactive Grids
Traditional use of Grid computing systems has been for batch jobs in the scientific and academic computing. We envision the next generation Grid computing systems to support graphical interactive sessions. In this paper, we propose a resource management framework for supporting graphical interactive sessions in a Grid computing system. We describe the high-level architectural resource management framework distributed among the submission node, central scheduler node, and the execution node. We then describe in detail the resource management framework on the execution node. The description of the resource management framework on the scheduler node is kept at a high level in this paper. The framework on execution nodes consists of Resource Management Agents, an Admission Control system and Application Predictor system. The agents on the execution node are Startup Agents, Sensor Agents, Monitoring Agents, Aggregator Agents, Enforcement Agents and Registration Agents. The Session Admission Control system is responsible for determining if a new application session can be admitted to the execution node. An Application Predictor system is responsible for predicting the resource utilization behavior of applications based on data obtained from the Resource Management Agents. The proposed framework allows for implementation of a scalable and extensible middleware for interactive Grid resource management. It supports fine-grained performance guarantees specified in service level agreements and brings forth some important and novel contributions to enable graphical interactive sessions on Grids. Copyright © 2004 John Wiley & Sons, Ltd.
8225775
A global lower bound on parameter estimation error with periodic distortion functions
We present a global Ziv-Zakai (1969) type lower bound on the mean square error for estimation of signal parameter vectors, where some components of the distortion function may be periodic. Periodic distortion functions arise naturally in the context of direction of arrival or phase estimation problems. The bound is applied to an image registration problem, and compared to the performance of the maximum-likelihood estimator (MLE).
2261271
Selecting and Composing Web Services through Iterative Reformulation of Functional Specifications
We propose a specification-driven approach to Web service composition. The proposed framework allows users to start with a high-level, possibly incomplete specification of a desired (goal) service that is to be realized using a subset of the available component services. These services are represented by the system using transition systems augmented with guards over variables with infinite domains and are used to determine a strategy for their composition that would realize the goal service. In the event that the goal service cannot be realized using the available services, the system identifies the cause(s) for such failure which can then be used by the developer to reformulate the goal specification. Thus, the system supports Web service composition through iterative refinement of the functional specifications. We present a prototype implementation in tabled-logic programming environment that illustrates the key features of the proposed approach
7011829
QoS aware job scheduling in a cluster-based Web server for multimedia applications
We propose a cluster-based Web server where a few computing nodes are separately reserved for high-performance computing applications, such as multimedia, SSL, and CGI. As an example application, we consider a multimedia server that dynamically generates video units to satisfy the bit rate and bandwidth requirements of a variety of clients. To perform QoS aware scheduling of multiple multimedia jobs on the computing servers, a two-step algorithm is proposed. The first step is to fairly schedule multimedia streams to satisfy each stream's QoS requirement; and the second step is to balance the workload among heterogeneous computing nodes in the cluster. We propose a new quota-based adaptive coscheduling (QACS) algorithm that greatly reduces delay jitter by eliminating the out-of-order departure for outgoing streams, as well as achieves high throughput in a heterogeneous cluster. Experimental results show that the proposed scheduling technique gives adequate QoS guarantees to multiple streams.