Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Algorithmic approach to simulate Hamiltonian dynamics and an NMR simulation of quantum state transfer

We propose an iterative algorithm to simulate the dynamics generated by any n-qubit Hamiltonian. The simulation entails decomposing the unitary time evolution operator U (unitary) into a product of different time-step unitaries. The algorithm product-decomposes U in a chosen operator basis by identifying a certain symmetry of U that is intimately related to the number of gates in the decomposition. We illustrate the algorithm by first obtaining a polynomial decomposition in the Pauli basis of the n-qubit quantum state transfer unitary by Di Franco et al. [Phys. Rev. Lett. 101, 230502 (2008)] that transports quantum information from one end of a spin chain to the other, and then implement it in nuclear magnetic resonance to demonstrate that the decomposition is experimentally viable. We further experimentally test the resilience of the state transfer to static errors in the coupling parameters of the simulated Hamiltonian. This is done by decomposing and simulating the corresponding imperfect unitaries.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Conflict-Free Coloring for Rectangle Ranges Using O(n.382) Colors

Given a set of points P ⊆ R2, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each nonempty axisparallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T . This notion has been the subject of recent interest and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R2 can be conflict-free colored with O(nβ∗+o(1)) colors in expected polynomial time, where β∗ = 3−√5 2 < 0.382.

An invariant subspace-based approach to the random eigenvalue problem of systems with clustered spectrum

The repeated or closely spaced eigenvalues and corresponding eigenvectors of a matrix are usually very sensitive to a perturbation of the matrix, which makes capturing the behavior of these eigenpairs very difficult. Similar difficulty is encountered in solving the random eigenvalue problem when a matrix with random elements has a set of clustered eigenvalues in its mean. In addition, the methods to solve the random eigenvalue problem often differ in characterizing the problem, which leads to different interpretations of the solution. Thus, the solutions obtained from different methods become mathematically incomparable. These two issues, the difficulty of solving and the non-unique characterization, are addressed here. A different approach is used where instead of tracking a few individual eigenpairs, the corresponding invariant subspace is tracked. The spectral stochastic finite element method is used for analysis, where the polynomial chaos expansion is used to represent the random eigenvalues and eigenvectors. However, the main concept of tracking the invariant subspace remains mostly independent of any such representation. The approach is successfully implemented in response prediction of a system with repeated natural frequencies. It is found that tracking only an invariant subspace could be sufficient to build a modal-based reduced-order model of the system. Copyright (C) 2012 John Wiley & Sons, Ltd.

On maximum entropy and minimum KL-divergence optimization by Grobner basis methods

In this paper we study constrained maximum entropy and minimum divergence optimization problems, in the cases where integer valued sufficient statistics exists, using tools from computational commutative algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. We give an implicit description of maximum entropy models by embedding them in algebraic varieties for which we give a Grobner basis method to compute it. In the cases of minimum KL-divergence models we show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner basis method to embed minimum KL-divergence models in algebraic varieties. (C) 2012 Elsevier Inc. All rights reserved.

Surrogate based design optimisation of composite aerofoil cross-section for helicopter vibration reduction

Design optimisation of a helicopter rotor blade is performed. The objective is to reduce helicopter vibration and constraints are put on frequencies and aeroelastic stability. The ply angles of the D-spar and skin of the composite rotor blade with NACA 0015 aerofoil section are considered as design variables. Polynomial response surfaces and space filling experimental designs are used to generate surrogate models of the objective function with respect to cross-section properties. The stacking sequence corresponding to the optimal cross-section is found using a real-coded genetic algorithm. Ply angle discretisation of 1 degrees, 15 degrees, 30 degrees and 45 degrees are used. The mean value of the objective function is used to find the optimal blade designs and the resulting designs are tested for variance. The optimal designs show a vibration reduction of 26% to 33% from the baseline design. A substantial reduction in vibration and an aeroelastically stable blade is obtained even after accounting for composite material uncertainty.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.

c-theorems in arbitrary dimensions

The dilaton action in 3 + 1 dimensions plays a crucial role in the proof of the a-theorem. This action arises using Wess-Zumino consistency conditions and crucially relies on the existence of the trace anomaly. Since there are no anomalies in odd dimensions, it is interesting to ask how such an action could arise otherwise. Motivated by this we use the AdS/CFT correspondence to examine both even and odd dimensional conformal field theories. We find that in even dimensions, by promoting the cutoff to a field, one can get an action for this field which coincides with the Wess-Zumino action in flat space. In three dimensions, we observe that by finding an exact Hamilton-Jacobi counterterm, one can find a non-polynomial action which is invariant under global Weyl rescalings. We comment on how this finding is tied up with the F-theorem conjectures.

Nonuniform random geometric graphs with location-dependent radii

We propose a distribution-free approach to the study of random geometric graphs. The distribution of vertices follows a Poisson point process with intensity function n f(center dot), where n is an element of N, and f is a probability density function on R-d. A vertex located at x connects via directed edges to other vertices that are within a cut-off distance r(n)(x). We prove strong law results for (i) the critical cut-off function so that almost surely, the graph does not contain any node with out-degree zero for sufficiently large n and (ii) the maximum and minimum vertex degrees. We also provide a characterization of the cut-off function for which the number of nodes with out-degree zero converges in distribution to a Poisson random variable. We illustrate this result for a class of densities with compact support that have at most polynomial rates of decay to zero. Finally, we state a sufficient condition for an enhanced version of the above graph to be almost surely connected eventually.

