OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of Different Privacy Preserving Cloud Storage Frameworks
Venue: arXiv cs.CR 2012
Year: 2012

Privacy Security of data in Cloud Storage is one of the main issues. Many Frameworks and Technologies are used to preserve data security in cloud storage. [1] Proposes a framework which includes the design of data organization structure, the generation and management of keys, the treatment of change of user's access right and dynamic operations of data, and the interaction between participants. It also design an interactive protocol and an extirpation-based key derivation algorithm, which are combined with lazy revocation, it uses multi-tree structure and symmetric encryption to form a privacy-preserving, efficient framework for cloud storage. [2] Proposes a framework which design a privacy-preserving cloud storage framework in which he designed an interaction protocol among participants, use key derivation algorithm to generate and manage keys, use both symmetric and asymmetric encryption to hide the sensitive data of users, and apply Bloom filter for cipher text retrieval. A system based on this framework is realized. This paper analyzes both the frameworks in terms of the feasibility of the frameworks, running overhead of the system and the privacy security of the frameworks.
Juppix: a Linux Live-CD for Undergraduate Students
Venue: arXiv cs.OH 2012
Year: 2012

Juppix is a Linux Live-CD with a comfortable programming environment for the Java, C and O'Caml programming languages that has been distributed to hundreds of undergaduate students at the University of Paris 7 over the last few years. We describe the lessons we learnt while compiling and distributing Juppix, and outline our future plans.
Cellular Multi-User Two-Way MIMO AF Relaying via Signal Space Alignment: Minimum Weighted SINR Maximization
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider linear MIMO transceiver design for a cellular two-way amplify-and-forward relaying system consisting of a single multi-antenna base station, a single multi-antenna relay station, and multiple multi-antenna mobile stations (MSs). Due to the two-way transmission, the MSs could suffer from tremendous multi-user interference. We apply an interference management model exploiting signal space alignment and propose a transceiver design algorithm, which allows for alleviating the loss in spectral efficiency due to half-duplex operation and providing flexible performance optimization accounting for each user's quality of service priorities. Numerical comparisons to conventional two-way relaying schemes based on bidirectional channel inversion and spatial division multiple access-only processing show that the proposed scheme achieves superior error rate and average data rate performance.
A Heterogeneous Accelerated Matrix Multiplication: OpenCL + APU + GPU+ Fast Matrix Multiply
Venue: arXiv cs.MS 2012
Year: 2012

As users and developers, we are witnessing the opening of a new computing scenario: the introduction of hybrid processors into a single die, such as an accelerated processing unit (APU) processor, and the plug-and-play of additional graphics processing units (GPUs) onto a single motherboard. These APU processors provide multiple symmetric cores with their memory hierarchies and an integrated GPU. Moreover, these processors are designed to work with external GPUs that can push the peak performance towards the TeraFLOPS boundary. We present a case study for the development of dense Matrix Multiplication (MM) codes for matrix sizes up to 19K\times19K, thus using all of the above computational engines, and an achievable peak performance of 200 GFLOPS for, literally, a made- at-home built. We present the results of our experience, the quirks, the pitfalls, the achieved performance, and the achievable peak performance.
Design and implementation of a differentiated service based qos model for real-time interactive traffic on constrained bandwidth ip networks
Venue: arXiv cs.NI 2012
Year: 2012

