OpenRaiser/Intern-Atlas huggingface dataset:
On the Spectral Efficiency of Full-Duplex Small Cell Wireless Systems
Venue: arXiv cs.IT 2014
Year: 2014

We investigate the spectral efficiency of full-duplex small cell wireless systems, in which a full-duplex capable base station (BS) is designed to send/receive data to/from multiple halfduplex users on the same system resources. The major hurdle for designing such systems is due to the self-interference at the BS and co-channel interference among users. Hence, we consider a joint beamformer design to maximize the spectral efficiency subject to certain power constraints. The design problem is first formulated as a rank-constrained optimization one, and the rank relaxation method is then applied. However the relaxed problem is still nonconvex, and thus optimal solutions are hard to find. Herein, we propose two provably convergent algorithms to obtain suboptimal solutions. Based on the concept of the difference of convex functions programming, we approximate the design problem by a determinant maximization program in each iteration of the first algorithm. The second method is built upon the sequential parametric convex approximation method, which allows us to transform the relaxed problem into a semidefinite program in each iteration. Extensive numerical experiments under small cell setups illustrate that the full-duplex system with the proposed algorithms can achieve a large gain over the half-duplex one.
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
Venue: arXiv cs.LG 2014
Year: 2014

We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure $ε$-differential privacy [Dwork et al. TCC 2006] and approximate $(ε,δ)$-differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approximate differential privacy can be significantly lower than that under pure differential privacy. We define a family of optimization problems, which we call Quasi-Concave Promise Problems, that generalizes some of our considered tasks. We observe that a quasi-concave promise problem can be privately approximated using a solution to a smaller instance of a quasi-concave promise problem. This allows us to construct an efficient recursive algorithm solving such problems privately. Specifically, we construct private learners for point functions, threshold functions, and axis-aligned rectangles in high dimension. Similarly, we construct sanitizers for point functions and threshold functions. We also examine the sample complexity of label-private learners, a relaxation of private learning where the learner is required to only protect the privacy of the labels in the sample. We show that the VC dimension completely characterizes the sample complexity of such learners, that is, the sample complexity of learning with label privacy is equal (up to constants) to learning without privacy.
Joint Downlink Base Station Association and Power Control for Max-Min Fairness: Computation and Complexity
Venue: arXiv cs.IT 2014
Year: 2014

In a heterogeneous network (HetNet) with a large number of low power base stations (BSs), proper user-BS association and power control is crucial to achieving desirable system performance. In this paper, we systematically study the joint BS association and power allocation problem for a downlink cellular network under the max-min fairness criterion. First, we show that this problem is NP-hard. Second, we show that the upper bound of the optimal value can be easily computed, and propose a two-stage algorithm to find a high-quality suboptimal solution. Simulation results show that the proposed algorithm is near-optimal in the high-SNR regime. Third, we show that the problem under some additional mild assumptions can be solved to global optima in polynomial time by a semi-distributed algorithm. This result is based on a transformation of the original problem to an assignment problem with gains $\log(g_{ij})$, where $\{g_{ij}\}$ are the channel gains.
A human centered perspective of E-maintenance
Venue: arXiv cs.HC 2014
Year: 2014

E-maintenance is a technology aiming to organize and structure the ICT during the whole life cycle of the product, to develop a maintenance support system that is effective and efficient. A current challenge of E-maintenance is the development of generic visualization solutions for users responsible for the maintenance. AR can be a potential technology for E-maintenance visualization, since it can bring knowledge to the real physical world, to assist the technician perform his/her work without the need to interrupt to consult manuals for information. This paper proposes a methodology for the development of advanced interfaces for human aware E-maintenance so that complex maintenance processes can be made safer, better quality, faster, anytime and anywhere.
Possibilities of technologization of philosophical knowledge
Venue: arXiv cs.AI 2014
Year: 2014

Article purpose is the analysis of a question of possibility of technologization of philosophical knowledge. We understand the organization of cognitive activity which is guided by the set of methods guaranteed bringing to successful (i.e. to precisely corresponding set parameters) to applied results as technologization. Transformation of sense of philosophy allows revealing possibilities of its technologization. The leading role in this process is played by philosophy of science which creates conditions for such transformation. At the same time there is justified an appeal to branch combination theory of the directions of scientific knowledge and partial refusal of understanding of philosophy as synthetic knowledge in which the main task is permission, instead of generation of paradoxes.
Fedra: Query Processing for SPARQL Federations with Divergence
Venue: arXiv cs.DB 2014
Year: 2014

