OpenRaiser/Intern-Atlas huggingface dataset:
Engineering Crowdsourced Stream Processing Systems
Venue: arXiv cs.DB 2014
Year: 2014

A crowdsourced stream processing system (CSP) is a system that incorporates crowdsourced tasks in the processing of a data stream. This can be seen as enabling crowdsourcing work to be applied on a sample of large-scale data at high speed, or equivalently, enabling stream processing to employ human intelligence. It also leads to a substantial expansion of the capabilities of data processing systems. Engineering a CSP system requires the combination of human and machine computation elements. From a general systems theory perspective, this means taking into account inherited as well as emerging properties from both these elements. In this paper, we position CSP systems within a broader taxonomy, outline a series of design principles and evaluation metrics, present an extensible framework for their design, and describe several design patterns. We showcase the capabilities of CSP systems by performing a case study that applies our proposed framework to the design and analysis of a real system (AIDR) that classifies social media messages during time-critical crisis events. Results show that compared to a pure stream processing system, AIDR can achieve a higher data classification accuracy, while compared to a pure crowdsourcing solution, the system makes better use of human workers by requiring much less manual work effort.
On Sparse Representation in Fourier and Local Bases
Venue: arXiv cs.IT 2014
Year: 2014

We consider the classical problem of finding the sparse representation of a signal in a pair of bases. When both bases are orthogonal, it is known that the sparse representation is unique when the sparsity $K$ of the signal satisfies $K<1/μ(D)$, where $μ(D)$ is the mutual coherence of the dictionary. Furthermore, the sparse representation can be obtained in polynomial time by Basis Pursuit (BP), when $K<0.91/μ(D)$. Therefore, there is a gap between the unicity condition and the one required to use the polynomial-complexity BP formulation. For the case of general dictionaries, it is also well known that finding the sparse representation under the only constraint of unicity is NP-hard. In this paper, we introduce, for the case of Fourier and canonical bases, a polynomial complexity algorithm that finds all the possible $K$-sparse representations of a signal under the weaker condition that $K<\sqrt{2} /μ(D)$. Consequently, when $K<1/μ(D)$, the proposed algorithm solves the unique sparse representation problem for this structured dictionary in polynomial time. We further show that the same method can be extended to many other pairs of bases, one of which must have local atoms. Examples include the union of Fourier and local Fourier bases, the union of discrete cosine transform and canonical bases, and the union of random Gaussian and canonical bases.
Cryptanalysis of Sun and Cao's Remote Authentication Scheme with User Anonymity
Venue: arXiv cs.CR 2014
Year: 2014

Dynamic ID-based remote user authentication schemes ensure efficient and anonymous mutual authentication between entities. In 2013, Khan et al. proposed an improved dynamic ID-based authentication scheme to overcome the security flaws of Wang et al.'s authentication scheme. Recently, Sun and Cao showed that Khan et al. does not satisfies the claim of the user's privacy and proposed an efficient authentication scheme with user anonymity. The Sun and Cao's scheme achieve improvement over Khan et al.'s scheme in both privacy and performance point of view. Unfortunately, we identify that Sun and Cao's scheme does not resist password guessing attack. Additionally, Sun and Cao's scheme does not achieve forward secrecy.
Simultaneous Information and Energy Transfer in Large-Scale Networks with/without Relaying
Venue: arXiv cs.IT 2014
Year: 2014

Energy harvesting (EH) from ambient radio-frequency (RF) electromagnetic waves is an efficient solution for fully autonomous and sustainable communication networks. Most of the related works presented in the literature are based on specific (and small-scale) network structures, which although give useful insights on the potential benefits of the RF-EH technology, cannot characterize the performance of general networks. In this paper, we adopt a large-scale approach of the RF-EH technology and we characterize the performance of a network with random number of transmitter-receiver pairs by using stochastic-geometry tools. Specifically, we analyze the outage probability performance and the average harvested energy, when receivers employ power splitting (PS) technique for "simultaneous" information and energy transfer. A non-cooperative scheme, where information/energy are conveyed only via direct links, is firstly considered and the outage performance of the system as well as the average harvested energy are derived in closed form in function of the power splitting. For this protocol, an interesting optimization problem which minimizes the transmitted power under outage probability and harvesting constraints, is formulated and solved in closed form. In addition, we study a cooperative protocol where sources' transmissions are supported by a random number of potential relays that are randomly distributed into the network. In this case, information/energy can be received at each destination via two independent and orthogonal paths (in case of relaying). We characterize both performance metrics, when a selection combining scheme is applied at the receivers and a single relay is randomly selected for cooperative diversity.
Downlink Multi-Antenna Heterogeneous Cellular Network with Load Balancing
Venue: arXiv cs.IT 2014
Year: 2014

