OpenRaiser/Intern-Atlas huggingface dataset:
Near-Optimum Online Ad Allocation for Targeted Advertising
Venue: arXiv cs.DS 2015
Year: 2015

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(1-\frac{1}{e})$-competitive (\cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by Buchbinder et al.~\cite{buchbinder2007online}, graphs which we call $(k,d)-bounded$. In such graphs the maximal degree on the online side is at most $d$ and the minimal degree on the offline side is at least $k$. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio $1-\frac{d-1}{k+d-1}$, tending to \emph{one} as $d/k$ tends to zero. We prove this bound is tight for these algorithms. Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio $1-(1-\frac{1}{d})^k>1-\frac{1}{e^{k/d}}$, or \emph{exponentially} better loss as a function of $k/d$, and strictly better than $1-\frac{1}{e}$ whenever $k\geq d$. We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.
The Unreasonable Success of Local Search: Geometric Optimization
Venue: arXiv cs.CG 2015
Year: 2015

What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude $1/ε^c$ is an approximation scheme for the following problems in the Euclidian plane: TSP with random inputs, Steiner tree with random inputs, facility location (with worst case inputs), and bicriteria $k$-median (also with worst case inputs). The randomness assumption is necessary for TSP.
Uplink Scheduling for LTE Video Surveillance Systems
Venue: arXiv cs.NI 2015
Year: 2015

Due to the proliferation of applications for the Internet of Things, an increasing number of machine to machine (M2M) devices are being deployed. In particular, one of the M2M applications, video surveillance, has been widely discussed. Long Term Evolution (LTE), which can provide a high rate of data transmission and wide range of coverage, is a promising standard to serve as an M2M video surveillance system. In this paper, we studied a performance maximization problem in an LTE video surveillance system. Given a set of objects and a set of cameras, each camera has its own performance grade and its own coverage. The goal is to maximize the performance of the system by allocating limited resources to cameras while all objects should be monitored by the selected cameras. We propose a heuristic method to select the cameras and allocate resources to them to solve the problem. Moreover, to reduce the load of the LTE system, a dynamic adjustment method is also proposed.
Defending Tor from Network Adversaries: A Case Study of Network Path Prediction
Venue: arXiv cs.CR 2015
Year: 2015

The Tor anonymity network has been shown vulnerable to traffic analysis attacks by autonomous systems and Internet exchanges, which can observe different overlay hops belonging to the same circuit. We aim to determine whether network path prediction techniques provide an accurate picture of the threat from such adversaries, and whether they can be used to avoid this threat. We perform a measurement study by running traceroutes from Tor relays to destinations around the Internet. We use the data to evaluate the accuracy of the autonomous systems and Internet exchanges that are predicted to appear on the path using state-of-the-art path inference techniques; we also consider the impact that prediction errors have on Tor security, and whether it is possible to produce a useful overestimate that does not miss important threats. Finally, we evaluate the possibility of using these predictions to actively avoid AS and IX adversaries and the challenges this creates for the design of Tor.
Restricted Isometry Random Variables: Probability Distributions, RIC Prediction and Phase Transition Analysis for Gaussian Encoders
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we aim to generalize the notion of restricted isometry constant (RIC) in compressive sensing (CS) to restricted isometry random variable (RIV). Associated with a deterministic encoder there are two RICs, namely, the left and the right RIC. We show that these RICs can be generalized to a left RIV and a right RIV for an ensemble of random encoders. We derive the probability and the cumulative distribution functions of these RIVs for the most widely used i.i.d. Gaussian encoders. We also derive the asymptotic distributions of the RIVs and show that the distribution of the left RIV converges (in distribution) to the Weibull distribution, whereas that of the right RIV converges to the Gumbel distribution. By adopting the RIV framework, we bring to forefront that the current practice of using eigenvalues for RIC prediction can be improved. We show on the one hand that the eigenvalue-based approaches tend to overestimate the RICs. On the other hand, the RIV-based analysis yields precise estimates of the RICs. We also demonstrate that this precise estimation aids to improve the previous RIC-based phase transition analysis in CS.
Deep Representations for Iris, Face, and Fingerprint Spoofing Detection
Venue: arXiv cs.CV 2015
Year: 2015

Biometrics systems have significantly improved person identification and authentication, playing an important role in personal, national, and global security. However, these systems might be deceived (or "spoofed") and, despite the recent advances in spoofing detection, current solutions often rely on domain knowledge, specific biometric reading systems, and attack types. We assume a very limited knowledge about biometric spoofing at the sensor to derive outstanding spoofing detection systems for iris, face, and fingerprint modalities based on two deep learning approaches. The first approach consists of learning suitable convolutional network architectures for each domain, while the second approach focuses on learning the weights of the network via back-propagation. We consider nine biometric spoofing benchmarks --- each one containing real and fake samples of a given biometric modality and attack type --- and learn deep representations for each benchmark by combining and contrasting the two learning approaches. This strategy not only provides better comprehension of how these approaches interplay, but also creates systems that exceed the best known results in eight out of the nine benchmarks. The results strongly indicate that spoofing detection systems based on convolutional networks can be robust to attacks already known and possibly adapted, with little effort, to image-based attacks that are yet to come.
k-Mixing Properties of Multidimensional Cellular Automata
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the $k$-mixing property of a multidimensional cellular automaton. Suppose $F$ is a cellular automaton with the local rule $f$ defined on a $d$-dimensional convex hull $\mathcal{C}$ which is generated by an apex set $C$. Then $F$ is $k$-mixing with respect to the uniform Bernoulli measure for all positive integer $k$ if $f$ is a permutation at some apex in $C$. An algorithm called the \emph{Mixing Algorithm} is proposed to verify if a local rule $f$ is permutive at some apex in $C$. Moreover, the proposed conditions are optimal. An application of this investigation is to construct a multidimensional ergodic linear cellular automaton.
Efficient and Compact Representations of Prefix Codes
Venue: arXiv cs.DS 2015
Year: 2015

Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many applications, the storage space used to represent the prefix code itself can be an issue. In this paper we introduce and compare several techniques to store prefix codes. Let $N$ be the sequence length and $n$ be the alphabet size. Then a naive storage of an optimal prefix code uses $O(n\log n)$ bits. Our first technique shows how to use $O(n\log\log(N/n))$ bits to store the optimal prefix code. Then we introduce an approximate technique that, for any $0<ε<1/2$, takes $O(n \log \log (1 / ε))$ bits to store a prefix code with average codeword length within an additive $ε$ of the minimum. Finally, a second approximation takes, for any constant $c > 1$, $O(n^{1 / c} \log n)$ bits to store a prefix code with average codeword length at most $c$ times the minimum. In all cases, our data structures allow encoding and decoding of any symbol in $O(1)$ time. We experimentally compare our new techniques with the state of the art, showing that we achieve 6--8-fold space reductions, at the price of a slower encoding (2.5--8 times slower) and decoding (12--24 times slower). The approximations further reduce this space and improve the time significantly, up to recovering the speed of classical implementations, for a moderate penalty in the average code length. As a byproduct, we compare various heuristic, approximate, and optimal algorithms to generate length-restricted codes, showing that the optimal ones are clearly superior and practical enough to be implemented.
Memcomputing with membrane memcapacitive systems
Venue: arXiv cs.ET 2015
Year: 2015

We show theoretically that networks of membrane memcapacitive systems -- capacitors with memory made out of membrane materials -- can be used to perform a complete set of logic gates in a massively parallel way by simply changing the external input amplitudes, but not the topology of the network. This polymorphism is an important characteristic of memcomputing (computing with memories) that closely reproduces one of the main features of the brain. A practical realization of these membrane memcapacitive systems, using, e.g., graphene or other 2D materials, would be a step forward towards a solid-state realization of memcomputing with passive devices.
Transceiver designs with matrix-version water-filling architecture under mixed power constraints
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the multiple-input multiple-output (MIMO) transceiver design under an interesting power model named mixed power constraints. In the considered power model, several antenna subsets are constrained by sum power constraints while the other antennas are subject to per-antenna power constraints. This kind of transceiver designs includes both the transceiver designs under sum power constraint and per-antenna power constraint as its special cases. This kind of designs is of critical importance for distributed antenna systems (DASs) with heterogeneous remote radio heads (RRHs) such as cloud radio access networks (C-RANs). In our work, we try to solve the optimization problem in an analytical way instead of using some famous software packages e.g., CVX or SeDuMi. In our work, to strike tradeoffs between performance and complexity, both iterative and non-iterative solutions are proposed. Interestingly the non-iterative solution can be interpreted as a matrix version water-filling solution extended from the well-known and extensively studied vector version. Finally, simulation results demonstrate the accuracy of our theoretical results.
Parameterized Complexity of CTL: A Generalization of Courcelle's Theorem
Venue: arXiv cs.LO 2015
Year: 2015

We present an almost complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is the sum of temporal depth and structural pathwidth. The classification shows a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The only real operator fragment which is confirmed to be in FPT is the fragment containing solely AX. Also we prove a generalization of Courcelle's theorem to infinite signatures which will be used to proof the FPT-membership case.
Decentralized Convergence to Nash Equilibria in Constrained Deterministic Mean Field Control
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers decentralized control and optimization methodologies for large populations of systems, consisting of several agents with different individual behaviors, constraints and interests, and affected by the aggregate behavior of the overall population. For such large-scale systems, the theory of aggregative and mean field games has been established and successfully applied in various scientific disciplines. While the existing literature addresses the case of unconstrained agents, we formulate deterministic mean field control problems in the presence of heterogeneous convex constraints for the individual agents, for instance arising from agents with linear dynamics subject to convex state and control constraints. We propose several model-free feedback iterations to compute in a decentralized fashion a mean field Nash equilibrium in the limit of infinite population size. We apply our methods to the constrained linear quadratic deterministic mean field control problem and to the constrained mean field charging control problem for large populations of plug-in electric vehicles.
Code Construction and Decoding Algorithms for Semi-Quantitative Group Testing with Nonuniform Thresholds
Venue: arXiv cs.IT 2015
Year: 2015

We analyze a new group testing scheme, termed semi-quantitative group testing, which may be viewed as a concatenation of an adder channel and a discrete quantizer. Our focus is on non-uniform quantizers with arbitrary thresholds. For the most general semi-quantitative group testing model, we define three new families of sequences capturing the constraints on the code design imposed by the choice of the thresholds. The sequences represent extensions and generalizations of Bh and certain types of super-increasing and lexicographically ordered sequences, and they lead to code structures amenable for efficient recursive decoding. We describe the decoding methods and provide an accompanying computational complexity and performance analysis.
Boolean Computation Using Self-Sustaining Nonlinear Oscillators
Venue: arXiv cs.ET 2015
Year: 2015

Self-sustaining nonlinear oscillators of practically any type can function as latches and registers if Boolean logic states are represented physically as the phase of oscillatory signals. Combinational operations on such phase-encoded logic signals can be implemented using arithmetic negation and addition followed by amplitude limiting. With these, general-purpose Boolean computation using a wide variety of natural and engineered oscillators becomes potentially possible. Such phase-encoded logic shows promise for energy efficient computing. It also has inherent noise immunity advantages over traditional level-based logic.
Comparing CSI and PCA in Amalgamation with JPEG for Spectral Image Compression
Venue: arXiv cs.MM 2015
Year: 2015

Continuing our previous research on color image compression, we move towards spectral image compression. This enormous amount of data needs more space to store and more time to transmit. To manage this sheer amount of data, researchers have investigated different techniques so that image quality can be conserved and compressibility can be improved. The principle component analysis (PCA) can be employed to reduce the dimensions of spectral images to achieve high compressibility and performance. Due to processing complexity of PCA, a simple interpolation technique called cubic spline interpolation (CSI) was considered to reduce the dimensionality of spectral domain of spectral images. The CSI and PCA were employed one by one in the spectral domain and were amalgamated with the JPEG, which was employed in spatial domain. Three measures including compression rate (CR), processing time (Tp) and color difference CIEDE2000 were used for performance analysis. Test results showed that for a fixed value of compression rate, CSI based algorithm performed poor in terms of dE00, in comparison with PCA, but is still reliable because of small color difference. On the other hand it has lower complexity and is computationally much better as compared to PCA based algorithm, especially for spectral images with large size.
Distributed Methods for High-dimensional and Large-scale Tensor Factorization
Venue: arXiv cs.NA 2015
Year: 2015

Given a high-dimensional large-scale tensor, how can we decompose it into latent factors? Can we process it on commodity computers with limited memory? These questions are closely related to recommender systems, which have modeled rating data not as a matrix but as a tensor to utilize contextual information such as time and location. This increase in the dimension requires tensor factorization methods scalable with both the dimension and size of a tensor. In this paper, we propose two distributed tensor factorization methods, SALS and CDTF. Both methods are scalable with all aspects of data, and they show an interesting trade-off between convergence speed and memory requirements. SALS updates a subset of the columns of a factor matrix at a time, and CDTF, a special case of SALS, updates one column at a time. In our experiments, only our methods factorize a 5-dimensional tensor with 1 billion observable entries, 10M mode length, and 1K rank, while all other state-of-the-art methods fail. Moreover, our methods require several orders of magnitude less memory than our competitors. We implement our methods on MapReduce with two widely-applicable optimization techniques: local disk caching and greedy row assignment. They speed up our methods up to 98.2X and also the competitors up to 5.9X.
Building pattern recognition applications with the SPARE library
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents the SPARE C++ library, an open source software tool conceived to build pattern recognition and soft computing systems. The library follows the requirement of the generality: most of the implemented algorithms are able to process user-defined input data types transparently, such as labeled graphs and sequences of objects, as well as standard numeric vectors. Here we present a high-level picture of the SPARE library characteristics, focusing instead on the specific practical possibility of constructing pattern recognition systems for different input data types. In particular, as a proof of concept, we discuss two application instances involving clustering of real-valued multidimensional sequences and classification of labeled graphs.
Classes of Delay-Independent Multimessage Multicast Networks with Zero-Delay Nodes
Venue: arXiv cs.IT 2015
Year: 2015

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. Under the classical model, every node in the network incurs a delay. In this paper, we investigate the multimessage multicast network (MMN) under a generalized-delay model which allows some nodes to incur no delay. We obtain the capacity regions for three classes of MMNs with zero-delay nodes, namely the deterministic network dominated by product distribution, the MMN consisting of independent DMCs and the wireless erasure network. In addition, we show that for any MMN belonging to one of the above three classes, the set of achievable rate tuples under the generalized-delay model and under the classical model are the same, which implies that the set of achievable rate tuples for the MMN does not depend on the delay amounts incurred by the nodes in the network.
Remote sensing image classification exploiting multiple kernel learning
Venue: arXiv cs.CV 2015
Year: 2015

We propose a strategy for land use classification which exploits Multiple Kernel Learning (MKL) to automatically determine a suitable combination of a set of features without requiring any heuristic knowledge about the classification task. We present a novel procedure that allows MKL to achieve good performance in the case of small training sets. Experimental results on publicly available datasets demonstrate the feasibility of the proposed approach.
Type Targeted Testing
Venue: arXiv cs.PL 2015
Year: 2015

We present a new technique called type targeted testing, which translates precise refinement types into comprehensive test-suites. The key insight behind our approach is that through the lens of SMT solvers, refinement types can also be viewed as a high-level, declarative, test generation technique, wherein types are converted to SMT queries whose models can be decoded into concrete program inputs. Our approach enables the systematic and exhaustive testing of implementations from high-level declarative specifications, and furthermore, provides a gradual path from testing to full verification. We have implemented our approach as a Haskell testing tool called TARGET, and present an evaluation that shows how TARGET can be used to test a wide variety of properties and how it compares against state-of-the-art testing approaches.
Pushing the envelope of Optimization Modulo Theories with Linear-Arithmetic Cost Functions
Venue: arXiv cs.LO 2015
Year: 2015

In the last decade we have witnessed an impressive progress in the expressiveness and efficiency of Satisfiability Modulo Theories (SMT) solving techniques. This has brought previously-intractable problems at the reach of state-of-the-art SMT solvers, in particular in the domain of SW and HW verification. Many SMT-encodable problems of interest, however, require also the capability of finding models that are optimal wrt. some cost functions. In previous work, namely "Optimization Modulo Theory with Linear Rational Cost Functions -- OMT(LAR U T )", we have leveraged SMT solving to handle the minimization of cost functions on linear arithmetic over the rationals, by means of a combination of SMT and LP minimization techniques. In this paper we push the envelope of our OMT approach along three directions: first, we extend it to work also with linear arithmetic on the mixed integer/rational domain, by means of a combination of SMT, LP and ILP minimization techniques; second, we develop a multi-objective version of OMT, so that to handle many cost functions simultaneously; third, we develop an incremental version of OMT, so that to exploit the incrementality of some OMT-encodable problems. An empirical evaluation performed on OMT-encoded verification problems demonstrates the usefulness and efficiency of these extensions.