In this thesis work, a QoS model for real-time interactive traffic on a real network with constrained bandwidth and real-time traffic has been proposed. The model supports tight guarantees of QoS to real-time interactive traffic without over provisioning of bandwidth. A dynamic scheduling model which is adaptive to input data rate of traffic has been proposed. In this model, A Differentiated Service (DiffServ) based approach is proposed for QoS provisioning. The packets are classified and distributed among finite number of queues with limited buffer based on different priorities and total available bandwidth. The model proposes a mechanism to derive the weighted service rates and queue length distribution so as to meet the requirement of low packet loss and delay for real time interactive traffic in the QoS engineered network. An adaptive queuing strategy is proposed so that minimum bandwidth in used for real time traffic. This ensures maximizing availability to best effort traffic. The model assumes constrained bandwidth without having to over provision the network resources and thus keeping the cost low. A modified version suitable for testing on a real network is also presented. Experimental verification of these in a test bed network in a laboratory as well as on a real network has been carried out. The results of the QoS provisioning model for different sources of real-time traffic such as video conferencing equipment, robotic surveillance camera has also been shown. The thesis also introduces a real-time Variable Bit Rate (VBR) traffic tuning parameter for controlling the service of VBR traffic to give better and fair performance to rest of the traffic.
Tree Projections and Structural Decomposition Methods: The Power of Local Consistency and Larger Islands of Tractability
Venue: arXiv cs.DB 2012
Year: 2012

Evaluating conjunctive queries and solving constraint satisfaction problems are fundamental problems in database theory and artificial intelligence, respectively. These problems are NP-hard, so that several research efforts have been made in the literature for identifying tractable classes, known as islands of tractability, as well as for devising clever heuristics for solving efficiently real-world instances. Many heuristic approaches are based on enforcing on the given instance a property called local consistency, where (in database terms) each tuple in every query atom matches at least one tuple in every other query atom. Interestingly, it turns out that, for many well-known classes of queries, such as for the acyclic queries, enforcing local consistency is even sufficient to solve the given instance correctly. However, the precise power of such a procedure was unclear, but for some very restricted cases. The paper provides full answers to the long-standing questions about the precise power of algorithms based on enforcing local consistency. The classes of instances where enforcing local consistency turns out to be a correct query-answering procedure are however not efficiently recognizable. In fact, the paper finally focuses on certain subclasses defined in terms of the novel notion of greedy tree projections. These latter classes are shown to be efficiently recognizable and strictly larger than most islands of tractability known so far, both in the general case of tree projections and for specific structural decomposition methods.
1.85 Approximation for Min-Power Strong Connectivity
Venue: arXiv cs.DS 2012
Year: 2012

Given a directed simple graph G=(V,E) and a nonnegative-valued cost function the power of a vertex u in a directed spanning subgraph H is given by the maximum cost of an arcs of H exiting u. The power of H is the sum of the power of its vertices. Power Assignment seeks to minimize the power of H while H satisfies some connectivity constraint. In this paper, we assume E is bidirected (for every directed edge e in E, the opposite edge exists and has the same cost), while H is required to be strongly connected. This is the original power assignment problem introduced by Chen and Huang in 1989, who proved that bidirected minimum spanning tree has approximation ratio at most 2 (this is tight). In Approx 2010, we introduced a Greedy approximation algorithm and claimed a ratio of 1.992. Here we improve the analysis to 1.85. The proof also shows that a natural linear programming relaxation, introduced by us in 2012, has the same 1.85 integrality gap.
Bounded epsilon-Reach Set Computation of a Class of Deterministic and Transversal Linear Hybrid Automata
Venue: arXiv cs.SY 2012
Year: 2012

We define a special class of hybrid automata, called Deterministic and Transversal Linear Hybrid Automata (DTLHA), whose continuous dynamics in each location are linear time-invariant (LTI) with a constant input, and for which every discrete transition up to a given bounded time is deterministic and, importantly, transversal. For such a DTLHA starting from an initial state, we show that it is possible to compute an approximation of the reach set of a DTLHA over a finite time interval that is arbitrarily close to the exact reach set, called a bounded epsilon-reach set, through sampling and polyhedral over-approximation of sampled states. We propose an algorithm and an attendant architecture for the overall bounded epsilon-reach set computation process.
Degrees-of-Freedom Region of the MISO Broadcast Channel with General Mixed-CSIT
Venue: arXiv cs.IT 2012
Year: 2012

