OpenRaiser/Intern-Atlas huggingface dataset:
Search Me If You Can: Privacy-preserving Location Query Service
Venue: arXiv cs.CR 2013
Year: 2013

Location-Based Service (LBS) becomes increasingly popular with the dramatic growth of smartphones and social network services (SNS), and its context-rich functionalities attract considerable users. Many LBS providers use users' location information to offer them convenience and useful functions. However, the LBS could greatly breach personal privacy because location itself contains much information. Hence, preserving location privacy while achieving utility from it is still an challenging question now. This paper tackles this non-trivial challenge by designing a suite of novel fine-grained Privacy-preserving Location Query Protocol (PLQP). Our protocol allows different levels of location query on encrypted location information for different users, and it is efficient enough to be applied in mobile platforms.
Non-cooperative games with preplay negotiations
Venue: arXiv cs.GT 2013
Year: 2013

We consider an extension of strategic normal form games with a phase of negotiations before the actual play of the game, where players can make binding offers for transfer of utilities to other players after the play of the game, in order to provide additional incentives for each other to play designated strategies. Such offers are conditional on the recipients playing the specified strategies and they effect transformations of the payoff matrix of the game by accordingly transferring payoffs between players. We introduce and analyze solution concepts for 2-player normal form games with such preplay offers under various assumptions for the preplay negotiation phase and obtain results for existence of efficient negotiation strategies of the players. Then we extend the framework to coalitional preplay offers in N-player games, as well as to extensive form games with inter-play offers for side payments.
Structured Recursive Separator Decompositions for Planar Graphs in Linear Time
Venue: arXiv cs.DM 2013
Year: 2013

Given a planar graph G on n vertices and an integer parameter r<n, an r-division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces of G (also called holes), and such that, for each region, the total number of vertices on these faces is O(sqrt r). We provide a linear-time algorithm for computing r-divisions with few holes. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of G that includes r-divisions for essentially all values of r. In particular, given an exponentially increasing sequence r = (r_1,r_2,...), our algorithm can produce a recursive r-division with few holes in linear time. r-divisions with few holes have been used in efficient algorithms to compute shortest paths, minimum cuts, and maximum flows. Our linear-time algorithm improves upon the decomposition algorithm used in the state-of-the-art algorithm for minimum st-cut (Italiano, Nussbaum, Sankowski, and Wulff-Nilsen, STOC 2011), removing one of the bottlenecks in the overall running time of their algorithm (analogously for minimum cut in planar and bounded-genus graphs).
Sparsity Averaging for Compressive Imaging
Venue: arXiv cs.IT 2013
Year: 2013

We discuss a novel sparsity prior for compressive imaging in the context of the theory of compressed sensing with coherent redundant dictionaries, based on the observation that natural images exhibit strong average sparsity over multiple coherent frames. We test our prior and the associated algorithm, based on an analysis reweighted $\ell_1$ formulation, through extensive numerical simulations on natural images for spread spectrum and random Gaussian acquisition schemes. Our results show that average sparsity outperforms state-of-the-art priors that promote sparsity in a single orthonormal basis or redundant frame, or that promote gradient sparsity. Code and test data are available at https://github.com/basp-group/sopt.
Local reconstructors and tolerant testers for connectivity and diameter
Venue: arXiv cs.DS 2013
Year: 2013

A local property reconstructor for a graph property is an algorithm which, given oracle access to the adjacency list of a graph that is "close" to having the property, provides oracle access to the adjacency matrix of a "correction" of the graph, i.e. a graph which has the property and is close to the given graph. For this model, we achieve local property reconstructors for the properties of connectivity and $k$-connectivity in undirected graphs, and the property of strong connectivity in directed graphs. Along the way, we present a method of transforming a local reconstructor (which acts as a "adjacency matrix oracle" for the corrected graph) into an "adjacency list oracle". This allows us to recursively use our local reconstructor for $(k-1)$-connectivity to obtain a local reconstructor for $k$-connectivity. We also extend this notion of local property reconstruction to parametrized graph properties (for instance, having diameter at most $D$ for some parameter $D$) and require that the corrected graph has the property with parameter close to the original. We obtain a local reconstructor for the low diameter property, where if the original graph is close to having diameter $D$, then the corrected graph has diameter roughly 2D. We also exploit a connection between local property reconstruction and property testing, observed by Brakerski, to obtain new tolerant property testers for all of the aforementioned properties. Except for the one for connectivity, these are the first tolerant property testers for these properties.
What Good Are Strong Specifications?
Venue: arXiv cs.SE 2013
Year: 2013

