Solving MIN ONES 2-SAT as fast as VERTEX COVER

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

The Lovasz θ function, SVMs and finding large dense subgraphs

The Lovasz θ function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms. Computing θ involves solving a SDP and is extremely expensive even for moderately sized graphs. In this paper we establish that the Lovasz θ function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM−θ graphs, on which the Lovasz θ function can be approximated well by a one-class SVM. This leads to a novel use of SVM techniques to solve algorithmic problems in large graphs e.g. identifying a planted clique of size Θ(n√) in a random graph G(n,12). A classic approach for this problem involves computing the θ function, however it is not scalable due to SDP computation. We show that the random graph with a planted clique is an example of SVM−θ graph, and as a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the state-of-the-art. Further, we introduce the notion of a ''common orthogonal labeling'' which extends the notion of a ''orthogonal labelling of a single graph (used in defining the θ function) to multiple graphs. The problem of finding the optimal common orthogonal labelling is cast as a Multiple Kernel Learning problem and is used to identify a large common dense region in multiple graphs. The proposed algorithm achieves an order of magnitude scalability compared to the state of the art.

CUDA-for-clusters: a system for efficient execution of CUDA kernels on multi-core clusters

Rapid advancements in multi-core processor architectures coupled with low-cost, low-latency, high-bandwidth interconnects have made clusters of multi-core machines a common computing resource. Unfortunately, writing good parallel programs that efficiently utilize all the resources in such a cluster is still a major challenge. Various programming languages have been proposed as a solution to this problem, but are yet to be adopted widely to run performance-critical code mainly due to the relatively immature software framework and the effort involved in re-writing existing code in the new language. In this paper, we motivate and describe our initial study in exploring CUDA as a programming language for a cluster of multi-cores. We develop CUDA-For-Clusters (CFC), a framework that transparently orchestrates execution of CUDA kernels on a cluster of multi-core machines. The well-structured nature of a CUDA kernel, the growing popularity, support and stability of the CUDA software stack collectively make CUDA a good candidate to be considered as a programming language for a cluster. CFC uses a mixture of source-to-source compiler transformations, a work distribution runtime and a light-weight software distributed shared memory to manage parallel executions. Initial results on running several standard CUDA benchmark programs achieve impressive speedups of up to 7.5X on a cluster with 8 nodes, thereby opening up an interesting direction of research for further investigation.

BILATERAL EDGE DETECTORS

We propose to employ bilateral filters to solve the problem of edge detection. The proposed methodology presents an efficient and noise robust method for detecting edges. Classical bilateral filters smooth images without distorting edges. In this paper, we modify the bilateral filter to perform edge detection, which is the opposite of bilateral smoothing. The Gaussian domain kernel of the bilateral filter is replaced with an edge detection mask, and Gaussian range kernel is replaced with an inverted Gaussian kernel. The modified range kernel serves to emphasize dissimilar regions. The resulting approach effectively adapts the detection mask according as the pixel intensity differences. The results of the proposed algorithm are compared with those of standard edge detection masks. Comparisons of the bilateral edge detector with Canny edge detection algorithm, both after non-maximal suppression, are also provided. The results of our technique are observed to be better and noise-robust than those offered by methods employing masks alone, and are also comparable to the results from Canny edge detector, outperforming it in certain cases.

Lovasz theta function, SVMs and Finding Dense Subgraphs

In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.

UNIQUENESS OF SOLUTIONS TO SCHRODINGER EQUATIONS ON H-TYPE GROUPS

This paper deals with the Schrodinger equation i partial derivative(s)u(z, t; s) - Lu(z, t; s) = 0; where L is the sub-Laplacian on the Heisenberg group. Assume that the initial data f satisfies vertical bar f(z, t)vertical bar less than or similar to q(alpha)(z, t), where q(s) is the heat kernel associated to L. If in addition vertical bar u(z, t; s(0))vertical bar less than or similar to q(beta)(z, t), for some s(0) is an element of R \textbackslash {0}, then we prove that u(z, t; s) = 0 for all s is an element of R whenever alpha beta < s(0)(2). This result holds true in the more general context of H-type groups. We also prove an analogous result for the Grushin operator on Rn+1.

Smoothed Functional Algorithms for Stochastic Optimization Using q-Gaussian Distributions

Smoothed functional (SF) schemes for gradient estimation are known to be efficient in stochastic optimization algorithms, especially when the objective is to improve the performance of a stochastic system However, the performance of these methods depends on several parameters, such as the choice of a suitable smoothing kernel. Different kernels have been studied in the literature, which include Gaussian, Cauchy, and uniform distributions, among others. This article studies a new class of kernels based on the q-Gaussian distribution, which has gained popularity in statistical physics over the last decade. Though the importance of this family of distributions is attributed to its ability to generalize the Gaussian distribution, we observe that this class encompasses almost all existing smoothing kernels. This motivates us to study SF schemes for gradient estimation using the q-Gaussian distribution. Using the derived gradient estimates, we propose two-timescale algorithms for optimization of a stochastic objective function in a constrained setting with a projected gradient search approach. We prove the convergence of our algorithms to the set of stationary points of an associated ODE. We also demonstrate their performance numerically through simulations on a queuing model.

An improved free surface modeling for incompressible SPH