Data replication and deployment of local SPARQL endpoints improve scalability and availability of public SPARQL endpoints, making the consumption of Linked Data a reality. This solution requires synchronization and specific query processing strategies to take advantage of replication. However, existing replication aware techniques in federations of SPARQL endpoints do not consider data dynamicity. We propose Fedra, an approach for querying federations of endpoints that benefits from replication. Participants in Fedra federations can copy fragments of data from several datasets, and describe them using provenance and views. These descriptions enable Fedra to reduce the number of selected endpoints while satisfying user divergence requirements. Experiments on real-world datasets suggest savings of up to three orders of magnitude.
A Survey of Named Entity Recognition in Assamese and other Indian Languages
Venue: arXiv cs.CL 2014
Year: 2014

Named Entity Recognition is always important when dealing with major Natural Language Processing tasks such as information extraction, question-answering, machine translation, document summarization etc so in this paper we put forward a survey of Named Entities in Indian Languages with particular reference to Assamese. There are various rule-based and machine learning approaches available for Named Entity Recognition. At the very first of the paper we give an idea of the available approaches for Named Entity Recognition and then we discuss about the related research in this field. Assamese like other Indian languages is agglutinative and suffers from lack of appropriate resources as Named Entity Recognition requires large data sets, gazetteer list, dictionary etc and some useful feature like capitalization as found in English cannot be found in Assamese. Apart from this we also describe some of the issues faced in Assamese while doing Named Entity Recognition.
Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
Venue: arXiv cs.CC 2014
Year: 2014

For a class $\mathcal{H}$ of graphs, #Sub$(\mathcal{H})$ is the counting problem that, given a graph $H\in \mathcal{H}$ and an arbitrary graph $G$, asks for the number of subgraphs of $G$ isomorphic to $H$. It is known that if $\mathcal{H}$ has bounded vertex-cover number (equivalently, the size of the maximum matching in $\mathcal{H}$ is bounded), then #Sub$(\mathcal{H})$ is polynomial-time solvable. We complement this result with a corresponding lower bound: if $\mathcal{H}$ is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub$(\mathcal{H})$ is #W[1]-hard parameterized by the size of $H$ and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT = #W[1]. As a first step of the proof, we show that counting $k$-matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting $k$-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no $f(k)n^{o(k/\log k)}$ time algorithm for counting $k$-matchings in bipartite graphs for any computable function $f(k)$. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length $k$ is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.
The asymmetric DoF Region for the 3-user MxN Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the 3-user Gaussian MIMO interference channel is considered. The asymmetric distribution of the DoF, where different users have different number of DoF, is studied. Two cases are presented, the first is when all transmitters and receivers have equal number of antennas $M$, the other when the transmitters have $M$ antennas each, while the receivers have $N$ antennas each. It is assumed that the channel coefficients are constant and known to all transmitters and receivers. The region of the achievable DoF tuple $(d_1; d_2; d_3)$ is presented.
Proving differential privacy in Hoare logic
Venue: arXiv cs.LO 2014
Year: 2014

Differential privacy is a rigorous, worst-case notion of privacy-preserving computation. Informally, a probabilistic program is differentially private if the participation of a single individual in the input database has a limited effect on the program's distribution on outputs. More technically, differential privacy is a quantitative 2-safety property that bounds the distance between the output distributions of a probabilistic program on adjacent inputs. Like many 2-safety properties, differential privacy lies outside the scope of traditional verification techniques. Existing approaches to enforce privacy are based on intricate, non-conventional type systems, or customized relational logics. These approaches are difficult to implement and often cumbersome to use. We present an alternative approach that verifies differential privacy by standard, non-relational reasoning on non-probabilistic programs. Our approach transforms a probabilistic program into a non-probabilistic program which simulates two executions of the original program. We prove that if the target program is correct with respect to a Hoare specification, then the original probabilistic program is differentially private. We provide a variety of examples from the differential privacy literature to demonstrate the utility of our approach. Finally, we compare our approach with existing verification techniques for privacy.
Hidden Markov Model Based Part of Speech Tagger for Sinhala Language
Venue: arXiv cs.CL 2014
Year: 2014

