OpenRaiser/Intern-Atlas huggingface dataset:
Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
Venue: arXiv cs.NI 2010
Year: 2010

Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been used to analyze and design distributed CSMA (Carrier Sense Multiple Access) scheduling algorithms for multi-hop wireless networks. In this paper we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links are allowed to update their states in parallel and the fugacity of each link can be different. The results can be used to prove that the average queue length (and hence, the delay) under the parallel Glauber dynamics based CSMA grows polynomially in the number of links for wireless networks with bounded-degree interference graphs when the arrival rate lies in a fraction of the capacity region. We also show that in specific network topologies, the low-delay capacity region can be further improved.
Skew Constacyclic Codes over Finite Chain Rings
Venue: arXiv cs.IT 2010
Year: 2010

Skew polynomial rings over finite fields ([7] and [10]) and over Galois rings ([8]) have been used to study codes. In this paper, we extend this concept to finite chain rings. Properties of skew constacyclic codes generated by monic right divisors of $x^n-λ$, where $λ$ is a unit element, are exhibited. When $λ^2=1$, the generators of Euclidean and Hermitian dual codes of such codes are determined together with necessary and sufficient conditions for them to be Euclidean and Hermitian self-dual. Of more interest are codes over the ring $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$. The structure of all skew constacyclic codes is completely determined. This allows us to express generators of Euclidean and Hermitian dual codes of skew cyclic and skew negacyclic codes in terms of the generators of the original codes. An illustration of all skew cyclic codes of length~2 over $\mathbb{F}_{3}+u\mathbb{F}_{3}$ and their Euclidean and Hermitian dual codes is also provided.
Sensitivity versus block sensitivity of Boolean functions
Venue: arXiv cs.CC 2010
Year: 2010

Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.
Evaluating and Improving Modern Variable and Revision Ordering Strategies in CSPs
Venue: arXiv cs.AI 2010
Year: 2010

A key factor that can dramatically reduce the search space during constraint solving is the criterion under which the variable to be instantiated next is selected. For this purpose numerous heuristics have been proposed. Some of the best of such heuristics exploit information about failures gathered throughout search and recorded in the form of constraint weights, while others measure the importance of variable assignments in reducing the search space. In this work we experimentally evaluate the most recent and powerful variable ordering heuristics, and new variants of them, over a wide range of benchmarks. Results demonstrate that heuristics based on failures are in general more efficient. Based on this, we then derive new revision ordering heuristics that exploit recorded failures to efficiently order the propagation list when arc consistency is maintained during search. Interestingly, in addition to reducing the number of constraint checks and list operations, these heuristics are also able to cut down the size of the explored search tree.
Blind Spectrum Sensing by Information Theoretic Criteria for Cognitive Radios
Venue: arXiv cs.IT 2010
Year: 2010

Spectrum sensing is a fundamental and critical issue for opportunistic spectrum access in cognitive radio networks. Among the many spectrum sensing methods, the information theoretic criteria (ITC) based method is a promising blind method which can reliably detect the primary users while requiring little prior information. In this paper, we provide an intensive treatment on the ITC sensing method. To this end, we first introduce a new over-determined channel model constructed by applying multiple antennas or over sampling at the secondary user in order to make the ITC applicable. Then, a simplified ITC sensing algorithm is introduced, which needs to compute and compare only two decision values. Compared with the original ITC sensing algorithm, the simplified algorithm significantly reduces the computational complexity without losing any performance. Applying the recent advances in random matrix theory, we then derive closed-form expressions to tightly approximate both the probability of false alarm and probability of detection. Based on the insight derived from the analytical study, we further present a generalized ITC sensing algorithm which can provide flexible tradeoff between the probability of detection and probability of false alarm. Finally, comprehensive simulations are carried out to evaluate the performance of the proposed ITC sensing algorithms. Results show that they considerably outperform other blind spectrum sensing methods in certain cases.
Web Video Categorization based on Wikipedia Categories and Content-Duplicated Open Resources
Venue: arXiv cs.MM 2010
Year: 2010

This paper presents a novel approach for web video categorization by leveraging Wikipedia categories (WikiCs) and open resources describing the same content as the video, i.e., content-duplicated open resources (CDORs). Note that current approaches only col-lect CDORs within one or a few media forms and ignore CDORs of other forms. We explore all these resources by utilizing WikiCs and commercial search engines. Given a web video, its discrimin-ative Wikipedia concepts are first identified and classified. Then a textual query is constructed and from which CDORs are collected. Based on these CDORs, we propose to categorize web videos in the space spanned by WikiCs rather than that spanned by raw tags. Experimental results demonstrate the effectiveness of both the proposed CDOR collection method and the WikiC voting catego-rization algorithm. In addition, the categorization model built based on both WikiCs and CDORs achieves better performance compared with the models built based on only one of them as well as state-of-the-art approach.
Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights
Venue: arXiv cs.DM 2010
Year: 2010