In Incompressible Smooth Particle Hydrodynamics (ISPH), a pressure Poisson equation (PPE) is solved to obtain a divergence free velocity field. When free surfaces are simulated using this method a Dirichlet boundary condition for pressure at the free surface has to be applied. In existing ISPH methods this is achieved by identifying free surface particles using heuristically chosen threshold of a parameter such as kernel sum, density or divergence of the position, and explicitly setting their pressure values. This often leads to clumping of particles near the free surface and spraying off of surface particles during splashes. Moreover, surface pressure gradients in flows where surface tension is important are not captured well using this approach. We propose a more accurate semi-analytical approach to impose Dirichlet boundary conditions on the free surface. We show the efficacy of the proposed algorithm by using test cases of elongation of a droplet and dam break. We perform two dimensional simulations of water entry and validate the proposed algorithm with experimental results. Further, a three dimensional simulation of droplet splash is shown to compare well with the Volume-of-Fluid simulations. (C) 2014 Elsevier Ltd. All rights reserved.

UNO Gets Easier for a Single Player

This work is a follow up to 2, FUN 2010], which initiated a detailed analysis of the popular game of UNO (R). We consider the solitaire version of the game, which was shown to be NP-complete. In 2], the authors also demonstrate a (O)(n)(c(2)) algorithm, where c is the number of colors across all the cards, which implies, in particular that the problem is polynomial time when the number of colors is a constant. In this work, we propose a kernelization algorithm, a consequence of which is that the problem is fixed-parameter tractable when the number of colors is treated as a parameter. This removes the exponential dependence on c and answers the question stated in 2] in the affirmative. We also introduce a natural and possibly more challenging version of UNO that we call ``All Or None UNO''. For this variant, we prove that even the single-player version is NP-complete, and we show a single-exponential FPT algorithm, along with a cubic kernel.

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

Logarithmic corrections to extremal black hole entropy in N=2, 4 and 8 supergravity

We compute the logarithmic correction to black hole entropy about exponentially suppressed saddle points of the Quantum Entropy Function corresponding to Z(N) orbifolds of the near horizon geometry of the extremal black hole under study. By carefully accounting for zero mode contributions we show that the logarithmic contributions for quarter-BPS black holes in N = 4 supergravity and one-eighth BPS black holes in N = 8 supergravity perfectly match with the prediction from the microstate counting. We also find that the logarithmic contribution for half-BPS black holes in N = 2 supergravity depends non-trivially on the Z(N) orbifold. Our analysis draws heavily on the results we had previously obtained for heat kernel coefficients on Z(N) orbifolds of spheres and hyperboloids in arXiv:1311.6286 and we also propose a generalization of the Plancherel formula to Z(N) orbifolds of hyperboloids to an expression involving the Harish-Chandra character of sl (2, R), a result which is of possible mathematical interest.

A meshless adaptive multiscale method for fracture

The paper presents a multiscale method for crack propagation. The coarse region is modelled by the differential reproducing kernel particle method. Fracture in the coarse scale region is modelled with the Phantom node method. A molecular statics approach is employed in the fine scale where crack propagation is modelled naturally by breaking of bonds. The triangular lattice corresponds to the lattice structure of the (111) plane of an FCC crystal in the fine scale region. The Lennard-Jones potential is used to model the atom-atom interactions. The coupling between the coarse scale and fine scale is realized through ghost atoms. The ghost atom positions are interpolated from the coarse scale solution and enforced as boundary conditions on the fine scale. The fine scale region is adaptively refined and coarsened as the crack propagates. The centro symmetry parameter is used to detect the crack tip location. The method is implemented in two dimensions. The results are compared to pure atomistic simulations and show excellent agreement. (C) 2014 Elsevier B. V. All rights reserved.

On Hermite pseudo-multipliers

In this article we deal with a variation of a theorem of Mauceri concerning the L-P boundedness of operators M which are known to be bounded on L-2. We obtain sufficient conditions on the kernel of the operator M so that it satisfies weighted L-P estimates. As an application we prove L-P boundedness of Hermite pseudo-multipliers. (C) 2014 Elsevier Inc. All rights reserved.

Transverse single spin asymmetry in e plus p up arrow -> e plus J/psi plus X and Q(2) evolution of Sivers function-II

We present estimates of single spin asymmetry in the electroproduction of J/psi taking into account the transverse momentum-dependent (TMD) evolution of the gluon Sivers function. We estimate single spin asymmetry for JLab, HERMES, COMPASS and eRHIC energies using the color evaporation model of J/psi. We have calculated the asymmetry using recent parameters extracted by Echevarria et al. using the Collins-Soper-Sterman approach to TMD evolution. These recent TMD evolution fits are based on the evolution kernel in which the perturbative part is resummed up to next-to-leading logarithmic accuracy. We have also estimated the asymmetry by using parameters which had been obtained by a fit by Anselmino et al., using both an exact numerical and an approximate analytical solution of the TMD evolution equations. We find that the variation among the different estimates obtained using TMD evolution is much smaller than between these on one hand and the estimates obtained using DGLAP evolution on the other. Even though the use of TMD evolution causes an overall reduction in asymmetries compared to the ones obtained without it, they remain sizable. Overall, upon use of TMD evolution, predictions for asymmetries stabilize.