In this paper we present a fundamental lexical semantics of Sinhala language and a Hidden Markov Model (HMM) based Part of Speech (POS) Tagger for Sinhala language. In any Natural Language processing task, Part of Speech is a very vital topic, which involves analysing of the construction, behaviour and the dynamics of the language, which the knowledge could utilized in computational linguistics analysis and automation applications. Though Sinhala is a morphologically rich and agglutinative language, in which words are inflected with various grammatical features, tagging is very essential for further analysis of the language. Our research is based on statistical based approach, in which the tagging process is done by computing the tag sequence probability and the word-likelihood probability from the given corpus, where the linguistic knowledge is automatically extracted from the annotated corpus. The current tagger could reach more than 90% of accuracy for known words.
Budget-restricted utility games with ordered strategic decisions
Venue: arXiv cs.GT 2014
Year: 2014

We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analyzed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.
SketchBio: A Scientist's 3D Interface for Molecular Modeling and Animation
Venue: arXiv cs.GR 2014
Year: 2014

Background: Because of the difficulties involved in learning and using 3D modeling and rendering software, many scientists hire programmers or animators to create models and animations. This both slows the discovery process and provides opportunities for miscommunication. Working with multiple collaborators, we developed a set of design goals for a tool that would enable them to directly construct models and animations. Results: We present SketchBio, a tool that incorporates state-of-the-art bimanual interaction and drop shadows to enable rapid construction of molecular structures and animations. It includes three novel features: crystal by example, pose-mode physics, and spring-based layout that accelerate operations common in the formation of molecular models. We present design decisions and their consequences, including cases where iterative design was required to produce effective approaches. Conclusions: The design decisions, novel features, and inclusion of state-of-the-art techniques enabled SketchBio to meet all of its design goals. These features and decisions can be incorporated into existing and new tools to improve their effectiveness
A modern resistive magnetohydrodynamics solver using C++ and the Boost library
Venue: arXiv cs.NA 2014
Year: 2014

In this paper we describe the implementation of our C++ resistive magnetohydrodynamics solver. The framework developed facilitates the separation of the code implementing the specific numerical method and the physical model, on the one hand, from the handling of boundary conditions and the management of the computational domain, on the other hand. In particular, this will allow us to use finite difference stencils which are only defined in the interior of the domain (the boundary conditions are handled automatically). We will discuss this and other design considerations and their impact on performance in some detail. In addition, we provide a documentation of the code developed and demonstrate that a performance comparable to Fortran can be achieved, while still maintaining a maximum of code readability and extensibility.
Possibility neutrosophic soft sets with applications in decision making and similarity measure
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, concept of possibility neutrosophic soft set and its operations are defined, and their properties are studied. An application of this theory in decision making is investigated. Also a similarity measure of two possibility neutrosophic soft sets is introduced and discussed. Finally an application of this similarity measure is given to select suitable person for position in a firm.
Density Adaptive Parallel Clustering
Venue: arXiv cs.DS 2014
Year: 2014

In this paper we are going to introduce a new nearest neighbours based approach to clustering, and compare it with previous solutions; the resulting algorithm, which takes inspiration from both DBscan and minimum spanning tree approaches, is deterministic but proves simpler, faster and doesnt require to set in advance a value for k, the number of clusters.
LP-Based Algorithms for Capacitated Facility Location
Venue: arXiv cs.DS 2014
Year: 2014

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.
Case Study Of GIPSY and MARF
Venue: arXiv cs.SE 2014
Year: 2014

Metrics are used mainly to predict software engineering efforts such as maintenance effort, error Prone ness, and error rate. This document emphasis on experimental study based on two open source systems namely MARF and GIPSY. With the help of various research papers we were able to analyze and give priorities to various metrics that are implemented with JDeodrant. LOGISCOPE and McCabe tools are used to identify problematic classes with help of Kiviat graph and average Cyclomatic Complexity that further are implemented with highest priority metric with JDeodrant. To obtain accurate results we collected data using different tools. The analysis of the two systems is done as a conclusion of study using different tools.
Speech Polarity Detection Using Hilbert Phase Information
Venue: arXiv cs.SD 2014
Year: 2014

