OpenRaiser/Intern-Atlas huggingface dataset:
A Round-based Pricing Scheme for Maximizing Service Provider's Revenue in P2PTV Networks
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, we analyze a round-based pricing scheme that encourages favorable behavior from users of real-time P2P applications like P2PTV. In the design of pricing schemes, we consider price to be a function of usage and capacity of download/upload streams, and quality of content served. Users are consumers and servers at the same time in such networks, and often exhibit behavior that is unfavorable towards maximization of social benefits. Traditionally, network designers have overcome this difficulty by building-in traffic latencies. However, using simulations, we show that appropriate pricing schemes and usage terms can enable designers to limit required traffic latencies, and be able to earn nearly 30% extra revenue from providing P2PTV services. The service provider adjusts the prices of individual programs incrementally within rounds, while making relatively large-scale adjustments at the end of each round. Through simulations, we show that it is most beneficial for the service provider to carry out 5 such rounds of price adjustments for maximizing his average profit and minimizing the associated standard deviation at the same time.
Performance Analysis of Two-Hop Cooperative MIMO transmission with Relay Selection in Rayleigh Fading Channel
Venue: arXiv cs.NI 2009
Year: 2009

Wireless relaying is one of the promising solutions to overcome the channel impairments and provide high data rate coverage that appears for beyond 3G mobile communications. In this paper we present an end to end BER performance analysis of dual hop wireless communication systems equipped with multiple decode and forward relays over the Rayleigh fading channel with relay selection. We select the best relay based on end to end channel conditions. We apply orthogonal space time block coding (OSTBC) at source, and also present how the multiple antennas at the source terminal affects the end to end BER performance. This intermediate relay technique will cover long distance where destination is out of reach from source.
New Bounds for Restricted Isometry Constants
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we show that if the restricted isometry constant $δ_k$ of the compressed sensing matrix satisfies \[ δ_k < 0.307, \] then $k$-sparse signals are guaranteed to be recovered exactly via $\ell_1$ minimization when no noise is present and $k$-sparse signals can be estimated stably in the noisy case. It is also shown that the bound cannot be substantively improved. An explicitly example is constructed in which $δ_{k}=\frac{k-1}{2k-1} < 0.5$, but it is impossible to recover certain $k$-sparse signals.
Manipulating Tournaments in Cup and Round Robin Competitions
Venue: arXiv cs.AI 2009
Year: 2009

In sports competitions, teams can manipulate the result by, for instance, throwing games. We show that we can decide how to manipulate round robin and cup competitions, two of the most popular types of sporting competitions in polynomial time. In addition, we show that finding the minimal number of games that need to be thrown to manipulate the result can also be determined in polynomial time. Finally, we show that there are several different variations of standard cup competitions where manipulation remains polynomial.
Graph isomorphism and volumes of convex bodies
Venue: arXiv cs.CC 2009
Year: 2009

We show that a nontrivial graph isomorphism problem of two undirected graphs, and more generally, the permutation similarity of two given $n\times n$ matrices, is equivalent to equalities of volumes of the induced three convex bounded polytopes intersected with a given sequence of balls, centered at the origin with radii $t_i\in (0,\sqrt{n-1})$, where $\{t_i\}$ is an increasing sequence converging to $\sqrt{n-1}$. These polytopes are characterized by $n^2$ inequalities in at most $n^2$ variables. The existence of fpras for computing volumes of convex bodies gives rise to a semi-frpas of order $O^*(n^{14})$ at most to find if given two undirected graphs are isomorphic.
Characteristic Formulae for Fixed-Point Semantics: A General Framework
Venue: arXiv cs.LO 2009
Year: 2009

The literature on concurrency theory offers a wealth of examples of characteristic-formula constructions for various behavioural relations over finite labelled transition systems and Kripke structures that are defined in terms of fixed points of suitable functions. Such constructions and their proofs of correctness have been developed independently, but have a common underlying structure. This study provides a general view of characteristic formulae that are expressed in terms of logics with a facility for the recursive definition of formulae. It is shown how several examples of characteristic-formula constructions from the literature can be recovered as instances of the proposed general framework, and how the framework can be used to yield novel constructions.
A note on conjugacy search and racks
Venue: arXiv cs.CR 2009
Year: 2009

We show that for every effective left conjugacy closed left quasigroup, there is an induced rack that retains the conjugation structure of the left translations. This means that cryptographic protocols relying on conjugacy search can be secure only if conjugacy search of left translations is infeasible in the induced rack. We note that, in fact, protocols based on conjugacy search could be simply implemented using a rack. We give an exposition of the Anshel-Anshel-Goldfeld protocol in such a case.
Almost Linear Büchi Automata
Venue: arXiv cs.FL 2009
Year: 2009

