OpenRaiser/Intern-Atlas huggingface dataset:
The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach
Venue: arXiv cs.GT 2010
Year: 2010

We propose a new class of game-theoretic models for network formation in which strategies are not directly related to edge choices, but instead correspond more generally to the exertion of social effort. The observed social network is thus a byproduct of an expressive strategic interaction, which can more naturally explain the emergence of complex social structures. Within this framework, we present a natural network formation game in which agent utilities are locally defined and that, despite its simplicity, produces a rich class of equilibria that exhibit structural properties commonly observed in social networks - such as triadic closure - that have proved elusive in most existing models. Specifically, we consider a game in which players organize networking events at a cost that grows with the number of attendees. An event's cost is assumed by the organizer but the benefit accrues equally to all attendees: a link is formed between any two players who see each other at more than a certain number r of events per time period. The graph of connections so obtained is the social network of the model. We analyze the Nash equilibria of this game when each player derives a benefit a>0 from all her neighbors in the network and when the costs are linear, i.e., when the cost of an event with L invitees is b+cL, with b>0 and c>0. For a/cr > 1 and b sufficiently small, all Nash equilibria have the complete graph as their social network; for a/cr < 1 the Nash equilibria correspond to a rich class of social networks, all of which have substantial clustering in the sense that the clustering coefficient is bounded below by the inverse of the average degree. Additionally, for any degree sequence with finite mean, and not too many vertices of degree one or two, we can construct a Nash equilibrium producing a social network with the given degree sequence.
Scaling Turbo Boost to a 1000 cores
Venue: arXiv cs.PF 2010
Year: 2010

The Intel Core i7 processor code named Nehalem provides a feature named Turbo Boost which opportunistically varies the frequencies of the processor's cores. The frequency of a core is determined by core temperature, the number of active cores, the estimated power consumption, the estimated current consumption, and operating system frequency scaling requests. For a chip multi-processor(CMP) that has a small number of physical cores and a small set of performance states, deciding the Turbo Boost frequency to use on a given core might not be difficult. However, we do not know the complexity of this decision making process in the context of a large number of cores, scaling to the 100s, as predicted by researchers in the field.
Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties
Venue: arXiv cs.FL 2010
Year: 2010

The first step when forming the polynomial hierarchies of languages is to consider languages of the form KaL where K and L are over a finite alphabet A and from a given variety V of languages, a being a letter from A. All such KaL's generate the variety of languages BPol1(V). We estimate the numerical parameters of the language KaL in terms of their values for K and L. These parameters include the state complexity of the minimal complete DFA and the size of the syntactic monoids. We also estimate the cardinality of the image of A* in the Schuetzenberger product of the syntactic monoids of K and L. In these three cases we obtain the optimal bounds. Finally, we also consider estimates for the cardinalities of free monoids in the variety of monoids corresponding to BPol1(V) in terms of sizes of the free monoids in the variety of monoids corresponding to V.
The Maximal Subword Complexity of Quasiperiodic Infinite Words
Venue: arXiv cs.FL 2010
Year: 2010

We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words. To this end we give a representation of the set of finite and of infinite words having a certain quasiperiod q via a finite language derived from q. It is shown that this language is a suffix code having a bounded delay of decipherability. Our estimate of the subword complexity now follows from this result, previously known results on the subword complexity and elementary results on formal power series.
Introduction to the 26th International Conference on Logic Programming Special Issue
Venue: arXiv cs.AI 2010
Year: 2010

This is the preface to the 26th International Conference on Logic Programming Special Issue
The Cloud Adoption Toolkit: Supporting Cloud Adoption Decisions in the Enterprise
Venue: arXiv cs.DC 2010
Year: 2010

Cloud computing promises a radical shift in the provisioning of computing resource within the enterprise. This paper describes the challenges that decision makers face when assessing the feasibility of the adoption of cloud computing in their organisations, and describes our Cloud Adoption Toolkit, which has been developed to support this process. The toolkit provides a framework to support decision makers in identifying their concerns, and matching these concerns to appropriate tools/techniques that can be used to address them. Cost Modeling is the most mature tool in the toolkit, and this paper shows its effectiveness by demonstrating how practitioners can use it to examine the costs of deploying their IT systems on the cloud. The Cost Modeling tool is evaluated using a case study of an organization that is considering the migration of some of its IT systems to the cloud. The case study shows that running systems on the cloud using a traditional "always on" approach can be less cost effective, and the elastic nature of the cloud has to be used to reduce costs. Therefore, decision makers have to be able to model the variations in resource usage and their systems deployment options to obtain accurate cost estimates.
Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee. To illustrate the applicability of our paradigm, we focus our attention on the undirected sparsest cut problem with general demands and the balanced separator problem. By a simple use of our framework, we obtain poly-logarithmic approximation algorithms for these problems that run in time close to linear. The main tool behind our result is an efficient procedure that decomposes general graphs into simpler ones while approximately preserving the cut-flow structure. This decomposition is inspired by the cut-based graph decomposition of Räcke that was developed in the context of oblivious routing schemes, as well as, by the construction of the ultrasparsifiers due to Spielman and Teng that was employed to preconditioning symmetric diagonally-dominant matrices.
Flow-Cut Gaps for Integer and Fractional Multiflows
Venue: arXiv cs.DM 2010
Year: 2010