The objective of the present work is to propose a method to automatically detect polarity of the speech signals by estimating instants of significant excitation of the vocaltract and the cosine phase of the analytic signal representation. The phase changes in the analytic signal around the Hilbert envelope (HE) peaks are found to vary according to the polarity of the given speech signal. The relevant HE peaks for the Hilbert phase analysis are selected by estimating the instants of significant excitation in speech. The speech polarity identification rate obtained for the proposed method is almost equal to the state of the art residual skewness method for speech polarity detection. The proposed method also provides the same results for the polarity detection in electro-glottogram signals. Finally, the robustness of the proposed method is confirmed from the reduced detection error rates obtained in noisy environments with various signal to noise ratios (SNRs). The MATLAB codes used for implementing the proposed method are available for download from the following link: http://nlp.amrita.edu:8080/TTS/polarityprograms.zip
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity
Venue: arXiv cs.CC 2014
Year: 2014

We prove that the Fourier dimension of any Boolean function with Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof method yields an improved bound of $\widetilde{O}(\sqrt{s})$ assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every Boolean function of sparsity $s$ there is an affine subspace of $\mathbb{F}_2^n$ of co-dimension $O(\poly\log s)$ restricted to which the function is constant. This conjectured bound is tight upto poly-logarithmic factors as the Fourier dimension and sparsity of the address function are quadratically separated. We obtain these bounds by observing that the Fourier dimension of a Boolean function is equivalent to its non-adaptive parity decision tree complexity, and then bounding the latter.
A New Rational Algorithm for View Updating in Relational Databases
Venue: arXiv cs.AI 2014
Year: 2014

The dynamics of belief and knowledge is one of the major components of any autonomous system that should be able to incorporate new pieces of information. In order to apply the rationality result of belief dynamics theory to various practical problems, it should be generalized in two respects: first it should allow a certain part of belief to be declared as immutable; and second, the belief state need not be deductively closed. Such a generalization of belief dynamics, referred to as base dynamics, is presented in this paper, along with the concept of a generalized revision algorithm for knowledge bases (Horn or Horn logic with stratified negation). We show that knowledge base dynamics has an interesting connection with kernel change via hitting set and abduction. In this paper, we show how techniques from disjunctive logic programming can be used for efficient (deductive) database updates. The key idea is to transform the given database together with the update request into a disjunctive (datalog) logic program and apply disjunctive techniques (such as minimal model reasoning) to solve the original update problem. The approach extends and integrates standard techniques for efficient query answering and integrity checking. The generation of a hitting set is carried out through a hyper tableaux calculus and magic set that is focused on the goal of minimality.
Performance Comparison between Network Coding in Space and Routing in Space
Venue: arXiv cs.IT 2014
Year: 2014

Network coding in geometric space, a new research direction also known as Space Information Flow, is a promising research field which shows the superiority of network coding in space over routing in space. Present literatures proved that given six terminal nodes, network coding in space is strictly superior to routing in space in terms of single-source multicast in regular (5+1) model, in which five terminal nodes forms a regular pentagon centered at a terminal node. In order to compare the performance between network coding in space and routing in space, this paper quantitatively studies two classes of network coding in space and optimal routing in space when any terminal node moves arbitrarily in two-dimensional Euclidean space, and cost advantage is used as the metric. Furthermore, the upper-bound of cost advantage is figured out as well as the region where network coding in space is superior to routing in space. Several properties of Space Information Flow are also presented.
Market Share Indicates Quality
Venue: arXiv cs.GT 2014
Year: 2014

Market share and quality, or customer satisfaction, go together. Yet inferring one from the other appears difficult. Indeed, such an inference would need detailed information about customer behavior, and might be clouded by modes of behavior such as herding (following popularity) or elitism, where customers avoid popular products. We investigate a fixed-price model where customers are informed about their history with products and about market share data. We find that it is in fact correct to make a Bayesian inference that the product with the higher market share has the better quality under few and unrestrictive assumptions on customer behavior.