OpenRaiser/Intern-Atlas huggingface dataset:
Diameter Constrained Reliability: Computational Complexity in terms of the diameter and number of terminals
Venue: arXiv cs.CC 2014
Year: 2014

Let $G=(V,E)$ be a simple graph with $|V|=n$ nodes and $|E|=m$ links, a subset $K \subseteq V$ of \emph{terminals}, a vector $p=(p_1,\ldots,p_m) \in [0,1]^m$ and a positive integer $d$, called \emph{diameter}. We assume nodes are perfect but links fail stochastically and independently, with probabilities $q_i=1-p_i$. The \emph{diameter-constrained reliability} (DCR for short), is the probability that the terminals of the resulting subgraph remain connected by paths composed by $d$ links, or less. This number is denoted by $R_{K,G}^{d}(p)$. The general DCR computation is inside the class of $\mathcal{N}\mathcal{P}$-Hard problems, since is subsumes the complexity that a random graph is connected. In this paper, the computational complexity of DCR-subproblems is discussed in terms of the number of terminal nodes $k=|K|$ and diameter $d$. Either when $d=1$ or when $d=2$ and $k$ is fixed, the DCR is inside the class $\mathcal{P}$ of polynomial-time problems. The DCR turns $\mathcal{N}\mathcal{P}$-Hard when $k \geq 2$ is a fixed input parameter and $d\geq 3$. The case where $k=n$ and $d \geq 2$ is fixed are not studied in prior literature. Here, the $\mathcal{N}\mathcal{P}$-Hardness of this case is established.
Using industrial robot to manipulate the measured object in CMM
Venue: arXiv cs.RO 2014
Year: 2014

Coordinate measuring machines (CMMs) are widely used to check dimensions of manufactured parts, especially in automotive industry. The major obstacles in automation of these measurements are fixturing and clamping assemblies, which are required in order to position the measured object within the CMM. This paper describes how an industrial robot can be used to manipulate the measured object within the CMM work space, in order to enable automation of complex geometry measurement.
Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation
Venue: arXiv cs.CG 2014
Year: 2014

We revisit two NP-hard geometric partitioning problems - convex decomposition and surface approximation. Building on recent developments in geometric separators, we present quasi-polynomial time algorithms for these problems with improved approximation guarantees.
A strong restricted isometry property, with an application to phaseless compressed sensing
Venue: arXiv cs.IT 2014
Year: 2014

The many variants of the restricted isometry property (RIP) have proven to be crucial theoretical tools in the fields of compressed sensing and matrix completion. The study of extending compressed sensing to accommodate phaseless measurements naturally motivates a strong notion of restricted isometry property (SRIP), which we develop in this paper. We show that if $A \in \mathbb{R}^{m\times n}$ satisfies SRIP and phaseless measurements $|Ax_0| = b$ are observed about a $k$-sparse signal $x_0 \in \mathbb{R}^n$, then minimizing the $\ell_1$ norm subject to $ |Ax| = b $ recovers $x_0$ up to multiplication by a global sign. Moreover, we establish that the SRIP holds for the random Gaussian matrices typically used for standard compressed sensing, implying that phaseless compressed sensing is possible from $O(k \log (n/k))$ measurements with these matrices via $\ell_1$ minimization over $|Ax| = b$. Our analysis also yields an erasure robust version of the Johnson-Lindenstrauss Lemma.
Generalized Second Price Auction with Probabilistic Broad Match
Venue: arXiv cs.GT 2014
Year: 2014