Supersymmetric Chern-Simons theories with vector matter

In this paper we discuss SU(N) Chern-Simons theories at level k with both fermionic and bosonic vector matter. In particular we present an exact calculation of the free energy of the N = 2 supersymmetric model (with one chiral field) for all values of the `t Hooft coupling in the large N limit. This is done by using a generalization of the standard Hubbard-Stratanovich method because the SUSY model contains higher order polynomial interactions.

Cubicity and Bandwidth

A unit cube in (or a k-cube in short) is defined as the Cartesian product R (1) x R (2) x ... x R (k) where R (i) (for 1 a parts per thousand currency sign i a parts per thousand currency sign k) is a closed interval of the form a (i) , a (i) + 1] on the real line. A k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that two vertices in G are adjacent if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G is the minimum k such that G has a k-cube representation. From a geometric embedding point of view, a k-cube representation of G = (V, E) yields an embedding such that for any two vertices u and v, ||f(u) - f(v)||(a) a parts per thousand currency sign 1 if and only if . We first present a randomized algorithm that constructs the cube representation of any graph on n vertices with maximum degree Delta in O(Delta ln n) dimensions. This algorithm is then derandomized to obtain a polynomial time deterministic algorithm that also produces the cube representation of the input graph in the same number of dimensions. The bandwidth ordering of the graph is studied next and it is shown that our algorithm can be improved to produce a cube representation of the input graph G in O(Delta ln b) dimensions, where b is the bandwidth of G, given a bandwidth ordering of G. Note that b a parts per thousand currency sign n and b is much smaller than n for many well-known graph classes. Another upper bound of b + 1 on the cubicity of any graph with bandwidth b is also shown. Together, these results imply that for any graph G with maximum degree Delta and bandwidth b, the cubicity is O(min{b, Delta ln b}). The upper bound of b + 1 is used to derive upper bounds for the cubicity of circular-arc graphs, cocomparability graphs and AT-free graphs in terms of the maximum degree Delta.

Efficient Methods for Robust Classification Under Uncertainty in Kernel Matrices

In this paper we study the problem of designing SVM classifiers when the kernel matrix, K, is affected by uncertainty. Specifically K is modeled as a positive affine combination of given positive semi definite kernels, with the coefficients ranging in a norm-bounded uncertainty set. We treat the problem using the Robust Optimization methodology. This reduces the uncertain SVM problem into a deterministic conic quadratic problem which can be solved in principle by a polynomial time Interior Point (IP) algorithm. However, for large-scale classification problems, IP methods become intractable and one has to resort to first-order gradient type methods. The strategy we use here is to reformulate the robust counterpart of the uncertain SVM problem as a saddle point problem and employ a special gradient scheme which works directly on the convex-concave saddle function. The algorithm is a simplified version of a general scheme due to Juditski and Nemirovski (2011). It achieves an O(1/T-2) reduction of the initial error after T iterations. A comprehensive empirical study on both synthetic data and real-world protein structure data sets show that the proposed formulations achieve the desired robustness, and the saddle point based algorithm outperforms the IP method significantly.

Diversity-Rate Trade-off for Fading Channels with Power Control

We consider a complex, additive, white Gaussian noise channel with flat fading. We study its diversity order vs transmission rate for some known power allocation schemes. The capacity region is divided into three regions. For one power allocation scheme, the diversity order is exponential throughout the capacity region. For selective channel inversion (SCI) scheme, the diversity order is exponential in low and high rate region but polynomial in mid rate region. For fast fading case we also provide a new upper bound on block error probability and a power allocation scheme that minimizes it. The diversity order behaviour of this scheme is same as for SCI but provides lower BER than the other policies.

On the Selection of Optimum Savitzky-Golay Filters

Savitzky-Golay (S-G) filters are finite impulse response lowpass filters obtained while smoothing data using a local least-squares (LS) polynomial approximation. Savitzky and Golay proved in their hallmark paper that local LS fitting of polynomials and their evaluation at the mid-point of the approximation interval is equivalent to filtering with a fixed impulse response. The problem that we address here is, ``how to choose a pointwise minimum mean squared error (MMSE) S-G filter length or order for smoothing, while preserving the temporal structure of a time-varying signal.'' We solve the bias-variance tradeoff involved in the MMSE optimization using Stein's unbiased risk estimator (SURE). We observe that the 3-dB cutoff frequency of the SURE-optimal S-G filter is higher where the signal varies fast locally, and vice versa, essentially enabling us to suitably trade off the bias and variance, thereby resulting in near-MMSE performance. At low signal-to-noise ratios (SNRs), it is seen that the adaptive filter length algorithm performance improves by incorporating a regularization term in the SURE objective function. We consider the algorithm performance on real-world electrocardiogram (ECG) signals. The results exhibit considerable SNR improvement. Noise performance analysis shows that the proposed algorithms are comparable, and in some cases, better than some standard denoising techniques available in the literature.