7441506
Derandomization and distinguishing complexity
We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [E. Allender (2001), E. Allender et al., (2002)]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits [P. B. Miltersen et al., (1999), R. Shaltiel et al., (2001)]. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity CND of [H. Buhrman et al., (2002)]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in [E. Allender (2001), E. Allender et al., (2002)] have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP/spl sube/NC and NEXP/spl sube/L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.
14665111
Oblivious Symmetric Alternation
We introduce a new class $\rm {O}^p_2$ as a subclass of the symmetric alternation class $\rm {S}^p_2$. An $\rm {O}^p_2$ proof system has the flavor of an $\rm {S}^p_2$ proof system, but it is more restrictive in nature. In an $\rm {S}^p_2$ proof system, we have two competing provers and a verifier such that for any input, the honest prover has an irrefutable certificate. In an $\rm {O}^p_2$ proof system, we require that the irrefutable certificates depend only on the length of the input, not on the input itself. In other words, the irrefutable proofs are oblivious of the input. For this reason, we call the new class oblivious symmetric alternation. While this might seem slightly contrived, it turns out that this class helps us improve some existing results. For instance, we show that if NP⊂P/poly then $\rm PH = {O}^p_2$, whereas the best known collapse under the same hypothesis was $\rm PH = {S}^p_2$. 
 
We also define classes $\rm Y{O}^p_2$ and $\rm N{O}^p_2$, bearing relations to $\rm {O}^p_2$ as NP and coNP are to P, and show that these along with $\rm {O}^p_2$ form a hierarchy, similar to the polynomial hierarchy. We investigate other inclusions involving these classes and strengthen some known results. For example, we show that $\rm MA \subseteq N{O}^p_2$ which sharpens the known result $\rm MA \subseteq {S}^p_2$ [16]. Another example is our result that $\rm AM \subseteq O_2 \cdot NP \subseteq {\prod}^p_2$, which is an improved upper bound on AM. Finally, we also prove better collapses for the 2-queries problem as discussed by [12,1,7]. We prove that $\rm P^{NP[1]} = P^{NP[2]} \Longrightarrow PH = {NO}^p_2 \cap Y{O}^p_2$.
411400
Parity Problems in Planar Graphs
We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2k, for constant k. On the other hand, we show that for any other modulus and in the non-modular case, our problem is as hard in the planar case as for the case of arbitrary graphs. This completely settles the question regarding the complexity of modular computation of the number of spanning trees in planar graphs. The techniques used rely heavily on algebraic-topology. In the spirit of counting problems modulo 2k, we also exhibit a highly parallel oplusL algorithm for finding the value of a Permanent modulo 2k. Previously, the best known result in this direction was Valiant's result that this problem lies in P.
9807325
A Fast Algorithm for Point Labeling Problem
In the map labeling problem, we are given a set P = {p1, p2, . . . , pn} of point sites distributed on a 2D map. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of map labeling problem where (i) the height of the label of each point is the same but its length may be different from the others, (ii) the label of a point pi touches the point at one of its four corners and (iii) it does not obscure any other point in P . We describe an efficient heuristic algorithm for this problem which runs in O(n √ n) time in the worst case. We run our algorithm as well as the algorithm proposed in [14] on the available benchmarks [13]. The results produced by our algorithm is same as that of [14] in most of the cases, and is one less in few cases. But the time taken by our algorithm is much less than [14].
1879700
Hand gesture modelling and recognition involving changing shapes and trajectories, using a Predictive EigenTracker
We present a novel eigenspace-based framework to model a dynamic hand gesture that incorporates both hand shape as well as trajectory information. We address the problem of choosing a gesture set that models an upper bound on gesture recognition efficiency. We show encouraging experimental results on a such a representative set.
1283699
ConvexSmooth: a simultaneous convex fitting and smoothing algorithm for convex optimization problems
Convex optimization problems are very popular in the VLSI design society due to their guaranteed convergence to a global optimal point. Table data is often fitted into analytical forms like posynomials to make them convex. However, fitting the look-up tables into posynomial forms with minimum error itself may not be a convex optimization problem and hence excessive fitting errors may be introduced. In recent literature numerically convex tables have been proposed. These tables are created optimally by minimizing the perturbation of data to make them numerically convex. But since these tables are numerical, it is extremely important to make the table data smooth, and yet preserve its convexity. Smoothness will ensure that the convex optimizer behaves in a predictable way and converges quickly to the global optimal point. In this paper, we propose to simultaneously create optimal numerically convex look-up tables and guarantee smoothness in the data. We show that numerically "convexifying" and "smoothing" the table data with minimum perturbation can be formulated as a convex semidefinite optimization problem and hence optimality can be reached in polynomial time. We present our convexifying and smoothing results on industrial cell libraries. ConvexSmooth shows 14times reduction in fitting error over a well-developed posynomial fitting algorithm
13954615
An algorithm for trading off quantization error with hardware resources for MATLAB-based FPGA design
Most practical FPGA designs of digital signal processing (DSP) applications are limited to fixed-point arithmetic owing to the cost and complexity of floating-point hardware. While mapping DSP applications onto FPGAs, a DSP algorithm designer must determine the dynamic range and desired precision of input, intermediate, and output signals in a design implementation. The first step in a MATLAB-based hardware design flow is the conversion of the floating-point MATLAB code into a fixed-point version using "quantizers" from the filter design and analysis (FDA) toolbox for MATLAB. This paper describes an approach to automate the conversion of floating-point MATLAB programs into fixed-point MATLAB programs, for mapping to FPGAs by profiling the expected inputs to estimate errors. Our algorithm attempts to minimize the hardware resources while constraining the quantization error within a specified limit. Experimental results on five MATLAB benchmarks are reported for Xilinx Virtex II FPGAs.
16700418
Identity Delegation in Policy Based Systems
Policy based systems have received considerable attention in the recent past from academia as well as the industry. Research on policy based systems encompasses a gamut of areas such as: models and languages for policy based systems, policy standards, domain specific implementations, policy tools etc. However an important issue, which did not receive much attention from researchers, is that of access control for policy execution. In this paper we present the concept of "identity delegation" which involves finding the 'correct' users/ identities, to whom task of policy execution can be delegated. Policies are generally defined by high level business executives (policy authors) and are implemented by policy enforcers who have sufficient access rights on the underlying systems. Given the increasing complexity of enterprise systems, we show in this paper that finding the right policy enforcers for a policy can be a fairly non-trivial task. We address this important problem by proposing a unique concept of 'implicit identity delegation', whereby an autonomic system automatically figures out the correct policy enforcers and implicitly delegates the task of policy execution. We present the Implicit Identity Delegation architecture which boasts of an efficient technique for performing implicit identity delegation and uses a plugin based architecture ensuring its applicability and use in diverse domains.