We model and analyze heterogeneous cellular networks with multiple antenna BSs (multi-antenna HetNets) with K classes or tiers of base stations (BSs), which may differ in terms of transmit power, deployment density, number of transmit antennas, number of users served, transmission scheme, and path loss exponent. We show that the cell selection rules in multi-antenna HetNets may differ significantly from the single-antenna HetNets due to the possible differences in multi-antenna transmission schemes across tiers. While it is challenging to derive exact cell selection rules even for maximizing signal-to-interferenceplus-noise-ratio (SINR) at the receiver, we show that adding an appropriately chosen tier-dependent cell selection bias in the received power yields a close approximation. Assuming arbitrary selection bias for each tier, simple expressions for downlink coverage and rate are derived. For coverage maximization, the required selection bias for each tier is given in closed form. Due to this connection with biasing, multi-antenna HetNets may balance load more naturally across tiers in certain regimes compared to single-antenna HetNets, where a large cell selection bias is often needed to offload traffic to small cells.
Joint Wireless Information and Energy Transfer in a K-User MIMO Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

Recently, joint wireless information and energy transfer (JWIET) methods have been proposed to relieve the battery limitation of wireless devices. However, the JWIET in a general K-user MIMO interference channel (IFC) has been unexplored so far. In this paper, we investigate for the first time the JWIET in K-user MIMO IFC, in which receivers either decode the incoming information data (information decoding, ID) or harvest the RF energy (energy harvesting, EH). In the K-user IFC, we consider three different scenarios according to the receiver mode -- i) multiple EH receivers and a single ID receiver, ii) multiple IDs and a single EH, and iii) multiple IDs and multiple EHs. For all scenarios, we have found a common necessary condition of the optimal transmission strategy and, accordingly, developed the transmission strategy that satisfies the common necessary condition, in which all the transmitters transferring energy exploit a rank-one energy beamforming. Furthermore, we have also proposed an iterative algorithm to optimize the covariance matrices of the transmitters that transfer information and the powers of the energy beamforming transmitters simultaneously, and identified the corresponding achievable rate-energy tradeoff region. Finally, we have shown that by selecting EH receivers according to their signal-to-leakage-and-harvested energy-ratio (SLER), we can improve the achievable rate-energy region further.
Energy Efficiency Optimization in Relay-Assisted MIMO Systems with Perfect and Statistical CSI
Venue: arXiv cs.IT 2014
Year: 2014

A framework for energy-efficient resource allocation in a single-user, amplify-and-forward relay-assisted MIMO system is devised in this paper. Previous results in this area have focused on rate maximization or sum power minimization problems, whereas fewer results are available when bits/Joule energy efficiency (EE) optimization is the goal. The performance metric to optimize is the ratio between the system's achievable rate and the total consumed power. The optimization is carried out with respect to the source and relay precoding matrices, subject to QoS and power constraints. Such a challenging non-convex problem is tackled by means of fractional programming and and alternating maximization algorithms, for various CSI assumptions at the source and relay. In particular the scenarios of perfect CSI and those of statistical CSI for either the source-relay or the relay-destination channel are addressed. Moreover, sufficient conditions for beamforming optimality are derived, which is useful in simplifying the system design. Numerical results are provided to corroborate the validity of the theoretical findings.
Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of sparse coding, where each sample consists of a sparse linear combination of a set of dictionary atoms, and the task is to learn both the dictionary elements and the mixing coefficients. Alternating minimization is a popular heuristic for sparse coding, where the dictionary and the coefficients are estimated in alternate steps, keeping the other fixed. Typically, the coefficients are estimated via $\ell_1$ minimization, keeping the dictionary fixed, and the dictionary is estimated through least squares, keeping the coefficients fixed. In this paper, we establish local linear convergence for this variant of alternating minimization and establish that the basin of attraction for the global optimum (corresponding to the true dictionary and the coefficients) is $\order{1/s^2}$, where $s$ is the sparsity level in each sample and the dictionary satisfies RIP. Combined with the recent results of approximate dictionary estimation, this yields provable guarantees for exact recovery of both the dictionary elements and the coefficients, when the dictionary elements are incoherent.
Capacity and Delay-Throughput Tradeoff in ICMNs with Poisson Meeting Process
Venue: arXiv cs.NI 2014
Year: 2014