Generalized Second Price (GSP) auctions are widely used by search engines today to sell their ad slots. Most search engines have supported broad match between queries and bid keywords when executing GSP auctions, however, it has been revealed that GSP auction with the standard broad-match mechanism they are currently using (denoted as SBM-GSP) has several theoretical drawbacks (e.g., its theoretical properties are known only for the single-slot case and full-information setting, and even in this simple setting, the corresponding worst-case social welfare can be rather bad). To address this issue, we propose a novel broad-match mechanism, which we call the Probabilistic Broad-Match (PBM) mechanism. Different from SBM that puts together the ads bidding on all the keywords matched to a given query for the GSP auction, the GSP with PBM (denoted as PBM-GSP) randomly samples a keyword according to a predefined probability distribution and only runs the GSP auction for the ads bidding on this sampled keyword. We perform a comprehensive study on the theoretical properties of the PBM-GSP. Specifically, we study its social welfare in the worst equilibrium, in both full-information and Bayesian settings. The results show that PBM-GSP can generate larger welfare than SBM-GSP under mild conditions. Furthermore, we also study the revenue guarantee for PBM-GSP in Bayesian setting. To the best of our knowledge, this is the first work on broad-match mechanisms for GSP that goes beyond the single-slot case and the full-information setting.
A Hybrid Analysis for Security Protocols with State
Venue: arXiv cs.CR 2014
Year: 2014

Cryptographic protocols rely on message-passing to coordinate activity among principals. Each principal maintains local state in individual local sessions only as needed to complete that session. However, in some protocols a principal also uses state to coordinate its different local sessions. Sometimes the non-local, mutable state is used as a means, for example with smart cards or Trusted Platform Modules. Sometimes it is the purpose of running the protocol, for example in commercial transactions. Many richly developed tools and techniques, based on well-understood foundations, are available for design and analysis of pure message-passing protocols. But the presence of cross-session state poses difficulties for these techniques. In this paper we provide a framework for modeling stateful protocols. We define a hybrid analysis method. It leverages theorem-proving---in this instance, the PVS prover---for reasoning about computations over state. It combines that with an "enrich-by-need" approach---embodied by CPSA---that focuses on the message-passing part. As a case study we give a full analysis of the Envelope Protocol, due to Mark Ryan.
Analysis of Dynamic Scheduling Strategies for Matrix Multiplication on Heterogeneous Platforms
Venue: arXiv cs.DC 2014
Year: 2014

The tremendous increase in the size and heterogeneity of supercomputers makes it very difficult to predict the performance of a scheduling algorithm. Therefore, dynamic solutions, where scheduling decisions are made at runtime have overpassed static allocation strategies. The simplicity and efficiency of dynamic schedulers such as Hadoop are a key of the success of the MapReduce framework. Dynamic schedulers such as StarPU, PaRSEC or StarSs are also developed for more constrained computations, e.g. task graphs coming from linear algebra. To make their decisions, these runtime systems make use of some static information, such as the distance of tasks to the critical path or the affinity between tasks and computing resources (CPU, GPU,...) and of dynamic information, such as where input data are actually located. In this paper, we concentrate on two elementary linear algebra kernels, namely the outer product and the matrix multiplication. For each problem, we propose several dynamic strategies that can be used at runtime and we provide an analytic study of their theoretical performance. We prove that the theoretical analysis provides very good estimate of the amount of communications induced by a dynamic strategy and can be used in order to efficiently determine thresholds used in dynamic scheduler, thus enabling to choose among them for a given problem and architecture.
Spiralet Sparse Representation
Venue: arXiv cs.CV 2014
Year: 2014

This is the first report on Working Paper WP-RFM-14-01. The potential and capability of sparse representations is well-known. However, their (multivariate variable) vectorial form, which is completely fine in many fields and disciplines, results in removal and filtering of important "spatial" relations that are implicitly carried by two-dimensional [or multi-dimensional] objects, such as images. In this paper, a new approach, called spiralet sparse representation, is proposed in order to develop an augmented representation and therefore a modified sparse representation and theory, which is capable to preserve the data associated to the spatial relations.
On the Role of Canonicity in Bottom-up Knowledge Compilation
Venue: arXiv cs.AI 2014
Year: 2014