In the setting of the two-user broadcast channel, recent work by Maddah-Ali and Tse has shown that knowledge of prior channel state information at the transmitter (CSIT) can be useful, even in the absence of any knowledge of current CSIT. Very recent work by Kobayashi et al., Yang et al., and Gou and Jafar, extended this to the case where, instead of no current CSIT knowledge, the transmitter has partial knowledge, and where under a symmetry assumption, the quality of this knowledge is identical for the different users' channels. Motivated by the fact that in multiuser settings, the quality of CSIT feedback may vary across different links, we here generalize the above results to the natural setting where the current CSIT quality varies for different users' channels. For this setting we derive the optimal degrees-of-freedom (DoF) region, and provide novel multi-phase broadcast schemes that achieve this optimal region. Finally this generalization incorporates and generalizes the corresponding result in Maleki et al. which considered the broadcast channel with one user having perfect CSIT and the other only having prior CSIT.
Lower Bounds for Adaptive Sparse Recovery
Venue: arXiv cs.DS 2012
Year: 2012

We give lower bounds for the problem of stable sparse recovery from /adaptive/ linear measurements. In this problem, one would like to estimate a vector $x \in \R^n$ from $m$ linear measurements $A_1x,..., A_mx$. One may choose each vector $A_i$ based on $A_1x,..., A_{i-1}x$, and must output $x*$ satisfying |x* - x|_p \leq (1 + ε) \min_{k\text{-sparse} x'} |x - x'|_p with probability at least $1-δ>2/3$, for some $p \in \{1,2\}$. For $p=2$, it was recently shown that this is possible with $m = O(\frac{1}εk \log \log (n/k))$, while nonadaptively it requires $Θ(\frac{1}εk \log (n/k))$. It is also known that even adaptively, it takes $m = Ω(k/ε)$ for $p = 2$. For $p = 1$, there is a non-adaptive upper bound of $\tilde{O}(\frac{1}{\sqrtε} k\log n)$. We show: * For $p=2$, $m = Ω(\log \log n)$. This is tight for $k = O(1)$ and constant $ε$, and shows that the $\log \log n$ dependence is correct. * If the measurement vectors are chosen in $R$ "rounds", then $m = Ω(R \log^{1/R} n)$. For constant $ε$, this matches the previously known upper bound up to an O(1) factor in $R$. * For $p=1$, $m = Ω(k/(\sqrtε \cdot \log k/ε))$. This shows that adaptivity cannot improve more than logarithmic factors, providing the analog of the $m = Ω(k/ε)$ bound for $p = 2$.
Limits of Random Oracles in Secure Computation
Venue: arXiv cs.CR 2012
Year: 2012

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for certain Secure Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer). Surprisingly, however, {\em since then there has been no further progress in separating one-way functions and SFE functionalities} (though several other black-box separation results were shown). In this work, we present the complete picture for deterministic 2-party SFE functionalities. We show that one-way functions are black-box separated from {\em all such SFE functionalities}, except the ones which have unconditionally secure protocols (and hence do not rely on any computational hardness), when secure computation against semi-honest adversaries is considered. In the case of security against active adversaries, a black-box one-way function is indeed useful for SFE, but we show that it is useful only as much as access to an ideal commitment functionality is useful. Technically, our main result establishes the limitations of random oracles for secure computation.
Scheduling and allocation algorithm for an elliptic filter
Venue: arXiv cs.DS 2012
Year: 2012

A new evolutionary algorithm for scheduling and allocation algorithm is developed for an elliptic filter. The elliptic filter is scheduled and allocated in the proposed work which is then compared with the different scheduling algorithms like As Soon As Possible algorithm, As Late As Possible algorithm, Mobility Based Shift algorithm, FDLS, FDS and MOGS. In this paper execution time and resource utilization is calculated using different scheduling algorithm for an Elliptic Filter and reported that proposed Scheduling and Allocation increases the speed of operation by reducing the control step. The proposed work to analyse the magnitude, phase and noise responses for different scheduling algorithm in an elliptic filter.
Computing Socially-Efficient Cake Divisions
Venue: arXiv cs.GT 2012
Year: 2012