Let $H$ be a fixed graph and let $G$ be an $H$-minor free $n$-vertex graph with integer edge weights and no negative weight cycles reachable from a given vertex $s$. We present an algorithm that computes a shortest path tree in $G$ rooted at $s$ in $\tilde{O}(n^{4/3}\log L)$ time, where $L$ is the absolute value of the smallest edge weight. The previous best bound was $\tilde{O}(n^{\sqrt{11.5}-2}\log L) = O(n^{1.392}\log L)$. Our running time matches an earlier bound for planar graphs by Henzinger et al.
Computing with Equations
Venue: arXiv cs.PL 2010
Year: 2010

The intention of these notes is to give a mathematical account of how I believe students could be taught to think about functional programming languages and to explain how such languages work.
Classical Mathematics for a Constructive World
Venue: arXiv cs.LO 2010
Year: 2010

Interactive theorem provers based on dependent type theory have the flexibility to support both constructive and classical reasoning. Constructive reasoning is supported natively by dependent type theory and classical reasoning is typically supported by adding additional non-constructive axioms. However, there is another perspective that views constructive logic as an extension of classical logic. This paper will illustrate how classical reasoning can be supported in a practical manner inside dependent type theory without additional axioms. We will see several examples of how classical results can be applied to constructive mathematics. Finally, we will see how to extend this perspective from logic to mathematics by representing classical function spaces using a weak value monad.
Security Weakness of Flexible Group Key Exchange with On-Demand Computation of Subgroup Keys
Venue: arXiv cs.CR 2010
Year: 2010

In AFRICACRYPT 2010, Abdalla et al. first proposed a slight modification to the computations steps of the BD protocol, called mBD+P. Then they extended mBD+P protocol into mBD+S protocol. In this paper, we show that both of mBD+P and mBD+S protocols are vulnerable to malicious insiders attack. Further, we propose a simple countermeasure against this attack.
Circle Packing for Origami Design Is Hard
Venue: arXiv cs.CG 2010
Year: 2010

We show that deciding whether a given set of circles can be packed into a rectangle, an equilateral triangle, or a unit square are NP-hard problems, settling the complexity of these natural packing problems. On the positive side, we show that any set of circles of total area 1 can be packed into a square of size 4/\sqrt{pi}=2.2567... These results are motivated by problems arising in the context of origami design.
Influence and Passivity in Social Media
Venue: arXiv cs.CY 2010
Year: 2010

The ever-increasing amount of information flowing through Social Media forces the members of these networks to compete for attention and influence by relying on other people to spread their message. A large study of information propagation within Twitter reveals that the majority of users act as passive information consumers and do not forward the content to the network. Therefore, in order for individuals to become influential they must not only obtain attention and thus be popular, but also overcome user passivity. We propose an algorithm that determines the influence and passivity of users based on their information forwarding activity. An evaluation performed with a 2.5 million user dataset shows that our influence measure is a good predictor of URL clicks, outperforming several other measures that do not explicitly take user passivity into account. We also explicitly demonstrate that high popularity does not necessarily imply high influence and vice-versa.
Towards arrow-theoretic semantics of ontologies: conceptories
Venue: arXiv cs.LO 2010
Year: 2010

In context of efforts of composing category-theoretic and logical methods in the area of knowledge representation we propose the notion of conceptory. We consider intersection/union and other constructions in conceptories as expressive alternative to category-theoretic (co)limits and show they have features similar to (pro-, in-)jections. Then we briefly discuss approaches to development of formal systems built on the base of conceptories and describe possible application of such system to the specific ontology.
Contributions of PDM Systems in Organizational Technical Data Management
Venue: arXiv cs.OH 2010
Year: 2010

Product Data Management (PDM) claims of producing desktop and web based systems to maintain the organizational data to increase the quality of products by improving the process of development, business process flows, change management, product structure management, project tracking and resource planning. Moreover PDM helps in reducing the cost and effort required in engineering. This paper discusses PDM desktop and web based system, needed information and important guidelines for PDM system development, functional requirements, basic components in detail and some already implemented PDM Sys-tems. In the end paper investigates and briefly concludes major currently faced challenges to Product Data Management (PDM) community.
Statistical Trading Using Target Oriented Trading Agent
Venue: arXiv cs.GT 2010
Year: 2010