Intermittently connected mobile networks (ICMNs) serve as an important network model for many critical applications. This paper focuses on a continuous ICMN model where the pair-wise meeting process between network nodes follows a homogeneous and independent Poisson process. This ICMN model is known to serve as good approximations to a class of important ICMNs with mobility models like random waypoint and random direction, so it is widely adopted in the performance study of ICMNs. This paper studies the throughput capacity and delay-throughput tradeoff in the considered ICMNs with Poisson meeting process. For the concerned ICMN, we first derive an exact expression of its throughput capacity based on the pairwise meeting rate therein and analyze the expected end-to-end packet delay under a routing algorithm that can achieve the throughput capacity. We then explore the inherent tradeoff between delay and throughput and establish a necessary condition for such tradeoff that holds under any routing algorithm in the ICMN. To illustrate the applicability of the theoretical results, case studies are further conducted for the random waypoint and random direction mobility models. Finally, simulation and numerical results are provided to verify the efficiency of our theoretical capacity/delay results and to illustrate our findings.
Using Surface-Motions for Locomotion of Microscopic Robots in Viscous Fluids
Venue: arXiv cs.RO 2014
Year: 2014

Microscopic robots could perform tasks with high spatial precision, such as acting in biological tissues on the scale of individual cells, provided they can reach precise locations. This paper evaluates the feasibility of in vivo locomotion for micron-size robots. Two appealing methods rely only on surface motions: steady tangential motion and small amplitude oscillations. These methods contrast with common microorganism propulsion based on flagella or cilia, which are more likely to damage nearby cells if used by robots made of stiff materials. The power potentially available to robots in tissue supports speeds ranging from one to hundreds of microns per second, over the range of viscosities found in biological tissue. We discuss design trade-offs among propulsion method, speed, power, shear forces and robot shape, and relate those choices to robot task requirements. This study shows that realizing such locomotion requires substantial improvements in fabrication capabilities and material properties over current technology.
Quasi-Static Multiple-Antenna Fading Channels at Finite Blocklength
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates the maximal achievable rate for a given blocklength and error probability over quasi-static multiple-input multiple-output (MIMO) fading channels, with and without channel state information (CSI) at the transmitter and/or the receiver. The principal finding is that outage capacity, despite being an asymptotic quantity, is a sharp proxy for the finite-blocklength fundamental limits of slow-fading channels. Specifically, the channel dispersion is shown to be zero regardless of whether the fading realizations are available at both transmitter and receiver, at only one of them, or at neither of them. These results follow from analytically tractable converse and achievability bounds. Numerical evaluation of these bounds verifies that zero dispersion may indeed imply fast convergence to the outage capacity as the blocklength increases. In the example of a particular $1 \times 2$ single-input multiple-output (SIMO) Rician fading channel, the blocklength required to achieve $90\%$ of capacity is about an order of magnitude smaller compared to the blocklength required for an AWGN channel with the same capacity. For this specific scenario, the coding/decoding schemes adopted in the LTE-Advanced standard are benchmarked against the finite-blocklength achievability and converse bounds.
Breaking the PPSZ Barrier for Unique 3-SAT
Venue: arXiv cs.CC 2014
Year: 2014

The PPSZ algorithm by Paturi, Pudlák, Saks, and Zane (FOCS 1998) is the fastest known algorithm for (Promise) Unique k-SAT. We give an improved algorithm with exponentially faster bounds for Unique 3-SAT. For uniquely satisfiable 3-CNF formulas, we do the following case distinction: We call a clause critical if exactly one literal is satisfied by the unique satisfying assignment. If a formula has many critical clauses, we observe that PPSZ by itself is already faster. If there are only few clauses allover, we use an algorithm by Wahlström (ESA 2005) that is faster than PPSZ in this case. Otherwise we have a formula with few critical and many non-critical clauses. Non-critical clauses have at least two literals satisfied; we show how to exploit this to improve PPSZ.
A New Look at Dual-Hop Relaying: Performance Limits with Hardware Impairments
Venue: arXiv cs.IT 2014
Year: 2014