Experience with lightweight formal methods suggests that programmers are willing to write specification if it brings tangible benefits to their usual development activities. This paper considers stronger specifications and studies whether they can be deployed as an incremental practice that brings additional benefits without being unacceptably expensive. We introduce a methodology that extends Design by Contract to write strong specifications of functional properties in the form of preconditions, postconditions, and invariants. The methodology aims at being palatable to developers who are not fluent in formal techniques but are comfortable with writing simple specifications. We evaluate the cost and the benefits of using strong specifications by applying the methodology to testing data structure implementations written in Eiffel and C#. In our extensive experiments, testing against strong specifications detects twice as many bugs as standard contracts, with a reasonable overhead in terms of annotation burden and run-time performance while testing. In the wide spectrum of formal techniques for software quality, testing against strong specifications lies in a "sweet spot" with a favorable benefit to effort ratio.
A Unified Linear MSE Minimization MIMO Beamforming Design Based on Quadratic Matrix Programming
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate a unified linear transceiver design with mean-square-error (MSE) as the objective function for a wide range of wireless systems. The unified design is based on an elegant mathematical programming technology namely quadratic matrix programming (QMP). It is revealed that for different wireless systems such as multi-cell coordination systems, multi-user MIMO systems, MIMO cognitive radio systems, amplify-and-forward MIMO relaying systems, the MSE minimization beamforming design problems can always be solved by solving a number of QMP problems. A comprehensive framework on how to solve QMP problems is also given.
Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs
Venue: arXiv cs.DS 2013
Year: 2013

For a graph $G$, let $Z(G,λ)$ be the partition function of the monomer-dimer system defined by $\sum_k m_k(G)λ^k$, where $m_k(G)$ is the number of matchings of size $k$ in $G$. We consider graphs of bounded degree and develop a sublinear-time algorithm for estimating $\log Z(G,λ)$ at an arbitrary value $λ>0$ within additive error $εn$ with high probability. The query complexity of our algorithm does not depend on the size of $G$ and is polynomial in $1/ε$, and we also provide a lower bound quadratic in $1/ε$ for this problem. This is the first analysis of a sublinear-time approximation algorithm for a $# P$-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with $Z(G,λ)$. We show that our algorithm approximates the probability for a vertex to be covered by a matching, sampled according to this Gibbs distribution, in a near-optimal sublinear time. We extend our results to approximate the average size and the entropy of such a matching within an additive error with high probability, where again the query complexity is polynomial in $1/ε$ and the lower bound is quadratic in $1/ε$. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to other systems where the correlation decay is known to hold as for the independent set problem up to the critical activity.
Using Location-Based Social Networks to Validate Human Mobility and Relationships Models
Venue: arXiv cs.SI 2013
Year: 2013

We propose to use social networking data to validate mobility models for pervasive mobile ad-hoc networks (MANETs) and delay tolerant networks (DTNs). The Random Waypoint (RWP) and Erdos-Renyi (ER) models have been a popular choice among researchers for generating mobility traces of nodes and relationships between them. Not only RWP and ER are useful in evaluating networking protocols in a simulation environment, but they are also used for theoretical analysis of such dynamic networks. However, it has been observed that neither relationships among people nor their movements are random. Instead, human movements frequently contain repeated patterns and friendship is bounded by distance. We used social networking site Gowalla to collect, create and validate models of human mobility and relationships for analysis and evaluations of applications in opportunistic networks such as sensor networks and transportation models in civil engineering. In doing so, we hope to provide more human-like movements and social relationship models to researchers to study problems in complex and mobile networks.
Multiple graph regularized protein domain ranking
Venue: arXiv cs.LG 2013
Year: 2013