We introduce a new fragment of Linear temporal logic (LTL) called LIO and a new class of Buechi automata (BA) called Almost linear Buechi automata (ALBA). We provide effective translations between LIO and ALBA showing that the two formalisms are expressively equivalent. While standard translations of LTL into BA use some intermediate formalisms, the presented translation of LIO into ALBA is direct. As we expect applications of ALBA in model checking, we compare the expressiveness of ALBA with other classes of Buechi automata studied in this context and we indicate possible applications.
Feeds as Query Result Serializations
Venue: arXiv cs.NI 2009
Year: 2009

Many Web-based data sources and services are available as feeds, a model that provides consumers with a loosely coupled way of interacting with providers. The current feed model is limited in its capabilities, however. Though it is simple to implement and scales well, it cannot be transferred to a wider range of application scenarios. This paper conceptualizes feeds as a way to serialize query results, describes the current hardcoded query semantics of such a perspective, and surveys the ways in which extensions of this hardcoded model have been proposed or implemented. Our generalized view of feeds as query result serializations has implications for the applicability of feeds as a generic Web service for any collection that is providing access to individual information items. As one interesting and compelling class of applications, we describe a simple way in which a query-based approach to feeds can be used to support location-based services.
Random Constraint Satisfaction Problems
Venue: arXiv cs.DM 2009
Year: 2009

Random instances of constraint satisfaction problems such as k-SAT provide challenging benchmarks. If there are m constraints over n variables there is typically a large range of densities r=m/n where solutions are known to exist with probability close to one due to non-constructive arguments. However, no algorithms are known to find solutions efficiently with a non-vanishing probability at even much lower densities. This fact appears to be related to a phase transition in the set of all solutions. The goal of this extended abstract is to provide a perspective on this phenomenon, and on the computational challenge that it poses.
An Intuitive Automated Modelling Interface for Systems Biology
Venue: arXiv cs.PL 2009
Year: 2009

We introduce a natural language interface for building stochastic pi calculus models of biological systems. In this language, complex constructs describing biochemical events are built from basic primitives of association, dissociation and transformation. This language thus allows us to model biochemical systems modularly by describing their dynamics in a narrative-style language, while making amendments, refinements and extensions on the models easy. We demonstrate the language on a model of Fc-gamma receptor phosphorylation during phagocytosis. We provide a tool implementation of the translation into a stochastic pi calculus language, Microsoft Research's SPiM.
Journals as constituents of scientific discourse: economic heterodoxy
Venue: arXiv cs.DL 2009
Year: 2009

Purpose: to provide a view and analysis of the immediate field of journals which surround a number of key heterodox economics journals. Design/methodology/approach: Using citation data from the Science and Social Science Citation Index, the individual and collective networks of a number of journals in this field are analyzed. Findings: The size and shape of the citation networks of journals can differ substantially, even if in a broadly similar category. Heterodox economics cannot (yet) be considered as an integrated specialty: authors in several journals in heterodox economics cite more from mainstream economics than from other heterodox journals. There are also strong links with other disciplinary fields such as geography, development studies, women studies, etc.
Emotion: Appraisal-coping model for the "Cascades" problem
Venue: arXiv cs.AI 2009
Year: 2009

Modelling emotion has become a challenge nowadays. Therefore, several models have been produced in order to express human emotional activity. However, only a few of them are currently able to express the close relationship existing between emotion and cognition. An appraisal-coping model is presented here, with the aim to simulate the emotional impact caused by the evaluation of a particular situation (appraisal), along with the consequent cognitive reaction intended to face the situation (coping). This model is applied to the "Cascades" problem, a small arithmetical exercise designed for ten-year-old pupils. The goal is to create a model corresponding to a child's behaviour when solving the problem using his own strategies.
Emotion : modèle d'appraisal-coping pour le problème des Cascades
Venue: arXiv cs.AI 2009
Year: 2009