Consider a routing problem consisting of a demand graph H and a supply graph G. If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there is a feasible multiflow for H if each edge of G is given capacity C. The flow-cut gap can be greater than 1 even when G is the (series-parallel) graph K_{2,3}. In this paper we are primarily interested in the "integer" flow-cut gap. What is the minimum value C such that there is a feasible integer valued multiflow for H if each edge of G is given capacity C? We conjecture that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. This strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) to suggest that the integer flow-cut gap is O(1). We give several results on non-trivial special classes of graphs supporting this conjecture and further explore the "primal" method for understanding flow-cut gaps. Our results include: - Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. If the cut condition holds for a compliant instance and G+H is Eulerian, then an integral routing of H exists. - The integer flow-cut gap in series-parallel graphs is 5. We also give an explicit class of instances that shows via elementary calculations that the flow-cut gap in series-parallel graphs is at least 2-o(1); this simplifies the proof by Lee and Raghavendra. - The integer flow-cut gap in k-Outerplanar graphs is c^{O(k)} for some fixed constant c. - A simple proof that the flow-cut gap is O(\log k^*) where k^* is the size of a node-cover in H; this was previously shown by Günlük via a more intricate proof.
RDFViewS: A Storage Tuning Wizard for RDF Applications
Venue: arXiv cs.DB 2010
Year: 2010

In recent years, the significant growth of RDF data used in numerous applications has made its efficient and scalable manipulation an important issue. In this paper, we present RDFViewS, a system capable of choosing the most suitable views to materialize, in order to minimize the query response time for a specific SPARQL query workload, while taking into account the view maintenance cost and storage space constraints. Our system employs practical algorithms and heuristics to navigate through the search space of potential view configurations, and exploits the possibly available semantic information - expressed via an RDF Schema - to ensure the completeness of the query evaluation.
A Novel Association Policy for Web Browsing in a Multirate WLAN
Venue: arXiv cs.NI 2010
Year: 2010

We obtain an association policy for STAs in an IEEE 802.11 WLAN by taking into account explicitly two aspects of practical importance: (a) TCP-controlled short file downloads interspersed with read times (motivated by web browsing), and (b) different STAs associated with an AP at possibly different rates (depending on distance from the AP). Our approach is based on two steps. First, we consider an analytical model to obtain the aggregate AP throughput for long TCP-controlled file downloads when STAs are associated at k different rates r1, r2, : : :, rk; this extends earlier work in the literature. Second, we present a 2-node closed queueing network model to approximate the expected average-sized file download time for a user who shares the AP with other users associated at a multiplicity of rates. These analytical results motivate the proposed association policy, called the Estimated Delay based Association (EDA) policy: Associate with the AP at which the expected file download time is the least. Simulations indicate that for a web-browsing type traffic scenario, EDA outperforms other policies that have been proposed earlier; the extent of improvement ranges from 12.8% to 46.4% for a 9-AP network. To the best of our knowledge, this is the first work that proposes an association policy tailored specifically for web browsing. Apart from this, our analytical results could be of independent interest
Achievable Rates and Upper bounds for the Interference Relay Channel
Venue: arXiv cs.IT 2010
Year: 2010

The two user Gaussian interference channel with a full-duplex relay is studied. By using genie aided approaches, two new upper bounds on the achievable sum-rate in this setup are derived. These upper bounds are shown to be tighter than previously known bounds under some conditions. Moreover, a transmit strategy for this setup is proposed. This strategy utilizes the following elements: Block Markov encoding combined with a Han-Kobayashi scheme at the sources, decode and forward at the relay, and Willems' backward decoding at the receivers. This scheme is shown to achieve within a finite gap our upper bounds in certain cases.
An MGF-based Unified Framework to Determine the Joint Statistics of Partial Sums of Ordered Random Variables
Venue: arXiv cs.IT 2010
Year: 2010

