OpenRaiser/Intern-Atlas huggingface dataset:
The Supermarket Game
Venue: arXiv cs.IT 2012
Year: 2012

A supermarket game is considered with $N$ FCFS queues with unit exponential service rate and global Poisson arrival rate $N λ$. Upon arrival each customer chooses a number of queues to be sampled uniformly at random and joins the least loaded sampled queue. Customers are assumed to have cost for both waiting and sampling, and they want to minimize their own expected total cost. We study the supermarket game in a mean field model that corresponds to the limit as $N$ converges to infinity in the sense that (i) for a fixed symmetric customer strategy, the joint equilibrium distribution of any fixed number of queues converges as $N \to \infty$ to a product distribution determined by the mean field model and (ii) a Nash equilibrium for the mean field model is an $ε$-Nash equilibrium for the finite $N$ model with $N$ sufficiently large. It is shown that there always exists a Nash equilibrium for $λ<1$ and the Nash equilibrium is unique with homogeneous waiting cost for $λ^2 \le 1/2$. Furthermore, we find that the action of sampling more queues by some customers has a positive externality on the other customers in the mean field model, but can have a negative externality for finite $N$.
Caracterização de tempos de ida-e-volta na Internet
Venue: arXiv cs.NI 2012
Year: 2012

Round-trip times (RTTs) are an important metric for the operation of many applications in the Internet. For instance, they are taken into account when choosing servers or peers in streaming systems, and they impact the operation of fault detectors and congestion control algorithms. Therefore, detailed knowledge about RTTs is important for application and protocol developers. In this work we present results on measuring RTTs between 81 PlanetLab nodes every ten seconds, for ten days. The resulting dataset has over 550 million measurements. Our analysis gives us a profile of delays in the network and identifies a Gamma distribution as the model that best fits our data. The average times observed are below 500 ms in more than 99% of the pairs, but there is significant variation, not only when we compare different pairs of hosts during the experiment, but also considering any given pair of hosts over time. By using a clustering technique, we observe that links can be divided in five distinct groups based on the distribution of RTTs over time and the losses observed, ranging from groups of near, well-connected pairs, to groups of distant hosts, with lower quality links between them.
Symbolic Protocol Analysis for Diffie-Hellman
Venue: arXiv cs.CR 2012
Year: 2012

We extend symbolic protocol analysis to apply to protocols using Diffie-Hellman operations. Diffie-Hellman operations act on a cyclic group of prime order, together with an exponentiation operator. The exponents form a finite field. This rich algebraic structure has resisted previous symbolic approaches. We work in an algebra defined by the normal forms of a rewriting theory (modulo associativity and commutativity). These normal forms allow us to define our crucial notion of indicator, a vector of integers that summarizes how many times each secret exponent appears in a message. We prove that the adversary can never construct a message with a new indicator in our adversary model. Using this invariant, we prove the main security goals achieved by several different protocols that use Diffie-Hellman operators in subtle ways. We also give a model-theoretic justification of our rewriting theory: the theory proves all equations that are uniformly true as the order of the cyclic group varies.
A security suite for wireless body area networks
Venue: arXiv cs.CR 2012
Year: 2012

Wireless Body Area Networks (WBANs) have gained a lot of research attention in recent years since they offer tremendous benefits for remote health monitoring and continuous, real-time patient care. However, as with any wireless communication, data security in WBANs is a challenging design issue. Since such networks consist of small sensors placed on the human body, they impose resource and computational restrictions, thereby making the use of sophisticated and advanced encryption algorithms infeasible. This calls for the design of algorithms with a robust key generation / management scheme, which are reasonably resource optimal. This paper presents a security suite for WBANs, comprised of IAMKeys, an independent and adaptive key management scheme for improving the security of WBANs, and KEMESIS, a key management scheme for security in inter-sensor communication. The novelty of these schemes lies in the use of a randomly generated key for encrypting each data frame that is generated independently at both the sender and the receiver, eliminating the need for any key exchange. The simplicity of the encryption scheme, combined with the adaptability in key management makes the schemes simple, yet secure. The proposed algorithms are validated by performance analysis.
Hierarchies of Local-Optimality Characterizations in Decoding of Tanner Codes
Venue: arXiv cs.IT 2012
Year: 2012