Background Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure of the protein domain database. Recently, graph regularized ranking that exploits the global structure of the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a difficult problem for most of the protein domain ranking methods. Results To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiG- Rank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization. Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an ob- jective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph regularized ranking methods and pairwise similarity based ranking methods. Conclusion The problem of graph model and parameter selection in graph regularized protein domain ranking can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new frontier in applying multiple graphs to solving protein domain ranking applications.
Robust Distributed Maximum Likelihood Estimation with Dependent Quantized Data
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider distributed maximum likelihood estimation (MLE) with dependent quantized data under the assumption that the structure of the joint probability density function (pdf) is known, but it contains unknown deterministic parameters. The parameters may include different vector parameters corresponding to marginal pdfs and parameters that describe dependence of observations across sensors. Since MLE with a single quantizer is sensitive to the choice of thresholds due to the uncertainty of pdf, we concentrate on MLE with multiple groups of quantizers (which can be determined by the use of prior information or some heuristic approaches) to fend off against the risk of a poor/outlier quantizer. The asymptotic efficiency of the MLE scheme with multiple quantizers is proved under some regularity conditions and the asymptotic variance is derived to be the inverse of a weighted linear combination of Fisher information matrices based on multiple different quantizers which can be used to show the robustness of our approach. As an illustrative example, we consider an estimation problem with a bivariate non-Gaussian pdf that has applications in distributed constant false alarm rate (CFAR) detection systems. Simulations show the robustness of the proposed MLE scheme especially when the number of quantized measurements is small.
Optimal Spectrum Access for Cognitive Radios
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate a time-slotted cognitive setting with buffered primary and secondary users. In order to alleviate the negative effects of misdetection and false alarm probabilities, a novel design of spectrum access mechanism is proposed. We propose two schemes. First, the SU senses primary channel to exploit the periods of silence, if the PU is declared to be idle, the SU randomly accesses the channel with some access probability $a_s$. Second, in addition to accessing the channel if the PU is idle, the SU possibly accesses the channel if it is declared to be busy with some access probability $b_s$. The access probabilities as function of the misdetection, false alarm and average primary arrival rate are obtained via solving an optimization problem designed to maximize the secondary service rate given a constraint on primary queue stability. In addition, we propose a variable sensing duration schemes where the SU optimizes over the optimal sensing time to achieve the maximum stable throughput of the network. The results reveal the performance gains of the proposed schemes over the conventional sensing scheme. We propose a method to estimate the mean arrival rate and the outage probability of the PU based on the primary feedback channel, i.e., acknowledgments (ACKs) and negative-acknowledgments (NACKs) messages.
Scientometrics
Venue: arXiv cs.DL 2013
Year: 2013

The paper provides an overview of the field of scientometrics, that is: the study of science, technology, and innovation from a quantitative perspective. We cover major historical milestones in the development of this specialism from the 1960s to today and discuss its relationship with the sociology of scientific knowledge, the library and information sciences, and science policy issues such as indicator development. The disciplinary organization of scientometrics is analyzed both conceptually and empirically, using a map of journals cited in the core journal of the field, entitled Scientometrics. A state-of-the-art review of five major research threads is provided: (1) the measurement of impact; (2) the delineation of reference sets; (3) theories of citation; (4) mapping science; and (5) the policy and management contexts of indicator developments.
SOA Framework for Integrated Business
Venue: arXiv cs.CY 2013
Year: 2013

In this paper SOA model for business is presented. This is a survey paper. As the new technology evolve the new businesses use SOA framework.
The Effect of Macrodiversity on the Performance of Maximal Ratio Combining in Flat Rayleigh Fading
Venue: arXiv cs.IT 2013
Year: 2013

The performance of maximal ratio combining (MRC) in Rayleigh channels with co-channel interference (CCI) is well-known for receive arrays which are co-located. Recent work in network MIMO, edge-excited cells and base station collaboration is increasing interest in macrodiversity systems. Hence, in this paper we consider the effect of macrodiversity on MRC performance in Rayleigh fading channels with CCI. We consider the uncoded symbol error rate (SER) as our performance measure of interest and investigate how different macrodiversity power profiles affect SER performance. This is the first analytical work in this area. We derive approximate and exact symbol error rate results for M-QAM/BPSK modulations and use the analysis to provide a simple power metric. Numerical results, verified by simulations, are used in conjunction with the analysis to gain insight into the effects of the link powers on performance.
New Constructions of Zero-Correlation Zone Sequences
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose three classes of systematic approaches for constructing zero correlation zone (ZCZ) sequence families. In most cases, these approaches are capable of generating sequence families that achieve the upper bounds on the family size ($K$) and the ZCZ width ($T$) for a given sequence period ($N$). Our approaches can produce various binary and polyphase ZCZ families with desired parameters $(N,K,T)$ and alphabet size. They also provide additional tradeoffs amongst the above four system parameters and are less constrained by the alphabet size. Furthermore, the constructed families have nested-like property that can be either decomposed or combined to constitute smaller or larger ZCZ sequence sets. We make detailed comparisons with related works and present some extended properties. For each approach, we provide examples to numerically illustrate the proposed construction procedure.
Survey of Multiscale and Multiphysics Applications and Communities
Venue: arXiv cs.OH 2013
Year: 2013