In this article we briefly present our contributions toward Trading Agent Competition (TAC); an international forum for promotion of research into the trading agent problems. Moreover, we present some strategies proposed and used in the development of our TAC Agent and resultant brief information after its participation in a real time trading environment. In the end we conclude with needed improvements and future recommendations.
PDM based I-SOAS Data Warehouse Design
Venue: arXiv cs.DB 2010
Year: 2010

This research paper briefly describes the industrial contributions of Product Data Management in any organization's technical and managerial data management. Then focusing on some current major PDM based problems i.e. Static and Unintelligent Search, Platform Independent System and Successful PDM System Implementation, briefly presents a semantic based solution i.e. I-SOAS. Majorly this research paper is about to present and discuss the contributions of I-SOAS in any organization's technical and system data management.
Matrix sparsification and the sparse null space problem
Venue: arXiv cs.CC 2010
Year: 2010

We revisit the matrix problems sparse null space and matrix sparsification, and show that they are equivalent. We then proceed to seek algorithms for these problems: We prove the hardness of approximation of these problems, and also give a powerful tool to extend algorithms and heuristics for sparse approximation theory to these problems.
GODDeS: Globally ε-Optimal Routing Via Distributed Decision-theoretic Self-organization
Venue: arXiv cs.NI 2010
Year: 2010

This paper introduces GODDeS: a fully distributed self-organizing decision-theoretic routing algorithm designed to effectively exploit high quality paths in lossy ad-hoc wireless environments, typically with a large number of nodes. The routing problem is modeled as an optimal control problem for a decentralized Markov Decision Process, with links characterized by locally known packet drop probabilities that either remain constant on average or change slowly. The equivalence of this optimization problem to that of performance maximization of an explicitly constructed probabilistic automata allows us to effectively apply the theory of quantitative measures of probabilistic regular languages, and design a distributed highly efficient solution approach that attempts to minimize source-to-sink drop probabilities across the network. Theoretical results provide rigorous guarantees on global performance, showing that the algorithm achieves near-global optimality, in polynomial time. It is also argued that GODDeS is significantly congestion-aware, and exploits multi-path routes optimally. Theoretical development is supported by high-fidelity network simulations.
L-systems in Geometric Modeling
Venue: arXiv cs.GR 2010
Year: 2010

We show that parametric context-sensitive L-systems with affine geometry interpretation provide a succinct description of some of the most fundamental algorithms of geometric modeling of curves. Examples include the Lane-Riesenfeld algorithm for generating B-splines, the de Casteljau algorithm for generating Bezier curves, and their extensions to rational curves. Our results generalize the previously reported geometric-modeling applications of L-systems, which were limited to subdivision curves.
A Parsing Scheme for Finding the Design Pattern and Reducing the Development Cost of Reusable Object Oriented Software
Venue: arXiv cs.SE 2010
Year: 2010

Because of the importance of object oriented methodologies, the research in developing new measure for object oriented system development is getting increased focus. The most of the metrics need to find the interactions between the objects and modules for developing necessary metric and an influential software measure that is attracting the software developers, designers and researchers. In this paper a new interactions are defined for object oriented system. Using these interactions, a parser is developed to analyze the existing architecture of the software. Within the design model, it is necessary for design classes to collaborate with one another. However, collaboration should be kept to an acceptable minimum i.e. better designing practice will introduce low coupling. If a design model is highly coupled, the system is difficult to implement, to test and to maintain overtime. In case of enhancing software, we need to introduce or remove module and in that case coupling is the most important factor to be considered because unnecessary coupling may make the system unstable and may cause reduction in the system's performance. So coupling is thought to be a desirable goal in software construction, leading to better values for external software qualities such as maintainability, reusability and so on. To test this hypothesis, a good measure of class coupling is needed. In this paper, based on the developed tool called Design Analyzer we propose a methodology to reuse an existing system with the objective of enhancing an existing Object oriented system keeping the coupling as low as possible.
Role of Ontology in Semantic Web Development
Venue: arXiv cs.AI 2010
Year: 2010

World Wide Web (WWW) is the most popular global information sharing and communication system consisting of three standards .i.e., Uniform Resource Identifier (URL), Hypertext Transfer Protocol (HTTP) and Hypertext Mark-up Language (HTML). Information is provided in text, image, audio and video formats over the web by using HTML which is considered to be unconventional in defining and formalizing the meaning of the context...
Scheduling with Rate Adaptation under Incomplete Knowledge of Channel/Estimator Statistics
Venue: arXiv cs.NI 2010
Year: 2010