Recent developments in decoding of Tanner codes with maximum-likelihood certificates are based on a sufficient condition called local-optimality. We define hierarchies of locally-optimal codewords with respect to two parameters. One parameter is related to the minimum distance of the local codes in Tanner codes. The second parameter is related to the finite number of iterations used in iterative decoding. We show that these hierarchies satisfy inclusion properties as these parameters are increased. In particular, this implies that a codeword that is decoded with a certificate using an iterative decoder after $h$ iterations is decoded with a certificate after $k\cdot h$ iterations, for every integer $k$.
A visual programming language for drawing and executing flowcharts
Venue: arXiv cs.PL 2012
Year: 2012

With recent advances in graphical user interfaces, more and more tasks on computers have become easier to perform. Out of the belief that creating computer programs can also be one of them, visual programming languages (VPLs) have emerged. The goal of VPLs is to shift a part of work from the programmer to the IDE so that the programmer can focus more on algorithm logic than the syntax of the implementation programming language. In this article, the methods required to build a VPL are presented, with an emphasis on a novel method of code generation in a WHILE language. Also, the methods for achieving basic principles of VPLs will be shown - suitable visual presentation of information and guiding the programmer in the right direction using constraints. These methods are demonstrated on an example of vIDE, a VPL based on the Eclipse integrated development environment (IDE). The design of vIDE with respect to the Eclipse Graphical Modeling Framework (GMF) is described. The concept of a flowchart graphical notation is examined in contrast with the algorithm model it maps to. Finally, the disambiguity of the model representation of an algorithm is discussed and the methods for transforming it to an actual implementation in a programming language.
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning
Venue: arXiv cs.LO 2012
Year: 2012

We prove that the graph tautology principles of Alekhnovich, Johannsen, Pitassi and Urquhart have polynomial size pool resolution refutations that use only input lemmas as learned clauses and without degenerate resolution inferences. We also prove that these graph tautology principles can be refuted by polynomial size DPLL proofs with clause learning, even when restricted to greedy, unit-propagating DPLL search.
Getting It All from the Crowd
Venue: arXiv cs.DB 2012
Year: 2012

Hybrid human/computer systems promise to greatly expand the usefulness of query processing by incorporating the crowd for data gathering and other tasks. Such systems raise many database system implementation questions. Perhaps most fundamental is that the closed world assumption underlying relational query semantics does not hold in such systems. As a consequence the meaning of even simple queries can be called into question. Furthermore query progress monitoring becomes difficult due to non-uniformities in the arrival of crowdsourced data and peculiarities of how people work in crowdsourcing systems. To address these issues, we develop statistical tools that enable users and systems developers to reason about tradeoffs between time/cost and completeness. These tools can also help drive query execution and crowdsourcing strategies. We evaluate our techniques using experiments on a popular crowdsourcing platform.
A High Order Sliding Mode Control with PID Sliding Surface: Simulation on a Torpedo
Venue: arXiv cs.SY 2012
Year: 2012

Position and speed control of the torpedo present a real problem for the actuators because of the high level of the system non linearity and because of the external disturbances. The non linear systems control is based on several different approaches, among it the sliding mode control. The sliding mode control has proved its effectiveness through the different studies. The advantage that makes such an important approach is its robustness versus the disturbances and the model uncertainties. However, this approach implies a disadvantage which is the chattering phenomenon caused by the discontinuous part of this control and which can have a harmful effect on the actuators. This paper deals with the basic concepts, mathematics, and design aspects of a control for nonlinear systems that make the chattering effect lower. As solution to this problem we will adopt as a starting point the high order sliding mode approaches then the PID sliding surface. Simulation results show that this control strategy can attain excellent control performance with no chattering problem.
Self-healing systems and virtual structures
Venue: arXiv cs.DC 2012
Year: 2012

Modern networks are large, highly complex and dynamic. Add to that the mobility of the agents comprising many of these networks. It is difficult or even impossible for such systems to be managed centrally in an efficient manner. It is imperative for such systems to attain a degree of self-management. Self-healing i.e. the capability of a system in a good state to recover to another good state in face of an attack, is desirable for such systems. In this paper, we discuss the self-healing model for dynamic reconfigurable systems. In this model, an omniscient adversary inserts or deletes nodes from a network and the algorithm responds by adding a limited number of edges in order to maintain invariants of the network. We look at some of the results in this model and argue for their applicability and further extensions of the results and the model. We also look at some of the techniques we have used in our earlier work, in particular, we look at the idea of maintaining virtual graphs mapped over the existing network and assert that this may be a useful technique to use in many problem domains.
Seamless Long Term Learning in Agile Teams for Sustainable Leadership
Venue: arXiv cs.SE 2012
Year: 2012