Modeling emotion has become a challenge nowadays. Therefore, several models have been produced in order to express human emotional activity. However, only a few of them are currently able to express the close relationship existing between emotion and cognition. An appraisal-coping model is presented here, with the aim to simulate the emotional impact caused by the evaluation of a particular situation (appraisal), along with the consequent cognitive reaction intended to face the situation (coping). This model is applied to the ?Cascades? problem, a small arithmetical exercise designed for ten-year-old pupils. The goal is to create a model corresponding to a child's behavior when solving the problem using his own strategies.
Euclidean versus hyperbolic congestion in idealized versus experimental networks
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes a mathematical justification of the phenomenon of extreme congestion at a very limited number of nodes in very large networks. It is argued that this phenomenon occurs as a combination of the negative curvature property of the network together with minimum length routing. More specifically, it is shown that, in a large n-dimensional hyperbolic ball B of radius R viewed as a roughly similar model of a Gromov hyperbolic network, the proportion of traffic paths transiting through a small ball near the center is independent of the radius R whereas, in a Euclidean ball, the same proportion scales as 1/R^{n-1}. This discrepancy persists for the traffic load, which at the center of the hyperbolic ball scales as the square of the volume, whereas the same traffic load scales as the volume to the power (n+1)/n in the Euclidean ball. This provides a theoretical justification of the experimental exponent discrepancy observed by Narayan and Saniee between traffic loads in Gromov-hyperbolic networks from the Rocketfuel data base and synthetic Euclidean lattice networks. It is further conjectured that for networks that do not enjoy the obvious symmetry of hyperbolic and Euclidean balls, the point of maximum traffic is near the center of mass of the network.
Measuring contextual citation impact of scientific journals
Venue: arXiv cs.DL 2009
Year: 2009

This paper explores a new indicator of journal citation impact, denoted as source normalized impact per paper (SNIP). It measures a journal's contextual citation impact, taking into account characteristics of its properly defined subject field, especially the frequency at which authors cite other papers in their reference lists, the rapidity of maturing of citation impact, and the extent to which a database used for the assessment covers the field's literature. It further develops Eugene Garfield's notions of a field's 'citation potential' defined as the average length of references lists in a field and determining the probability of being cited, and the need in fair performance assessments to correct for differences between subject fields. A journal's subject field is defined as the set of papers citing that journal. SNIP is defined as the ratio of the journal's citation count per paper and the citation potential in its subject field. It aims to allow direct comparison of sources in different subject fields. Citation potential is shown to vary not only between journal subject categories - groupings of journals sharing a research field - or disciplines (e.g., journals in mathematics, engineering and social sciences tend to have lower values than titles in life sciences), but also between journals within the same subject category. For instance, basic journals tend to show higher citation potentials than applied or clinical journals, and journals covering emerging topics higher than periodicals in classical subjects or more general journals. SNIP corrects for such differences. Its strengths and limitations are critically discussed, and suggestions are made for further research. All empirical results are derived from Elsevier's Scopus.
Simulation of Pedestrians Crossing a Street
Venue: arXiv cs.MA 2009
Year: 2009

The simulation of vehicular traffic as well as pedestrian dynamics meanwhile both have a decades long history. The success of this conference series, PED and others show that the interest in these topics is still strongly increasing. This contribution deals with a combination of both systems: pedestrians crossing a street. In a VISSIM simulation for varying demand jam sizes of vehicles as well as pedestrians and the travel times of the pedestrians are measured and compared. The study is considered as a study of VISSIM's con ict area functionality as such, as there is no empirical data available to use for calibration issues. Above a vehicle demand threshold the results show a non-monotonic dependence of pedestrians' travel time on pedestrian demand.
A Recursive Definition of the Holographic Standard Signature
Venue: arXiv cs.CC 2009
Year: 2009

We provide a recursive description of the signatures realizable on the standard basis by a holographic algorithm. The description allows us to prove tight bounds on the size of planar matchgates and efficiently test for standard signatures. Over finite fields, it allows us to count the number of n-bit standard signatures and calculate their expected sparsity.
How to combine diagrammatic logics
Venue: arXiv cs.LO 2009
Year: 2009

This paper is a submission to the contest: How to combine logics? at the World Congress and School on Universal Logic III, 2010. We claim that combining "things", whatever these things are, is made easier if these things can be seen as the objects of a category. We define the category of diagrammatic logics, so that categorical constructions can be used for combining diagrammatic logics. As an example, a combination of logics using an opfibration is presented, in order to study computational side-effects due to the evolution of the state during the execution of an imperative program.
The Citation Impacts and Citation Environments of Chinese Journals in Mathematics
Venue: arXiv cs.DL 2009
Year: 2009

Based on the citation data of journals covered by the China Scientific and Technical Papers and Citations Database (CSTPCD), we obtained aggregated journal-journal citation environments by applying routines developed specifically for this purpose. Local citation impact of journals is defined as the share of the total citations in a local citation environment, which is expressed as a ratio and can be visualized by the size of the nodes. The vertical size of the nodes varies proportionally to a journal's total citation share, while the horizontal size of the nodes is used to provide citation information after correction for the within-journal (self-) citations. In this study, we analyze citation impacts of three Chinese journals in mathematics and compare local citation impacts with impact factors. Local citation impacts reflect a journal's status and function better than (global) impact factors. We also found that authors in Chinese journals prefer international instead of domestic ones as sources for their citations.
Indicators of Structural Change in the Dynamics of Science: Entropy Statistics of the SCI Journal Citation Reports
Venue: arXiv cs.DL 2009
Year: 2009

