OpenRaiser/Intern-Atlas huggingface dataset:
Necklaces, Convolutions, and X+Y
Venue: arXiv cs.DS 2012
Year: 2012

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = \infty. For p even, we reduce the problem to standard convolution, while for p = \infty and p = 1, we reduce the problem to (min, +) convolution and (median, +) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X + Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X + Y matrix. All of our algorithms run in o(n^2) time, whereas the obvious algorithms for these problems run in Θ(n^2) time.
A Practical Algorithm for Topic Modeling with Provable Guarantees
Venue: arXiv cs.LG 2012
Year: 2012

Topic models provide a useful method for dimensionality reduction and exploratory data analysis in large text corpora. Most approaches to topic model inference have been based on a maximum likelihood objective. Efficient algorithms exist that approximate this objective, but they have no provable guarantees. Recently, algorithms have been introduced that provide provable bounds, but these algorithms are not practical because they are inefficient and not robust to violations of model assumptions. In this paper we present an algorithm for topic model inference that is both provable and practical. The algorithm produces results comparable to the best MCMC implementations while running orders of magnitude faster.
Can P2P Technology Benefit Eyeball ISPs? A Cooperative Profit Distribution Answer
Venue: arXiv cs.NI 2012
Year: 2012

Peer-to-Peer (P2P) technology has been regarded as a promising way to help Content Providers (CPs) cost-effectively distribute content. However, under the traditional Internet pricing mechanism, the fact that most P2P traffic flows among peers can dramatically decrease the profit of ISPs, who may take actions against P2P and impede the progress of P2P technology. In this paper, we develop a mathematical framework to analyze such economic issues. Inspired by the idea from cooperative game theory, we propose a cooperative profit-distribution model based on Nash Bargaining Solution (NBS), in which eyeball ISPs and Peer-assisted CPs (PCPs) form two coalitions respectively and then compute a fair Pareto point to determine profit distribution. Moreover, we design a fair and feasible mechanism for profit distribution within each coalition. We show that such a cooperative method not only guarantees the fair profit distribution among network participators, but also helps to improve the economic efficiency of the overall network system. To our knowledge, this is the first work that systematically studies solutions for P2P caused unbalanced profit distribution and gives a feasible cooperative method to increase and fairly share profit.
Binary Sequences with Minimum Peak Sidelobe Level up to Length 68
Venue: arXiv cs.OH 2012
Year: 2012

Results of an exhaustive search for minimum peak sidelobe level binary sequences are presented. Several techniques for efficiency implementation of search algorithm are described. A table of number of non-equivalent optimal binary sequences with minimum peak sidelobe (MPS) level up to length 68 is given. This number can be used in prediction of the longest length for a given sidelobe level of binary sequences. The examples of optimal binary MPS sequences having high merit factor are shown.
A Physical Layer Secured Key Distribution Technique for IEEE 802.11g Wireless Networks
Venue: arXiv cs.IT 2012
Year: 2012

Key distribution and renewing in wireless local area networks is a crucial issue to guarantee that unauthorized users are prevented from accessing the network. In this paper, we propose a technique for allowing an automatic bootstrap and periodic renewing of the network key by exploiting physical layer security principles, that is, the inherent differences among transmission channels. The proposed technique is based on scrambling of groups of consecutive packets and does not need the use of an initial authentication nor automatic repeat request protocols. We present a modification of the scrambling circuits included in the IEEE 802.11g standard which allows for a suitable error propagation at the unauthorized receiver, thus achieving physical layer security.
A General Framework for the Derivation of Regular Expressions
Venue: arXiv cs.FL 2012
Year: 2012