Seamless and continuous support for long term organizational learning needs is essential for long lasting progress of the organization. Agile process model provides an excellent opportunity to cater that specific problem and also helps in motivation, satisfaction, coordination, presentation and technical skills enhancement of agile teams. This long term learning process makes organization to sustain their current successes and lead both organization and team members to successful and dynamic market leaders.
On the Diversity Gain Region of the Z-interference Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this work, we analyze the diversity gain region (DGR) of the single-antenna Rayleigh fading Z-Interference channel (ZIC). More specifically, we characterize the achievable DGR of the fixed-power split Han-Kobayashi (HK) approach under these assumptions. Our characterization comes in a closed form and demonstrates that the HK scheme with only a common message is a singular case, which achieves the best DGR among all HK schemes for certain multiplexing gains. Finally, we show that generalized time sharing, with variable rate and power assignments for the common and private messages, does not improve the achievable DGR.
Mobile Advertisement in Vehicular Ad-Hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

Mobile Advertisement is a location-aware dissemination solution built on top of a vehicular ad-hoc network. We envision a network of WiFi access points that dynamically disseminate data to clients running on the car's smart device. The approach can be considered an alternative to the static advertisement billboards and can be useful to business companies wanting to dynamically advertise their products and offers to people driving their car. The clients can subscribe to information based on specific topics. We present design solutions that use access points as emitters for transmitting messages to wireless-enabled devices equipped on vehicles. We also present implementation details for the evaluation of the proposed solution using a simulator designed for VANET application. The results show that the application can be used for transferring a significant amount of data even under difficult conditions, such as when cars are moving at increased speeds, or the congested Wi-Fi network causes significant packet loss.
New Results on the Sum of Gamma Random Variates With Application to the Performance of Wireless Communication Systems over Nakagami-m Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

The probability density function (PDF) and cumulative distribution function of the sum of L independent but not necessarily identically distributed Gamma variates, applicable to the output statistics of maximal ratio combining (MRC) receiver operating over Nakagami-m fading channels or in other words to the statistical analysis of the scenario where the sum of squared Nakagami-m distributions are user-of-interest, is presented in closed-form in terms of well-known Meijer's G function and easily computable Fox's H-bar function for integer valued and non-integer valued m fading parameters. Further analysis, particularly on bit error rate via a PDF-based approach is also offered in closed form in terms of Meijer's G function and Fox's H-bar function for integer valued fading parameters, and extended Fox's H-bar function (H-hat) for non-integer valued fading parameters. Our proposed results complement previous known results that are either expressed in terms of infinite sums, nested sums, or higher order derivatives of the fading parameter m.
On Davis-Putnam reductions for minimally unsatisfiable clause-sets
Venue: arXiv cs.DM 2012
Year: 2012