Can change in citation patterns among journals be used as an indicator of structural change in the organization of the sciences? Aggregated journal-journal citations for 1999 are compared with similar data in the Journal Citation Reports 1998 of the Science Citation Index. In addition to indicating local change, probabilistic entropy measures enable us to analyze changes in distributions at different levels of aggregation. The results of various statistics are discussed and compared by elaborating the journal-journal mappings. The relevance of this indicator for science and technology policies is further specified.
Bounding Rationality by Discounting Time
Venue: arXiv cs.GT 2009
Year: 2009

Consider a game where Alice generates an integer and Bob wins if he can factor that integer. Traditional game theory tells us that Bob will always win this game even though in practice Alice will win given our usual assumptions about the hardness of factoring. We define a new notion of bounded rationality, where the payoffs of players are discounted by the computation time they take to produce their actions. We use this notion to give a direct correspondence between the existence of equilibria where Alice has a winning strategy and the hardness of factoring. Namely, under a natural assumption on the discount rates, there is an equilibriumwhere Alice has a winning strategy iff there is a linear-time samplable distribution with respect to which Factoring is hard on average. We also give general results for discounted games over countable action spaces, including showing that any game with bounded and computable payoffs has an equilibrium in our model, even if each player is allowed a countable number of actions. It follows, for example, that the Largest Integer game has an equilibrium in our model though it has no Nash equilibria or epsilon-Nash equilibria.
Automated words stability and languages phylogeny
Venue: arXiv cs.CL 2009
Year: 2009

The idea of measuring distance between languages seems to have its roots in the work of the French explorer Dumont D'Urville (D'Urville 1832). He collected comparative words lists of various languages during his voyages aboard the Astrolabe from 1826 to1829 and, in his work about the geographical division of the Pacific, he proposed a method to measure the degree of relation among languages. The method used by modern glottochronology, developed by Morris Swadesh in the 1950s (Swadesh 1952), measures distances from the percentage of shared cognates, which are words with a common historical origin. Recently, we proposed a new automated method which uses normalized Levenshtein distance among words with the same meaning and averages on the words contained in a list. Another classical problem in glottochronology is the study of the stability of words corresponding to different meanings. Words, in fact, evolve because of lexical changes, borrowings and replacement at a rate which is not the same for all of them. The speed of lexical evolution is different for different meanings and it is probably related to the frequency of use of the associated words (Pagel et al. 2007). This problem is tackled here by an automated methodology only based on normalized Levenshtein distance.
Understanding the Principles of Recursive Neural networks: A Generative Approach to Tackle Model Complexity
Venue: arXiv cs.NE 2009
Year: 2009

Recursive Neural Networks are non-linear adaptive models that are able to learn deep structured information. However, these models have not yet been broadly accepted. This fact is mainly due to its inherent complexity. In particular, not only for being extremely complex information processing models, but also because of a computational expensive learning phase. The most popular training method for these models is back-propagation through the structure. This algorithm has been revealed not to be the most appropriate for structured processing due to problems of convergence, while more sophisticated training methods enhance the speed of convergence at the expense of increasing significantly the computational cost. In this paper, we firstly perform an analysis of the underlying principles behind these models aimed at understanding their computational power. Secondly, we propose an approximate second order stochastic learning algorithm. The proposed algorithm dynamically adapts the learning rate throughout the training phase of the network without incurring excessively expensive computational effort. The algorithm operates in both on-line and batch modes. Furthermore, the resulting learning scheme is robust against the vanishing gradients problem. The advantages of the proposed algorithm are demonstrated with a real-world application example.
Keystroke Dynamics Authentication For Collaborative Systems
Venue: arXiv cs.LG 2009
Year: 2009

We present in this paper a study on the ability and the benefits of using a keystroke dynamics authentication method for collaborative systems. Authentication is a challenging issue in order to guarantee the security of use of collaborative systems during the access control step. Many solutions exist in the state of the art such as the use of one time passwords or smart-cards. We focus in this paper on biometric based solutions that do not necessitate any additional sensor. Keystroke dynamics is an interesting solution as it uses only the keyboard and is invisible for users. Many methods have been published in this field. We make a comparative study of many of them considering the operational constraints of use for collaborative systems.
Software Engineering Education by Example
Venue: arXiv cs.SE 2009
Year: 2009

Based on the old but famous distinction between "in the small" and "in the large" software development, at Nancy Université, UHP Nancy 1, we experience for a while software engineering education thanks to actual project engineering. This education method has the merit to enable students to discover and to overcome actual problems when faced to a large project which may be conducted by a large development team. The mode of education is a simulation of an actual software engineering project as encountered in "real lifeé" activities.