The aim of this paper is to design a theoretical framework that allows us to perform the computation of regular expression derivatives through a space of generic structures. Thanks to this formalism, the main properties of regular expression derivation, such as the finiteness of the set of derivatives, need only be stated and proved one time, at the top level. Moreover, it is shown how to construct an alternating automaton associated with the derivation of a regular expression in this general framework. Finally, Brzozowski's derivation and Antimirov's derivation turn out to be a particular case of this general scheme and it is shown how to construct a DFA, a NFA and an AFA for both of these derivations.
A Polynomial Time Version of LLL With Deep Insertions
Venue: arXiv cs.CR 2012
Year: 2012

Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the LLL algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the LLL algorithm was LLL with deep insertions (DeepLLL). The output of this version of LLL has higher quality in practice but the running time seems to explode. Weaker variants of DeepLLL, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper a new variant of DeepLLL with provably polynomial running time is presented. We compare the practical behavior of the new algorithm to classical LLL, BKZ as well as blockwise variants of DeepLLL regarding both the output quality and running time.
The Inverse Shapley Value Problem
Venue: arXiv cs.GT 2012
Year: 2012

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley and Martin Shubik in 1954 \cite{SS54} and are widely studied in social choice theory as a measure of the "influence" of voters. The \emph{Inverse Shapley Value Problem} is the problem of designing a weighted voting scheme which (approximately) achieves a desired input vector of values for the Shapley-Shubik indices. Despite much interest in this problem no provably correct and efficient algorithm was known prior to our work. We give the first efficient algorithm with provable performance guarantees for the Inverse Shapley Value Problem. For any constant $\eps > 0$ our algorithm runs in fixed poly$(n)$ time (the degree of the polynomial is independent of $\eps$) and has the following performance guarantee: given as input a vector of desired Shapley values, if any "reasonable" weighted voting scheme (roughly, one in which the threshold is not too skewed) approximately matches the desired vector of values to within some small error, then our algorithm explicitly outputs a weighted voting scheme that achieves this vector of Shapley values to within error $\eps.$ If there is a "reasonable" voting scheme in which all voting weights are integers at most $\poly(n)$ that approximately achieves the desired Shapley values, then our algorithm runs in time $\poly(n)$ and outputs a weighted voting scheme that achieves the target vector of Shapley values to within error $\eps=n^{-1/8}.$
Quantized Network Coding for Correlated Sources
Venue: arXiv cs.IT 2012
Year: 2012

Non-adaptive joint source network coding of correlated sources is discussed in this paper. By studying the information flow in the network, we propose quantized network coding as an alternative for packet forwarding. This technique has both network coding and distributed source coding advantages, simultaneously. Quantized network coding is a combination of random linear network coding in the (infinite) field of real numbers and quantization to cope with the limited capacity of links. With the aid of the results in the literature of compressed sensing, we discuss theoretical and practical feasibility of quantized network coding in lossless networks. We show that, due to the nature of the field it operates on, quantized network coding can provide good quality decoding at a sink node with the reception of a reduced number of packets. Specifically, we discuss the required conditions on local network coding coefficients, by using restricted isometry property and suggest a design, which yields in appropriate linear measurements. Finally, our simulation results show the achieved gain in terms of delivery delay, compared to conventional routing based packet forwarding.
A Blind Time-Reversal Detector in the Presence of Channel Correlation
Venue: arXiv cs.IT 2012
Year: 2012

A blind target detector using the time reversal transmission is proposed in the presence of channel correlation. We calculate the exact moments of the test statistics involved. The derived moments are used to construct an accurate approximative Likelihood Ratio Test (LRT) based on multivariate Edgeworth expansion. Performance gain over an existing detector is observed in scenarios with channel correlation and relatively strong target signal.
Random Spanning Trees and the Prediction of Weighted Graphs
Venue: arXiv cs.LG 2012
Year: 2012

We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world datasets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice.
High-precision camera distortion measurements with a "calibration harp"
Venue: arXiv cs.CV 2012
Year: 2012

This paper addresses the high precision measurement of the distortion of a digital camera from photographs. Traditionally, this distortion is measured from photographs of a flat pattern which contains aligned elements. Nevertheless, it is nearly impossible to fabricate a very flat pattern and to validate its flatness. This fact limits the attainable measurable precisions. In contrast, it is much easier to obtain physically very precise straight lines by tightly stretching good quality strings on a frame. Taking literally "plumb-line methods", we built a "calibration harp" instead of the classic flat patterns to obtain a high precision measurement tool, demonstrably reaching 2/100 pixel precisions. The harp is complemented with the algorithms computing automatically from harp photographs two different and complementary lens distortion measurements. The precision of the method is evaluated on images corrected by state-of-the-art distortion correction algorithms, and by popular software. Three applications are shown: first an objective and reliable measurement of the result of any distortion correction. Second, the harp permits to control state-of-the art global camera calibration algorithms: It permits to select the right distortion model, thus avoiding internal compensation errors inherent to these methods. Third, the method replaces manual procedures in other distortion correction methods, makes them fully automatic, and increases their reliability and precision.
Collaborating Robotics Using Nature-Inspired Meta-Heuristics
Venue: arXiv cs.NE 2012
Year: 2012