We consider a setting in which a single divisible good ("cake") needs to be divided between n players, each with a possibly different valuation function over pieces of the cake. For this setting, we address the problem of finding divisions that maximize the social welfare, focusing on divisions where each player needs to get one contiguous piece of the cake. We show that for both the utilitarian and the egalitarian social welfare functions it is NP-hard to find the optimal division. For the utilitarian welfare, we provide a constant factor approximation algorithm, and prove that no FPTAS is possible unless P=NP. For egalitarian welfare, we prove that it is NP-hard to approximate the optimum to any factor smaller than 2. For the case where the number of players is small, we provide an FPT (fixed parameter tractable) FPTAS for both the utilitarian and the egalitarian welfare objectives.
Extraction of Historical Events from Wikipedia
Venue: arXiv cs.IR 2012
Year: 2012

The DBpedia project extracts structured information from Wikipedia and makes it available on the web. Information is gathered mainly with the help of infoboxes that contain structured information of the Wikipedia article. A lot of information is only contained in the article body and is not yet included in DBpedia. In this paper we focus on the extraction of historical events from Wikipedia articles that are available for about 2,500 years for different languages. We have extracted about 121,000 events with more than 325,000 links to DBpedia entities and provide access to this data via a Web API, SPARQL endpoint, Linked Data Interface and in a timeline application.
Theory of Dependent Hierarchical Normalized Random Measures
Venue: arXiv cs.LG 2012
Year: 2012

This paper presents theory for Normalized Random Measures (NRMs), Normalized Generalized Gammas (NGGs), a particular kind of NRM, and Dependent Hierarchical NRMs which allow networks of dependent NRMs to be analysed. These have been used, for instance, for time-dependent topic modelling. In this paper, we first introduce some mathematical background of completely random measures (CRMs) and their construction from Poisson processes, and then introduce NRMs and NGGs. Slice sampling is also introduced for posterior inference. The dependency operators in Poisson processes and for the corresponding CRMs and NRMs is then introduced and Posterior inference for the NGG presented. Finally, we give dependency and composition results when applying these operators to NRMs so they can be used in a network with hierarchical and dependent relations.
Deployment of software components: Application to Wireless System
Venue: arXiv cs.SE 2012
Year: 2012

The wide variety of wireless devices brings to design mobile applications as a collection of interchangeable software components adapted to the deployment environment of the software. To ensure the proper functioning of the software assembly and make a real enforcement in case of failures, the introduction of concepts, models and tools necessary for the administration of these components is crucial. This article proposes a method for deploying components in wireless systems.
Chernoff Bounds for Analysis of Rate-Compatible Sphere-Packing with Numerous Transmissions
Venue: arXiv cs.IT 2012
Year: 2012

Recent results by Chen et al. and Polyanskiy et al. explore using feedback to approach capacity with short blocklengths. This paper explores Chernoff bounding techniques to extend the rate-compatible sphere-packing (RCSP) analysis proposed by Chen et al. to scenarios involving numerous retransmissions and different step sizes in each incremental retransmission. Williamson et al. employ exact RCSP computations for up to six transmissions. However, exact RCSP computation with more than six retransmissions becomes unwieldy because of joint error probabilities involving numerous chi-squared distributions. This paper explores Chernoff approaches for upper and lower bounds to provide support for computations involving more than six transmissions. We present two versions of upper and lower bounds for the two-transmission case. One of the versions is extended to the general case of $m$ transmissions where $m \geq 1$. Computing the general bounds requires minimization of exponential functions with the auxiliary parameters, but is less complex and more stable than multiple rounds of numerical integration. These bounds also provide a good estimate of the expected throughput and expected latency, which are useful for optimization purposes.
Graph-based Code Design for Quadratic-Gaussian Wyner-Ziv Problem with Arbitrary Side Information
Venue: arXiv cs.IT 2012
Year: 2012