We consider the problem of bottom-up compilation of knowledge bases, which is usually predicated on the existence of a polytime function for combining compilations using Boolean operators (usually called an Apply function). While such a polytime Apply function is known to exist for certain languages (e.g., OBDDs) and not exist for others (e.g., DNNF), its existence for certain languages remains unknown. Among the latter is the recently introduced language of Sentential Decision Diagrams (SDDs), for which a polytime Apply function exists for unreduced SDDs, but remains unknown for reduced ones (i.e. canonical SDDs). We resolve this open question in this paper and consider some of its theoretical and practical implications. Some of the findings we report question the common wisdom on the relationship between bottom-up compilation, language canonicity and the complexity of the Apply function.
Web Mining using Artificial Ant Colonies: A Survey
Venue: arXiv cs.OH 2014
Year: 2014

Web mining has been very crucial to any organization as it provides useful insights to business patterns. It helps the company to understand its customers better. As the web is growing in pace, so is its importance and hence it becomes all the more necessary to find useful patterns. Here in this paper, web mining using ant colony optimization has been reviewed with some of its experimental results.
SWAPHI: Smith-Waterman Protein Database Search on Xeon Phi Coprocessors
Venue: arXiv cs.DC 2014
Year: 2014

The maximal sensitivity of the Smith-Waterman (SW) algorithm has enabled its wide use in biological sequence database search. Unfortunately, the high sensitivity comes at the expense of quadratic time complexity, which makes the algorithm computationally demanding for big databases. In this paper, we present SWAPHI, the first parallelized algorithm employing Xeon Phi coprocessors to accelerate SW protein database search. SWAPHI is designed based on the scale-and-vectorize approach, i.e. it boosts alignment speed by effectively utilizing both the coarse-grained parallelism from the many co-processing cores (scale) and the fine-grained parallelism from the 512-bit wide single instruction, multiple data (SIMD) vectors within each core (vectorize). By searching against the large UniProtKB/TrEMBL protein database, SWAPHI achieves a performance of up to 58.8 billion cell updates per second (GCUPS) on one coprocessor and up to 228.4 GCUPS on four coprocessors. Furthermore, it demonstrates good parallel scalability on varying number of coprocessors, and is also superior to both SWIPE on 16 high-end CPU cores and BLAST+ on 8 cores when using four coprocessors, with the maximum speedup of 1.52 and 1.86, respectively. SWAPHI is written in C++ language (with a set of SIMD intrinsics), and is freely available at http://swaphi.sourceforge.net.
Time-Frequency Packing for High Capacity Coherent Optical Links
Venue: arXiv cs.IT 2014
Year: 2014

We consider realistic long-haul optical links, with linear and nonlinear impairments, and investigate the application of time-frequency packing with low-order constellations as a possible solution to increase the spectral efficiency. A detailed comparison with available techniques from the literature will be also performed. We will see that this technique represents a feasible solution to overcome the relevant theoretical and technological issues related to this spectral efficiency increase and could be more effective than the simple adoption of high-order modulation formats.
Managing Change in Graph-structured Data Using Description Logics (long version with appendix)
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we consider the setting of graph-structured data that evolves as a result of operations carried out by users or applications. We study different reasoning problems, which range from ensuring the satisfaction of a given set of integrity constraints after a given sequence of updates, to deciding the (non-)existence of a sequence of actions that would take the data to an (un)desirable state, starting either from a specific data instance or from an incomplete description of it. We consider an action language in which actions are finite sequences of conditional insertions and deletions of nodes and labels, and use Description Logics for describing integrity constraints and (partial) states of the data. We then formalize the above data management problems as a static verification problem and several planning problems. We provide algorithms and tight complexity bounds for the formalized problems, both for an expressive DL and for a variant of DL-Lite.
Case study: Data Mining of Associate Degree Accepted Candidates by Modular Method
Venue: arXiv cs.DB 2014
Year: 2014