This paper introduces collaborating robots which provide the possibility of enhanced task performance, high reliability and decreased. Collaborating-bots are a collection of mobile robots able to self-assemble and to self-organize in order to solve problems that cannot be solved by a single robot. These robots combine the power of swarm intelligence with the flexibility of self-reconfiguration as aggregate Collaborating-bots can dynamically change their structure to match environmental variations. Collaborating robots are more than just networks of independent agents, they are potentially reconfigurable networks of communicating agents capable of coordinated sensing and interaction with the environment. Robots are going to be an important part of the future. Collaborating robots are limited in individual capability, but robots deployed in large numbers can represent a strong force similar to a colony of ants or swarm of bees. We present a mechanism for collaborating robots based on swarm intelligence such as Ant colony optimization and Particle swarm Optimization
Classical Model Predictive Control of a Permanent Magnet Synchronous Motor
Venue: arXiv cs.SY 2012
Year: 2012

A model predictive control (MPC) scheme for a permanent-magnet synchronous motor (PMSM) is presented. The torque controller optimizes a quadratic cost consisting of control error and machine losses repeatedly, accounting the voltage and current limitations. The scheme extensively relies on optimization, to meet the runtime limitation, a suboptimal algorithm based on differential flatness, continuous parameterization and linear programming is introduced. The multivariable controller exploits cross-coupling effects in the long-range constrained predictive control strategy. The optimization results in fast and smooth torque dynamics while inherently using field-weakening to improve the power efficiency and the current dynamics in high speed operation. As distinctive MPC feature, constraint handling is improved, instead of just saturating the control input, field weakening is applied dynamically to bypass the voltage limitation. The performance of the scheme is demonstrated by experimental and numerical results.
Distributed optimization of deeply nested systems
Venue: arXiv cs.LG 2012
Year: 2012

In science and engineering, intelligent processing of complex signals such as images, sound or language is often performed by a parameterized hierarchy of nonlinear processing layers, sometimes biologically inspired. Hierarchical systems (or, more generally, nested systems) offer a way to generate complex mappings using simple stages. Each layer performs a different operation and achieves an ever more sophisticated representation of the input, as, for example, in an deep artificial neural network, an object recognition cascade in computer vision or a speech front-end processing. Joint estimation of the parameters of all the layers and selection of an optimal architecture is widely considered to be a difficult numerical nonconvex optimization problem, difficult to parallelize for execution in a distributed computation environment, and requiring significant human expert effort, which leads to suboptimal systems in practice. We describe a general mathematical strategy to learn the parameters and, to some extent, the architecture of nested systems, called the method of auxiliary coordinates (MAC). This replaces the original problem involving a deeply nested function with a constrained problem involving a different function in an augmented space without nesting. The constrained problem may be solved with penalty-based methods using alternating optimization over the parameters and the auxiliary coordinates. MAC has provable convergence, is easy to implement reusing existing algorithms for single layers, can be parallelized trivially and massively, applies even when parameter derivatives are not available or not desirable, and is competitive with state-of-the-art nonlinear optimizers even in the serial computation setting, often providing reasonable models within a few iterations.
Interoperability and Standardization of Intercloud Cloud Computing
Venue: arXiv cs.DC 2012
Year: 2012

Cloud computing is getting mature, and the interoperability and standardization of the clouds is still waiting to be solved. This paper discussed the interoperability among clouds about message transmission, data transmission and virtual machine transfer. Starting from IEEE Pioneering Cloud Computing Initiative, this paper discussed about standardization of the cloud computing, especially intercloud cloud computing. This paper also discussed the standardization from the market-oriented view.
Design and Performance Study of Smart Antenna Systems for WIMAX Applications
Venue: arXiv cs.OH 2012
Year: 2012