Wyner-Ziv coding (WZC) is a compression technique using decoder side information, which is unknown at the encoder, to help the reconstruction. In this paper, we propose and implement a new WZC structure, called residual WZC, for the quadratic-Gaussian Wyner-Ziv problem where side information can be arbitrarily distributed. In our two-stage residual WZC, the source is quantized twice and the input of the second stage is the quantization error (residue) of the first stage. The codebook of the first stage quantizer must be simultaneously good for source and channel coding, since it also acts as a channel code at the decoder. Stemming from the non-ideal quantization at the encoder, a problem of channel decoding beyond capacity is identified and solved when we design the practical decoder. Moreover,by using the modified reinforced belief-propagation quantization algorithm, the low-density parity check code (LDPC), whose edge degree is optimized for channel coding, also performs well as a source code. We then implement the residual WZC by an LDPC and a low density generator matrix code (LDGM). The simulation results show that our practical construction approaches the Wyner-Ziv bound. Compared with previous works, our construction can offer more design lexibility in terms of distribution of side information and practical code rate selection.
On Providing Downlink Services in Collocated Spectrum-Sharing Macro and Femto Networks
Venue: arXiv cs.NI 2012
Year: 2012

Femtocells have been considered by the wireless industry as a cost-effective solution not only to improve indoor service providing, but also to unload traffic from already overburdened macro networks. Due to spectrum availability and network infrastructure considerations, a macro network may have to share spectrum with overlaid femtocells. In spectrum-sharing macro and femto networks, inter-cell interference caused by different transmission powers of macrocell base stations (MBS) and femtocell access points (FAP), in conjunction with potentially densely deployed femtocells, may create dead spots where reliable services cannot be guaranteed to either macro or femto users. In this paper, based on a thorough analysis of downlink (DL) outage probabilities (OP) of collocated spectrum-sharing orthogonal frequency division multiple access (OFDMA) based macro and femto networks, we devise a decentralized strategy for an FAP to self-regulate its transmission power level and usage of radio resources depending on its distance from the closest MBS. Simulation results show that the derived closed-form lower bounds of DL OPs are tight, and the proposed decentralized femtocell self-regulation strategy is able to guarantee reliable DL services in targeted macro and femto service areas while providing superior spatial reuse, for even a large number of spectrum-sharing femtocells deployed per cell site.
Minimum Mean-Squared Error Iterative Successive Parallel Arbitrated Decision Feedback Detectors for DS-CDMA Systems
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we propose minimum mean squared error (MMSE) iterative successive parallel arbitrated decision feedback (DF) receivers for direct sequence code division multiple access (DS-CDMA) systems. We describe the MMSE design criterion for DF multiuser detectors along with successive, parallel and iterative interference cancellation structures. A novel efficient DF structure that employs successive cancellation with parallel arbitrated branches and a near-optimal low complexity user ordering algorithm are presented. The proposed DF receiver structure and the ordering algorithm are then combined with iterative cascaded DF stages for mitigating the deleterious effects of error propagation for convolutionally encoded systems with both Viterbi and turbo decoding as well as for uncoded schemes. We mathematically study the relations between the MMSE achieved by the analyzed DF structures, including the novel scheme, with imperfect and perfect feedback. Simulation results for an uplink scenario assess the new iterative DF detectors against linear receivers and evaluate the effects of error propagation of the new cancellation methods against existing ones.
Reduced-Rank Adaptive Filtering Based on Joint Iterative Optimization of Adaptive Filters
Venue: arXiv cs.IT 2012
Year: 2012

This letter proposes a novel adaptive reduced-rank filtering scheme based on joint iterative optimization of adaptive filters. The novel scheme consists of a joint iterative optimization of a bank of full-rank adaptive filters that forms the projection matrix and an adaptive reduced-rank filter that operates at the output of the bank of filters. We describe minimum mean-squared error (MMSE) expressions for the design of the projection matrix and the reduced-rank filter and low-complexity normalized least-mean squares (NLMS) adaptive algorithms for its efficient implementation. Simulations for an interference suppression application show that the proposed scheme outperforms in convergence and tracking the state-ofthe- art reduced-rank schemes at significantly lower complexity.