Order statistics find applications in various areas of communications and signal processing. In this paper, we introduce an unified analytical framework to determine the joint statistics of partial sums of ordered random variables (RVs). With the proposed approach, we can systematically derive the joint statistics of any partial sums of ordered statistics, in terms of the moment generating function (MGF) and the probability density function (PDF). Our MGF-based approach applies not only when all the K ordered RVs are involved but also when only the Ks (Ks < K) best RVs are considered. In addition, we present the closed-form expressions for the exponential RV special case. These results apply to the performance analysis of various wireless communication systems over fading channels.
The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks
Venue: arXiv cs.CR 2010
Year: 2010

Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will someday become a reality, we would like to have \emph{post-quantum} cryptosystems which can be implemented today with classical computers, but which will remain secure even in the presence of quantum attacks. In this article we show that the McEliece cryptosystem over \emph{well-permuted, well-scrambled} linear codes resists precisely the attacks to which the RSA and El Gamal cryptosystems are vulnerable---namely, those based on generating and measuring coset states. This eliminates the approach of strong Fourier sampling on which almost all known exponential speedups by quantum algorithms are based. Specifically, we show that the natural case of the Hidden Subgroup Problem to which the McEliece cryptosystem reduces cannot be solved by strong Fourier sampling, or by any measurement of a coset state. We start with recent negative results on quantum algorithms for Graph Isomorphism, which are based on particular subgroups of size two, and extend them to subgroups of arbitrary structure, including the automorphism groups of linear codes. This allows us to obtain the first rigorous results on the security of the McEliece cryptosystem in the face of quantum adversaries, strengthening its candidacy for post-quantum cryptography.
A Survey of RFID Authentication Protocols Based on Hash-Chain Method
Venue: arXiv cs.CR 2010
Year: 2010

Security and privacy are the inherent problems in RFID communications. There are several protocols have been proposed to overcome those problems. Hash chain is commonly employed by the protocols to improve security and privacy for RFID authentication. Although the protocols able to provide specific solution for RFID security and privacy problems, they fail to provide integrated solution. This article is a survey to closely observe those protocols in terms of its focus and limitations.
Well-definedness of Streams by Transformation and Termination
Venue: arXiv cs.LO 2010
Year: 2010