In this paper we propose an approach that uses homodyne receivers to design smart antenna systems. The receivers functions are to detect angles of arrivals of seven incoming RF signals using MUSIC or ESPRIT algorithms. The characteristics of each algorithm are critical for the systems precision as well as receivers types. Results are deduced from the simulation of each system, using the Advanced Design System (ADS) and MATLAB. These are compared to results deduced from real systems in the WIMAX (3.5GHz) domains.
Beamforming Techniques for Multichannel audio Signal Separation
Venue: arXiv cs.OH 2012
Year: 2012

Beamforming is a signal processing technique. It has been studied in many areas such as radar, sonar, seismology and wireless communications, to name but a few. It can be used for a myriad of purposes, such as detecting the presence of a signal, estimating the direction of arrival, and enhancing a desired signal from its measurements corrupted by noise, competing sources and reverberation. Actually, Beamforming has been adopted by the audio research society, mostly to separate or extract speech for noisy environment. Beamforming techniques basically approach the problem from a spatial point of view. A microphone array is used to form a spatial filter which can extract a signal from a specific direction and reduce the contamination of signals from other directions. In this paper we survey some Beamforming techniques used for multichannel audio signal separation.
Single-sided Real-time PESQ Score Estimation
Venue: arXiv cs.SD 2012
Year: 2012

For several years now, the ITU-T's Perceptual Evaluation of Speech Quality (PESQ) has been the reference for objective speech quality assessment. It is widely deployed in commercial QoE measurement products, and it has been well studied in the literature. While PESQ does provide reasonably good correlation with subjective scores for VoIP applications, the algorithm itself is not usable in a real-time context, since it requires a reference signal, which is usually not available in normal conditions. In this paper we provide an alternative technique for estimating PESQ scores in a single-sided fashion, based on the Pseudo Subjective Quality Assessment (PSQA) technique.
On Neighborhood Tree Search
Venue: arXiv cs.OH 2012
Year: 2012

We consider the neighborhood tree induced by alternating the use of different neighborhood structures within a local search descent. We investigate the issue of designing a search strategy operating at the neighborhood tree level by exploring different paths of the tree in a heuristic way. We show that allowing the search to 'backtrack' to a previously visited solution and resuming the iterative variable neighborhood descent by 'pruning' the already explored neighborhood branches leads to the design of effective and efficient search heuristics. We describe this idea by discussing its basic design components within a generic algorithmic scheme and we propose some simple and intuitive strategies to guide the search when traversing the neighborhood tree. We conduct a thorough experimental analysis of this approach by considering two different problem domains, namely, the Total Weighted Tardiness Problem (SMTWTP), and the more sophisticated Location Routing Problem (LRP). We show that independently of the considered domain, the approach is highly competitive. In particular, we show that using different branching and backtracking strategies when exploring the neighborhood tree allows us to achieve different trade-offs in terms of solution quality and computing cost.
Identifying Research Fields within Business and Management: A Journal Cross-Citation Analysis
Venue: arXiv cs.DL 2012
Year: 2012

A discipline such as business and management (B&M) is very broad and has many fields within it, ranging from fairly scientific ones such as management science or economics to softer ones such as information systems. There are at least two reasons why it is important to identify these sub-fields accurately. Firstly, for the purpose of normalizing citation data as it is well known that citation rates vary significantly between different disciplines. Secondly, because journal rankings and lists tend to split their classifications into different subjects, for example the the Association of Business Schools (ABS) list, which is a standard in the UK, has 22 different fields. Unfortunately, at the moment these are created in an ad hoc manner with no underlying rigour. The purpose of this paper is to identify possible sub-fields in B&M rigorously based on actual citation patterns. We have examined 450 journals in B&M which are included in the ISI Web of Science (WoS) and analysed the cross-citation rates between them enabling us to generate sets of coherent and consistent sub-fields that minimise the extent to which journals appear in several categories. Implications and limitations of the analysis are discussed
Lattice Sparsification and the Approximate Closest Vector Problem
Venue: arXiv cs.DS 2012
Year: 2012

We give a deterministic algorithm for solving the (1+eps)-approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2^{O(n)}(1+1/eps)^n time and 2^n poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the "AKS Sieve" based algorithms for (1+eps)-CVP (Ajtai, Kumar, and Sivakumar; STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2^{O(n)} time algorithm for exact CVP in the l_2 norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for "sparsifying" any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003) for the purpose of proving hardness for Shortest Vector Problem (SVP) under l_p norms.