Since about 10 years ago, University of Applied Science and Technology (UAST) in Iran has admitted students in discontinuous associate degree by modular method, so that almost 100,000 students are accepted every year. Although the first aim of holding such courses was to improve scientific and skill level of employees, over time a considerable group of unemployed people have been interested to participate in these courses. According to this fact, in this paper, we mine and analyze a sample data of accepted candidates in modular 2008 and 2009 courses by using unsupervised and supervised learning paradigms. In the first step, by using unsupervised paradigm, we grouped (clustered) set of modular accepted candidates based on their student status and labeled data sets by three classes so that each class somehow shows educational and student status of modular accepted candidates. In the second step, by using supervised and unsupervised algorithms, we generated predicting models in 2008 data sets. Then, by making a comparison between performances of generated models, we selected predicting model of association rules through which some rules were extracted. Finally, this model is executed for Test set which includes accepted candidates of next course then by evaluation of results, the percentage of correctness and confidentiality of obtained results can be viewed.
Enhanced List-Based Group-Wise Overloaded Receiver with Application to Satellite Reception
Venue: arXiv cs.IT 2014
Year: 2014

The market trends towards the use of smaller dish antennas for TV satellite receivers, as well as the growing density of broadcasting satellites in orbit require the application of robust adjacent satellite interference (ASI) cancellation algorithms at the receivers. The wider beamwidth of a small size dish and the growing number of satellites in orbit impose an overloaded scenario, i.e., a scenario where the number of transmitting satellites exceeds the number of receiving antennas. For such a scenario, we present a two stage receiver to enhance signal detection from the satellite of interest, i.e., the satellite that the dish is pointing to, while reducing interference from neighboring satellites. Towards this objective, we propose an enhanced List-based Group-wise Search Detection (LGSD) receiver architecture that takes into account the spatially correlated additive noise and uses the signal-to-interference-plus noise ratio (SINR) maximization criterion to improve detection performance. Simulations show that the proposed receiver structure enhances the performance of satellite systems in the presence of ASI when compared to existing methods.
Rainbow Colouring of Split Graphs
Venue: arXiv cs.DM 2014
Year: 2014

A rainbow path in an edge coloured graph is a path in which no two edges are coloured the same. A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one rainbow path. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Between them, Chakraborty et al. [J. Comb. Optim., 2011] and Ananth et al. [FSTTCS, 2012] have shown that for every integer k, k \geq 2, it is NP-complete to decide whether a given graph can be rainbow coloured using k colours. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Chandran and Rajendraprasad have shown that the problem of deciding whether a given split graph G can be rainbow coloured using 3 colours is NP-complete and further have described a linear time algorithm to rainbow colour any split graph using at most one colour more than the optimum [COCOON, 2012]. In this article, we settle the computational complexity of the problem on split graphs and thereby discover an interesting dichotomy. Specifically, we show that the problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k \in {2,3}, but can be solved in polynomial time for all other values of k.
On Upper and Lower Bounds on the Length of Alternating Towers
Venue: arXiv cs.FL 2014
Year: 2014

A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the other language, and each string can be embedded into the next string in the sequence. It is known that if there are towers of any length, then there also exists an infinite tower. We investigate upper and lower bounds on the length of finite towers between two regular languages with respect to the size of the automata representing the languages in the case there is no infinite tower. This problem is relevant to the separation problem of regular languages by piecewise testable languages.
Deterministic Truncation of Linear Matroids
Venue: arXiv cs.DS 2014
Year: 2014

Let $M=(E,{\cal I})$ be a matroid. A {\em $k$-truncation} of $M$ is a matroid {$M'=(E,{\cal I}')$} such that for any $A\subseteq E$, $A\in {\cal I}'$ if and only if $|A|\leq k$ and $A\in {\cal I}$. Given a linear representation of $M$ we consider the problem of finding a linear representation of the $k$-truncation of this matroid. This problem can be abstracted out to the following problem on matrices. Let $M$ be a $n\times m$ matrix over a field $\mathbb{F}$. A {\em rank $k$-truncation} of the matrix $M$ is a $k\times m$ matrix $M_k$ (over $\mathbb{F}$ or a related field) such that for every subset $I\subseteq \{1,\ldots,m\}$ of size at most $k$, the set of columns corresponding to $I$ in $M$ has rank $|I|$ if and only of the corresponding set of columns in $M_k$ has rank $|I|$. Finding rank $k$-truncation of matrices is a common way to obtain a linear representation of $k$-truncation of linear matroids, which has many algorithmic applications. A common way to compute a rank $k$-truncation of a $n \times m$ matrix is to multiply the matrix with a random $k\times n$ matrix (with the entries from a field of an appropriate size), yielding a simple randomized algorithm. So a natural question is whether it possible to obtain a rank $k$-truncations of a matrix, {\em deterministically}. In this paper we settle this question for matrices over any finite field or the field of rationals ($\mathbb Q$). We show that given a matrix $M$ over a field $\mathbb{F}$ we can compute a $k$-truncation $M_k$ over the ring $\mathbb{F}[X]$ in deterministic polynomial time.
Retargeting Without Tracking
Venue: arXiv cs.CR 2014
Year: 2014