Multiscale and multiphysics applications are now commonplace, and many researchers focus on combining existing models to construct combined multiscale models. Here we present a concise review of multiscale applications and their source communities. We investigate the prevalence of multiscale projects in the EU and the US, review a range of coupling toolkits they use to construct multiscale models and identify areas where collaboration between disciplines could be particularly beneficial. We conclude that multiscale computing has become increasingly popular in recent years, that different communities adopt very different approaches to constructing multiscale simulations, and that simulations on a length scale of a few metres and a time scale of a few hours can be found in many of the multiscale research domains. Communities may receive additional benefit from sharing methods that are geared towards these scales.
The Degrees of Freedom Region of the MIMO Interference Channel with Hybrid CSIT
Venue: arXiv cs.IT 2013
Year: 2013

The degrees of freedom (DoF) region of the two-user MIMO (multiple-input multiple-output) interference channel is established under a new model termed as hybrid CSIT. In this model, one transmitter has delayed channel state information (CSI) and the other transmitter has instantaneous CSIT, of incoming channel matrices at the respective unpaired receivers, and neither transmitter has any knowledge of the incoming channel matrices of its respective paired receiver. The DoF region for hybrid CSIT, and consequently that of $2\times2\times3^{5}$ CSIT models, is completely characterized, and a new achievable scheme based on a combination of transmit beamforming and retrospective interference alignment is developed. Conditions are obtained on the numbers of antennas at each of the four terminals such that the DoF region under hybrid CSIT is equal to that under (a) global and instantaneous CSIT and (b) global and delayed CSIT, with the remaining cases resulting in a DoF region with hybrid CSIT that lies somewhere in between the DoF regions under the instantaneous and delayed CSIT settings. Further synergistic benefits accruing from switching between the two hybrid CSIT models are also explored.
Cross-Bifix-Free Codes Within a Constant Factor of Optimality
Venue: arXiv cs.IT 2013
Year: 2013

A cross-bifix-free code is a set of words in which no prefix of any length of any word is the suffix of any word in the set. Cross-bifix-free codes arise in the study of distributed sequences for frame synchronization. We provide a new construction of cross-bifix-free codes which generalizes the construction in Bajic (2007) to longer code lengths and to any alphabet size. The codes are shown to be nearly optimal in size. We also establish new results on Fibonacci sequences, that are used in estimating the size of the cross-bifix-free codes.
Constrained Multilinear Detection and Generalized Graph Motifs
Venue: arXiv cs.DS 2013
Year: 2013

We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. As applications of the technique, we show an $O^*(2^k)$-time polynomial space algorithm for the $k$-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute Graph Motif, and Min-Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an $O^*((2-ε)^k)$-time algorithm for the Graph Motif problem implies an $O((2-ε')^n)$-time algorithm for Set Cover.
Classification of binary systematic codes of small defect
Venue: arXiv cs.IT 2013
Year: 2013

In this paper non-trivial non-linear binary systematic AMDS codes are classified in terms of their weight distributions, employing only elementary techniques. In particular, we show that their length and minimum distance completely determine the weight distribution.
Diophantine Approach to Blind Interference Alignment of Homogeneous K-user 2x1 MISO Broadcast Channels
Venue: arXiv cs.IT 2013
Year: 2013

Although the sufficient condition for a blindly interference-aligned (BIA) 2-user 2x1 broadcast channel (BC) in homogeneous fading to achieve its maximal 4/3 DoF is well understood, its counterpart for the general K-user 2x1 MISO BC in homogeneous block fading to achieve the corresponding 2k/(2+K-1) (DoF) remains unsolved and is, thus, the focus of this paper. An interference channel is said BIA-feasible if it achieves its maximal DoF only via BIA. In this paper, we cast this general feasibility problem in the framework of finding integer solutions for a system of linear Diophantine equations. By assuming independent user links each of the same coherence time and by studying the solvability of the Diophantine system, we derive the sufficient and necessary conditions on the K users' fading block offsets to ensure the BIA feasibility of the K-user BC. If the K offsets are independent and uniformly distributed over a coherence block, we can further prove that 11 users are enough for one to find, with certainty of 95%, 3 users among them to form a BIA-feasible 3-user 2x1 BC.