Streams are infinite sequences over a given data type. A stream specification is a set of equations intended to define a stream. We propose a transformation from such a stream specification to a term rewriting system (TRS) in such a way that termination of the resulting TRS implies that the stream specification is well-defined, that is, admits a unique solution. As a consequence, proving well-definedness of several interesting stream specifications can be done fully automatically using present powerful tools for proving TRS termination. In order to increase the power of this approach, we investigate transformations that preserve semantics and well-definedness. We give examples for which the above mentioned technique applies for the ransformed specification while it fails for the original one.
Sequential Rationality in Cryptographic Protocols
Venue: arXiv cs.GT 2010
Year: 2010

Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers. We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat-free Nash equilibrium that is more permissive but still eliminates the undesirable ``empty threats'' of non-sequential solution concepts. To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria (Dodis-Halevi-Rabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a non-trivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.
Modelling the Dynamics of an Aedes albopictus Population
Venue: arXiv cs.CE 2010
Year: 2010

We present a methodology for modelling population dynamics with formal means of computer science. This allows unambiguous description of systems and application of analysis tools such as simulators and model checkers. In particular, the dynamics of a population of Aedes albopictus (a species of mosquito) and its modelling with the Stochastic Calculus of Looping Sequences (Stochastic CLS) are considered. The use of Stochastic CLS to model population dynamics requires an extension which allows environmental events (such as changes in the temperature and rainfalls) to be taken into account. A simulator for the constructed model is developed via translation into the specification language Maude, and used to compare the dynamics obtained from the model with real data.
Building Toffoli Network for Reversible Logic Synthesis Based on Swapping Bit Strings
Venue: arXiv cs.AR 2010
Year: 2010

In this paper, we have implemented and designed a sorting network for reversible logic circuits synthesis in terms of n*n Toffoli gates. The algorithm presented in this paper constructs a Toffoli Network based on swapping bit strings. Reduction rules are then applied by simple template matching and removing useless gates from the network. Random selection of bit strings and reduction of control inputs are used to minimize both the number of gates and gate width. The method produces near optimal results for up to 3-input 3-output circuits.
On weakly optimal partitions in modular networks
Venue: arXiv cs.SI 2010
Year: 2010

Modularity was introduced as a measure of goodness for the community structure induced by a partition of the set of vertices in a graph. Then, it also became an objective function used to find good partitions, with high success. Nevertheless, some works have shown a scaling limit and certain instabilities when finding communities with this criterion. Modularity has been studied proposing several formalisms, as hamiltonians in a Potts model or laplacians in spectral partitioning. In this paper we present a new probabilistic formalism to analyze modularity, and from it we derive an algorithm based on weakly optimal partitions. This algorithm obtains good quality partitions and also scales to large graphs.
Self-adaptive congestion control for multi-class intermittent connections in a communication network
Venue: arXiv cs.NI 2010
Year: 2010

A Markovian model of the evolution of intermittent connections of various classes in a communication network is established and investigated. Any connection evolves in a way which depends only on its class and the state of the network, in particular as to the route it uses among a subset of the network nodes. It can be either active (ON) when it is transmitting data along its route, or idle (OFF). The congestion of a given node is defined as a functional of the transmission rates of all ON connections going through it, and causes losses and delays to these connections. In order to control this, the ON connections self-adaptively vary their transmission rate in TCP-like fashion. The connections interact through this feedback loop. A Markovian model is provided by the states (OFF, or ON with some transmission rate) of the connections. The number of connections in each class being potentially huge, a mean-field limit result is proved with an appropriate scaling so as to reduce the dimensionality. In the limit, the evolution of the states of the connections can be represented by a non-linear system of stochastic differential equations, of dimension the number of classes. Additionally, it is shown that the corresponding stationary distribution can be expressed by the solution of a fixed-point equation of finite dimension.
Comparative Studies of 10 Programming Languages within 10 Diverse Criteria - a Team 10 COMP6411-S10 Term Report
Venue: arXiv cs.PL 2010
Year: 2010

This is a survey on the programming languages: C++, JavaScript, AspectJ, C#, Haskell, Java, PHP, Scala, Scheme, and BPEL. Our survey work involves a comparative study of these ten programming languages with respect to the following criteria: secure programming practices, web application development, web service composition, OOP-based abstractions, reflection, aspect orientation, functional programming, declarative programming, batch scripting, and UI prototyping. We study these languages in the context of the above mentioned criteria and the level of support they provide for each one of them.
On disjoint paths in acyclic planar graphs
Venue: arXiv cs.DM 2010
Year: 2010

We give an algorithm with complexity $O(f(R)^{k^2} k^3 n)$ for the integer multiflow problem on instances $(G,H,r,c)$ with $G$ an acyclic planar digraph and $r+c$ Eulerian. Here, $f$ is a polynomial function, $n = |V(G)|$, $k = |E(H)|$ and $R$ is the maximum request $\max_{h \in E(H)} r(h)$. When $k$ is fixed, this gives a polynomial algorithm for the arc-disjoint paths problem under the same hypothesis.
EVM as generic QoS trigger for heterogeneous wieless overlay network
Venue: arXiv cs.NI 2010
Year: 2010

Fourth Generation (4G) Wireless System will integrate heterogeneous wireless overlay systems i.e. interworking of WLAN/ GSM/ CDMA/ WiMAX/ LTE/ etc with guaranteed Quality of Service (QoS) and Experience (QoE).QoS(E) vary from network to network and is application sensitive. User needs an optimal mobility solution while roaming in Overlaid wireless environment i.e. user could seamlessly transfer his session/ call to a best available network bearing guaranteed Quality of Experience. And If this Seamless transfer of session is executed between two networks having different access standards then it is called Vertical Handover (VHO). Contemporary VHO decision algorithms are based on generic QoS metrics viz. SNR, bandwidth, jitter, BER and delay. In this paper, Error Vector Magnitude (EVM) is proposed to be a generic QoS trigger for VHO execution. EVM is defined as the deviation of inphase/ quadrature (I/Q) values from ideal signal states and thus provides a measure of signal quality. In 4G Interoperable environment, OFDM is the leading Modulation scheme (more prone to multi-path fading). EVM (modulation error) properly characterises the wireless link/ channel for accurate VHO decision. EVM depends on the inherent transmission impairments viz. frequency offset, phase noise, non-linear-impairment, skewness etc. for a given wireless link. Paper provides an insight to the analytical aspect of EVM & measures EVM (%) for key management subframes like association/re-association/disassociation/ probe request/response frames. EVM relation is explored for different possible NAV-Network Allocation Vectors (frame duration). Finally EVM is compared with SNR, BER and investigation concludes EVM as a promising QoS trigger for OFDM based emerging wireless standards.