Retargeting ads are increasingly prevalent on the Internet as their effectiveness has been shown to outperform conventional targeted ads. Retargeting ads are not only based on users' interests, but also on their intents, i.e. commercial products users have shown interest in. Existing retargeting systems heavily rely on tracking, as retargeting companies need to know not only the websites a user has visited but also the exact products on these sites. They are therefore very intrusive, and privacy threatening. Furthermore, these schemes are still sub-optimal since tracking is partial, and they often deliver ads that are obsolete (because, for example, the targeted user has already bought the advertised product). This paper presents the first privacy-preserving retargeting ads system. In the proposed scheme, the retargeting algorithm is distributed between the user and the advertiser such that no systematic tracking is necessary, more control and transparency is provided to users, but still a lot of targeting flexibility is provided to advertisers. We show that our scheme, that relies on homomorphic encryption, can be efficiently implemented and trivially solves many problems of existing schemes, such as frequency capping and ads freshness.
Set Families with Low Pairwise Intersection
Venue: arXiv cs.CC 2014
Year: 2014

A $\left(n,\ell,γ\right)$-sharing set family of size $m$ is a family of sets $S_1,\ldots,S_m\subseteq [n]$ s.t. each set has size $\ell$ and each pair of sets shares at most $γ$ elements. We let $m\left(n,\ell,γ\right)$ denote the maximum size of any such set family and we consider the following question: How large can $m\left(n,\ell,γ\right)$ be? $\left(n,\ell,γ\right)$-sharing set families have a rich set of applications including the construction of pseudorandom number generators and usable and secure password management schemes. We analyze the explicit construction of Blocki et al using recent bounds on the value of the $t$'th Ramanujan prime. We show that this explicit construction produces a $\left(4\ell^2\ln 4\ell,\ell,γ\right)$-sharing set family of size $\left(2 \ell \ln 2\ell\right)^{γ+1}$ for any $\ell\geq γ$. We also show that the construction of Blocki et al can be used to obtain a weak $\left(n,\ell,γ\right)$-sharing set family of size $m$ for any $m >0$. These results are competitive with the inexplicit construction of Raz et al for weak $\left(n,\ell,γ\right)$-sharing families. We show that our explicit construction of weak $\left(n,\ell,γ\right)$-sharing set families can be used to obtain a parallelizable pseudorandom number generator with a low memory footprint by using the pseudorandom number generator of Nisan and Wigderson. We also prove that $m\left(n,n/c_1,c_2n\right)$ must be a constant whenever $c_2 \leq \frac{2}{c_1^3+c_1^2}$. We show that this bound is nearly tight as $m\left(n,n/c_1,c_2n\right)$ grows exponentially fast whenever $c_2 > c_1^{-2}$.
A Survey of Methods For Analyzing and Improving GPU Energy Efficiency
Venue: arXiv cs.AR 2014
Year: 2014

Recent years have witnessed a phenomenal growth in the computational capabilities and applications of GPUs. However, this trend has also led to dramatic increase in their power consumption. This paper surveys research works on analyzing and improving energy efficiency of GPUs. It also provides a classification of these techniques on the basis of their main research idea. Further, it attempts to synthesize research works which compare energy efficiency of GPUs with other computing systems, e.g. FPGAs and CPUs. The aim of this survey is to provide researchers with knowledge of state-of-the-art in GPU power management and motivate them to architect highly energy-efficient GPUs of tomorrow.