For investigations into the structure of MU, i.e., minimally unsatisfiable clause-sets or conjunctive normal forms, singular DP-reduction is a fundamental tool, applying DP-reduction F -> DP_v(F) in case variable v occurs in one polarity only once. Recall, in general DP_v(F) replaces all clauses containing variable v by their resolvents on v (another name is "variable elimination"). We consider sDP(F), the set of all results of applying singular DP-reduction to F in MU as long as possible, obtaining non-singular F' in MU with the same deficiency, i.e., delta(F') = delta(F). (In general, delta(F) is the difference c(F) - n(F) of the number of clauses and the number of variables.) Our main results are: 1. For all F', F" in sDP(F) we have n(F') = n(F"). 2. If F is saturated (F in SMU), then we have |sDP(F)| = 1. 3. If F is "eventually saturated", that is, sDP(F) <= SMU, then for F', F" in sDP(F) we have F' isomorphic F" (establishing "confluence modulo isomorphism"). The results are obtained by a detailed analysis of singular DP-reduction for F in MU. As an application we obtain that singular DP-reduction for F in MU(2) (i.e., delta(F) = 2) is confluent modulo isomorphism (using the fundamental characterisation of MU(2) by Kleine Buening). The background for these considerations is the general project of the classification of MU in terms of the deficiency.
Craniofacial reconstruction as a prediction problem using a Latent Root Regression model
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we present a computer-assisted method for facial reconstruction. This method provides an estimation of the facial shape associated with unidentified skeletal remains. Current computer-assisted methods using a statistical framework rely on a common set of extracted points located on the bone and soft-tissue surfaces. Most of the facial reconstruction methods then consist of predicting the position of the soft-tissue surface points, when the positions of the bone surface points are known. We propose to use Latent Root Regression for prediction. The results obtained are then compared to those given by Principal Components Analysis linear models. In conjunction, we have evaluated the influence of the number of skull landmarks used. Anatomical skull landmarks are completed iteratively by points located upon geodesics which link these anatomical landmarks, thus enabling us to artificially increase the number of skull points. Facial points are obtained using a mesh-matching algorithm between a common reference mesh and individual soft-tissue surface meshes. The proposed method is validated in term of accuracy, based on a leave-one-out cross-validation test applied to a homogeneous database. Accuracy measures are obtained by computing the distance between the original face surface and its reconstruction. Finally, these results are discussed referring to current computer-assisted reconstruction facial techniques.
Beyond the Bethe Free Energy of LDPC Codes via Polymer Expansions
Venue: arXiv cs.IT 2012
Year: 2012

The loop series provides a formal way to write down corrections to the Bethe entropy (and/or free energy) of graphical models. We provide methods to rigorously control such expansions for low-density parity-check codes used over a highly noisy binary symmetric channel. We prove that in the asymptotic limit of large size, with high probability, the Bethe expression gives an exact formula for the entropy (per bit) of the input word conditioned on the output of the channel. Our methods also apply to more general models.
The Computational Complexity of Truthfulness in Combinatorial Auctions
Venue: arXiv cs.GT 2012
Year: 2012

One of the fundamental questions of Algorithmic Mechanism Design is whether there exists an inherent clash between truthfulness and computational tractability: in particular, whether polynomial-time truthful mechanisms for combinatorial auctions are provably weaker in terms of approximation ratio than non-truthful ones. This question was very recently answered for universally truthful mechanisms for combinatorial auctions \cite{D11}, and even for truthful-in-expectation mechanisms \cite{DughmiV11}. However, both of these results are based on information-theoretic arguments for valuations given by a value oracle, and leave open the possibility of polynomial-time truthful mechanisms for succinctly described classes of valuations. This paper is the first to prove {\em computational hardness} results for truthful mechanisms for combinatorial auctions with succinctly described valuations. We prove that there is a class of succinctly represented submodular valuations for which no deterministic truthful mechanism provides an $m^{1/2-ε}$-approximation for a constant $ε>0$, unless $NP=RP$ ($m$ denotes the number of items). Furthermore, we prove that even truthful-in-expectation mechanisms cannot approximate combinatorial auctions with certain succinctly described submodular valuations better than within $n^γ$, where $n$ is the number of bidders and $γ>0$ some absolute constant, unless $NP \subseteq P/poly$. In addition, we prove computational hardness results for two related problems.
On Approximating String Selection Problems with Outliers
Venue: arXiv cs.DS 2012
Year: 2012

Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most Strings problem is, given a set S of same-length strings, and a parameter d, find a string x that maximizes the number of "non-outliers" within Hamming distance d of x. We prove this problem has no PTAS unless ZPP=NP, correcting a decade-old mistake. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no EPTAS unless W[1]=FPT. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult.
Uplink Performance Analysis of Multicell MU-MIMO Systems with ZF Receivers
Venue: arXiv cs.IT 2012
Year: 2012

We consider the uplink of a multicell multiuser multiple-input multiple-output system where the channel experiences both small and large-scale fading. The data detection is done by using the linear zero-forcing technique, assuming the base station (BS) has perfect channel state information. We derive new, exact closed-form expressions for the uplink rate, symbol error rate, and outage probability per user, as well as a lower bound on the achievable rate. This bound is very tight and becomes exact in the large-number-of-antennas limit. We further study the asymptotic system performance in the regimes of high signal-to-noise ratio (SNR), large number of antennas, and large number of users per cell. We show that at high SNRs, the system is interference-limited and hence, we cannot improve the system performance by increasing the transmit power of each user. Instead, by increasing the number of BS antennas, the effects of interference and noise can be reduced, thereby improving the system performance. We demonstrate that, with very large antenna arrays at the BS, the transmit power of each user can be made inversely proportional to the number of BS antennas while maintaining a desired quality-of-service. Numerical results are presented to verify our analysis.
Semi-Quantitative Group Testing
Venue: arXiv cs.IT 2012
Year: 2012

We consider a novel group testing procedure, termed semi-quantitative group testing, motivated by a class of problems arising in genome sequence processing. Semi-quantitative group testing (SQGT) is a non-binary pooling scheme that may be viewed as a combination of an adder model followed by a quantizer. For the new testing scheme we define the capacity and evaluate the capacity for some special choices of parameters using information theoretic methods. We also define a new class of disjunct codes suitable for SQGT, termed SQ-disjunct codes. We also provide both explicit and probabilistic code construction methods for SQGT with simple decoding algorithms.