In time-varying wireless networks, the states of the communication channels are subject to random variations, and hence need to be estimated for efficient rate adaptation and scheduling. The estimation mechanism possesses inaccuracies that need to be tackled in a probabilistic framework. In this work, we study scheduling with rate adaptation in single-hop queueing networks under two levels of channel uncertainty: when the channel estimates are inaccurate but complete knowledge of the channel/estimator joint statistics is available at the scheduler; and when the knowledge of the joint statistics is incomplete. In the former case, we characterize the network stability region and show that a maximum-weight type scheduling policy is throughput-optimal. In the latter case, we propose a joint channel statistics learning - scheduling policy. With an associated trade-off in average packet delay and convergence time, the proposed policy has a stability region arbitrarily close to the stability region of the network under full knowledge of channel/estimator joint statistics.
Design and Modeling Billing solution to Next Generation Networks
Venue: arXiv cs.NI 2010
Year: 2010

Next generation networks (NGN) services are assumed to be a new revenue stream for both network operators and service providers. New services especially focused on a mobile telecommunications that would be used not only as a communication de vice but also as a personal gateway to order or consume a variety of services and products [1]. This type of advanced services can be accomplished when the adaptability of the packet-networks (Internet) and the quality of service of the circuit switched networks are combined into one network [2]. New challenges appear in the billing of this heterogeneous multi services network. Some examples of such a services and possible solutions about charging and billing are examined in this paper. The first steps of mathematical model for billing are also considered.
On the simulation of nonlinear bidimensional spiking neuron models
Venue: arXiv cs.NA 2010
Year: 2010

Bidimensional spiking models currently gather a lot of attention for their simplicity and their ability to reproduce various spiking patterns of cortical neurons, and are particularly used for large network simulations. These models describe the dynamics of the membrane potential by a nonlinear differential equation that blows up in finite time, coupled to a second equation for adaptation. Spikes are emitted when the membrane potential blows up or reaches a cutoff value. The precise simulation of the spike times and of the adaptation variable is critical for it governs the spike pattern produced, and is hard to compute accurately because of the exploding nature of the system at the spike times. We thoroughly study the precision of fixed time-step integration schemes for this type of models and demonstrate that these methods produce systematic errors that are unbounded, as the cutoff value is increased, in the evaluation of the two crucial quantities: the spike time and the value of the adaptation variable at this time. Precise evaluation of these quantities therefore involve very small time steps and long simulation times. In order to achieve a fixed absolute precision in a reasonable computational time, we propose here a new algorithm to simulate these systems based on a variable integration step method that either integrates the original ordinary differential equation or the equation of the orbits in the phase plane, and compare this algorithm with fixed time-step Euler scheme and other more accurate simulation algorithms.
Information capacity in the weak-signal approximation
Venue: arXiv cs.IT 2010
Year: 2010

We derive an approximate expression for mutual information in a broad class of discrete-time stationary channels with continuous input, under the constraint of vanishing input amplitude or power. The approximation describes the input by its covariance matrix, while the channel properties are described by the Fisher information matrix. This separation of input and channel properties allows us to analyze the optimality conditions in a convenient way. We show that input correlations in memoryless channels do not affect channel capacity since their effect decreases fast with vanishing input amplitude or power. On the other hand, for channels with memory, properly matching the input covariances to the dependence structure of the noise may lead to almost noiseless information transfer, even for intermediate values of the noise correlations. Since many model systems described in mathematical neuroscience and biophysics operate in the high noise regime and weak-signal conditions, we believe, that the described results are of potential interest also to researchers in these areas.
Hierarchical states in the Compositional Interchange Format
Venue: arXiv cs.LO 2010
Year: 2010

CIF is a language designed for two purposes, namely as a specification language for hybrid systems and as an interchange format for allowing model transformations between other languages for hybrid systems. To facilitate the top-down development of a hybrid system and also to be able to express models more succinctly in the CIF formalism, we need a mechanism for stepwise refinement. In this paper, we add the notion of hierarchy to a subset of the CIF language, which we call hCIF. The semantic domain of the CIF formalism is a hybrid transition system, constructed using structural operational semantics. The goal of this paper is to present a semantics for hierarchy in such a way that only the SOS rules for atomic entities in hCIF are redesigned in comparison to CIF. Furthermore, to be able to reuse existing tools like simulators of the CIF language, a procedure to eliminate hierarchy from an automaton is given.