Physical transceivers have hardware impairments that create distortions which degrade the performance of communication systems. The vast majority of technical contributions in the area of relaying neglect hardware impairments and, thus, assumes ideal hardware. Such approximations make sense in low-rate systems, but can lead to very misleading results when analyzing future high-rate systems. This paper quantifies the impact of hardware impairments on dual-hop relaying, for both amplify-and-forward and decode-and-forward protocols. The outage probability (OP) in these practical scenarios is a function of the effective end-to-end signal-to-noise-and-distortion ratio (SNDR). This paper derives new closed-form expressions for the exact and asymptotic OPs, accounting for hardware impairments at the source, relay, and destination. A similar analysis for the ergodic capacity is also pursued, resulting in new upper bounds. We assume that both hops are subject to independent but non-identically distributed Nakagami-m fading. This paper validates that the performance loss is small at low rates, but otherwise can be very substantial. In particular, it is proved that for high signal-to-noise ratio (SNR), the end-to-end SNDR converges to a deterministic constant, coined the SNDR ceiling, which is inversely proportional to the level of impairments. This stands in contrast to the ideal hardware case in which the end-to-end SNDR grows without bound in the high-SNR regime. Finally, we provide fundamental design guidelines for selecting hardware that satisfies the requirements of a practical relaying system.
Large Independent Sets in Triangle-Free Planar Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Every triangle-free planar graph on n vertices has an independent set of size at least (n+1)/3, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph G on n vertices and an integer k>=0, decides whether G has an independent set of size at least (n+k)/3, in time 2^{O(sqrt{k})}n. Thus, the problem is fixed-parameter tractable when parameterized by k. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists epsilon>0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n/(3-epsilon).
SUNNY: a Lazy Portfolio Approach for Constraint Solving
Venue: arXiv cs.AI 2014
Year: 2014

*** To appear in Theory and Practice of Logic Programming (TPLP) *** Within the context of constraint solving, a portfolio approach allows one to exploit the synergy between different solvers in order to create a globally better solver. In this paper we present SUNNY: a simple and flexible algorithm that takes advantage of a portfolio of constraint solvers in order to compute --- without learning an explicit model --- a schedule of them for solving a given Constraint Satisfaction Problem (CSP). Motivated by the performance reached by SUNNY vs. different simulations of other state of the art approaches, we developed sunny-csp, an effective portfolio solver that exploits the underlying SUNNY algorithm in order to solve a given CSP. Empirical tests conducted on exhaustive benchmarks of MiniZinc models show that the actual performance of SUNNY conforms to the predictions. This is encouraging both for improving the power of CSP portfolio solvers and for trying to export them to fields such as Answer Set Programming and Constraint Logic Programming.
On the Adaptivity Gap of Stochastic Orienteering
Venue: arXiv cs.DS 2014
Year: 2014

The input to the stochastic orienteering problem consists of a budget $B$ and metric $(V,d)$ where each vertex $v$ has a job with deterministic reward and random processing time (drawn from a known distribution). The processing times are independent across vertices. The goal is to obtain a non-anticipatory policy to run jobs at different vertices, that maximizes expected reward, subject to the total distance traveled plus processing times being at most $B$. An adaptive policy is one that can choose the next vertex to visit based on observed random instantiations. Whereas, a non-adaptive policy is just given by a fixed ordering of vertices. The adaptivity gap is the worst-case ratio of the expected rewards of the optimal adaptive and non-adaptive policies. We prove an $Ω(\log\log B)^{1/2}$ lower bound on the adaptivity gap of stochastic orienteering. This provides a negative answer to the $O(1)$ adaptivity gap conjectured earlier, and comes close to the $O(\log\log B)$ upper bound. This result holds even on a line metric. We also show an $O(\log\log B)$ upper bound on the adaptivity gap for the correlated stochastic orienteering problem, where the reward of each job is random and possibly correlated to its processing time. Using this, we obtain an improved quasi-polynomial time approximation algorithm for correlated stochastic orienteering.
A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
Venue: arXiv cs.DS 2014
Year: 2014

We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time \frac{9}{7}-approximation algorithm for cubic bipartite graphs and a (\frac{9}{7}+\frac{1}{21(k-2)})-approximation algorithm for k-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.
Deciding first-order properties of nowhere dense graphs
Venue: arXiv cs.LO 2014
Year: 2014

Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes. At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighbourhood covers for nowhere dense graphs. This extends and improves previous constructions of neighbourhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterisation of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a "rank-preserving" version of Gaifman's locality theorem.
Local computation mechanism design
Venue: arXiv cs.GT 2014
Year: 2014

We introduce the notion of Local Computation Mechanism Design - designing game theoretic mechanisms which run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. In addition, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanisms need to maintain incentive compatibility with respect to the allocation and payments. We present local computation mechanisms for a variety of classical game-theoretical problems: 1. stable matching, 2. job scheduling, 3. combinatorial auctions for unit-demand and k-minded bidders, and 4. the housing allocation problem. For stable matching, some of our techniques may have general implications. Specifically, we show that when the men's preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.