OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bounds for the Average and Smoothed Number of Pareto Optima
Venue: arXiv cs.DS 2011
Year: 2011

Smoothed analysis of multiobjective 0-1 linear optimization has drawn considerable attention recently. The number of Pareto-optimal solutions (i.e., solutions with the property that no other solution is at least as good in all the coordinates and better in at least one) for multiobjective optimization problems is the central object of study. In this paper, we prove several lower bounds for the expected number of Pareto optima. Our basic result is a lower bound of Ω_d(n^(d-1)) for optimization problems with d objectives and n variables under fairly general conditions on the distributions of the linear objectives. Our proof relates the problem of lower bounding the number of Pareto optima to results in geometry connected to arrangements of hyperplanes. We use our basic result to derive (1) To our knowledge, the first lower bound for natural multiobjective optimization problems. We illustrate this for the maximum spanning tree problem with randomly chosen edge weights. Our technique is sufficiently flexible to yield such lower bounds for other standard objective functions studied in this setting (such as, multiobjective shortest path, TSP tour, matching). (2) Smoothed lower bound of min {Ω_d(n^(d-1.5) ϕ^{(d-log d) (1-Θ(1/ϕ))}), 2^{Θ(n)}}$ for the 0-1 knapsack problem with d profits for phi-semirandom distributions for a version of the knapsack problem. This improves the recent lower bound of Brunsch and Roeglin.
The Harmonic Theory; A mathematical framework to build intelligent contextual and adaptive computing, cognition and sensory system
Venue: arXiv cs.AI 2011
Year: 2011

Harmonic theory provides a mathematical framework to describe the structure, behavior, evolution and emergence of harmonic systems. A harmonic system is context aware, contains elements that manifest characteristics either collaboratively or independently according to system's expression and can interact with its environment. This theory provides a fresh way to analyze emergence and collaboration of "ad-hoc" and complex systems.
PM2PLS: An Integration of Proxy Mobile IPv6 and MPLS
Venue: arXiv cs.NI 2011
Year: 2011

This paper proposes a handover scheme supporting Multi-Protocol Label Switching (MPLS) in a Proxy Mobile IPv6 (PMIPv6) domain that improves the mobility and gives Quality of Service (QoS) and Traffic Engineering (TE) capabilities in wireless access networks. The proposed scheme takes advantages of both PMIPv6 and MPLS. PMIPv6 was designed to provide NETwork-based Localized Mobility Management (NETLMM) support to a Mobile Node (MN); therefore, the MN does not perform any mobility related signaling, while MPLS is used as an alternative tunneling technology between the Mobile Access Gateway (MAG) and the Local Mobility Anchor (LMA) replacing the IP-in-IP tunnels with Label Switched Path (LSP) tunnels. It can also be integrated with other QoS architectures such as Differentiated Services (DiffServ) and/or Integrated Services (IntServ). In this study, we used MATLAB to perform an analysis to evaluate the impact of introducing MPLS technology in PMIPv6 domain based on handover latency, operational overhead and packet loss during the handover. This was compared with PMIPv6, and a PMIPv6/MPLS integration. We proved that the proposed scheme can give better performance than other schemes.
Linear Differential Equations with Fuzzy Boundary Values
Venue: arXiv cs.NA 2011
Year: 2011

In this study, we consider a linear differential equation with fuzzy boundary values. We express the solution of the problem in terms of a fuzzy set of crisp real functions. Each real function from the solution set satisfies differential equation, and its boundary values belong to intervals, determined by the corresponding fuzzy numbers. The least possibility among possibilities of boundary values in corresponding fuzzy sets is defined as the possibility of the real function in the fuzzy solution. In order to find the fuzzy solution we propose a method based on the properties of linear transformations. We show that, if the corresponding crisp problem has a unique solution then the fuzzy problem has unique solution too. We also prove that if the boundary values are triangular fuzzy numbers, then the value of the solution at any time is also a triangular fuzzy number. We find that the fuzzy solution determined by our method is the same as the one that is obtained from solution of crisp problem by the application of the extension principle. We present two examples describing the proposed method.
Functions as proofs as processes
Venue: arXiv cs.LO 2011
Year: 2011

This paper presents a logical approach to the translation of functional calculi into concurrent process calculi. The starting point is a type system for the π-calculus closely related to linear logic. Decompositions of intuitionistic and classical logics into this system provide type-preserving translations of the λ- and λμ-calculus, both for call-by-name and call-by-value evaluation strategies. Previously known encodings of the \lam-calculus are shown to correspond to particular cases of this logical embedding. The realisability interpretation of types in the π-calculus provides systematic soundness arguments for these translations and allows for the definition of type-safe extensions of functional calculi.
NK landscapes difficulty and Negative Slope Coefficient: How Sampling Influences the Results
Venue: arXiv cs.AI 2011
Year: 2011

Negative Slope Coefficient is an indicator of problem hardness that has been introduced in 2004 and that has returned promising results on a large set of problems. It is based on the concept of fitness cloud and works by partitioning the cloud into a number of bins representing as many different regions of the fitness landscape. The measure is calculated by joining the bins centroids by segments and summing all their negative slopes. In this paper, for the first time, we point out a potential problem of the Negative Slope Coefficient: we study its value for different instances of the well known NK-landscapes and we show how this indicator is dramatically influenced by the minimum number of points contained into a bin. Successively, we formally justify this behavior of the Negative Slope Coefficient and we discuss pros and cons of this measure.
Long-Term Energy Constraints and Power Control in Cognitive Radio Networks
Venue: arXiv cs.NI 2011
Year: 2011

When a long-term energy constraint is imposed to a transmitter, the average energy-efficiency of a transmitter is, in general, not maximized by always transmitting. In a cognitive radio context, this means that a secondary link can re-exploit the non-used time-slots. In the case where the secondary link is imposed to generate no interference on the primary link, a relevant issue is therefore to know the fraction of time-slots available to the secondary transmitter, depending on the system parameters. On the other hand, if the secondary transmitter is modeled as a selfish and free player choosing its power control policy to maximize its average energy-efficiency, resulting primary and secondary signals are not necessarily orthogonal and studying the corresponding Stackelberg game is relevant to know the outcome of this interactive situation in terms of power control policies.
Dynamics in Near-Potential Games
Venue: arXiv cs.GT 2011
Year: 2011

Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are "close" to a potential game should share similar properties. In this paper, we formalize and develop this idea by quantifying to what extent the dynamic features of potential games extend to "near-potential" games. We study convergence of three commonly studied classes of adaptive dynamics: discrete-time better/best response, logit response, and discrete-time fictitious play dynamics. For better/best response dynamics, we focus on the evolution of the sequence of pure strategy profiles and show that this sequence converges to a (pure) approximate equilibrium set, whose size is a function of the "distance" from a close potential game. We then study logit response dynamics and provide a characterization of the stationary distribution of this update rule in terms of the distance of the game from a close potential game and the corresponding potential function. We further show that the stochastically stable strategy profiles are pure approximate equilibria. Finally, we turn attention to fictitious play, and establish that the sequence of empirical frequencies of player actions converges to a neighborhood of (mixed) equilibria of the game, where the size of the neighborhood increases with distance of the game to a potential game. Thus, our results suggest that games that are close to a potential game inherit the dynamical properties of potential games. Since a close potential game to a given game can be found by solving a convex optimization problem, our approach also provides a systematic framework for studying convergence behavior of adaptive learning dynamics in arbitrary finite strategic form games.
Frequency based Classification of Activities using Accelerometer Data
Venue: arXiv cs.NE 2011
Year: 2011

This work presents, the classification of user activities such as Rest, Walk and Run, on the basis of frequency component present in the acceleration data in a wireless sensor network environment. As the frequencies of the above mentioned activities differ slightly for different person, so it gives a more accurate result. The algorithm uses just one parameter i.e. the frequency of the body acceleration data of the three axes for classifying the activities in a set of data. The algorithm includes a normalization step and hence there is no need to set a different value of threshold value for magnitude for different test person. The classification is automatic and done on a block by block basis.
Frequency Domain Approach for Activity Classification using Accelerometer
Venue: arXiv cs.ET 2011
Year: 2011

Activity classification was performed using MEMS accelerometer and wireless sensor node for wireless sensor network environment. Three axes MEMS accelerometer measures body's acceleration and transmits measured data with the help of sensor node to base station attached to PC. On the PC, real time accelerometer data is processed for movement classifications. In this paper, Rest, walking and running are the classified activities of the person. Both time and frequency analysis was performed to classify running and walking. The classification of rest and movement is done using Signal magnitude area (SMA). The classification accuracy for rest and movement is 100%. For the classification of walk and Run two parameters i.e. SMA and Median frequency were used. The classification accuracy for walk and running was detected as 81.25% in the experiments performed by the test persons.
High Accuracy Human Activity Monitoring using Neural network
Venue: arXiv cs.NE 2011
Year: 2011

This paper presents the designing of a neural network for the classification of Human activity. A Triaxial accelerometer sensor, housed in a chest worn sensor unit, has been used for capturing the acceleration of the movements associated. All the three axis acceleration data were collected at a base station PC via a CC2420 2.4GHz ISM band radio (zigbee wireless compliant), processed and classified using MATLAB. A neural network approach for classification was used with an eye on theoretical and empirical facts. The work shows a detailed description of the designing steps for the classification of human body acceleration data. A 4-layer back propagation neural network, with Levenberg-marquardt algorithm for training, showed best performance among the other neural network training algorithms.
Counting Perfect Matchings as Fast as Ryser
Venue: arXiv cs.DS 2011
Year: 2011

We show that there is a polynomial space algorithm that counts the number of perfect matchings in an $n$-vertex graph in $O^*(2^{n/2})\subset O(1.415^n)$ time. ($O^*(f(n))$ suppresses functions polylogarithmic in $f(n)$).The previously fastest algorithms for the problem was the exponential space $O^*(((1+\sqrt{5})/2)^n) \subset O(1.619^n)$ time algorithm by Koivisto, and for polynomial space, the $O(1.942^n)$ time algorithm by Nederlof. Our new algorithm's runtime matches up to polynomial factors that of Ryser's 1963 algorithm for bipartite graphs. We present our algorithm in the more general setting of computing the hafnian over an arbitrary ring, analogously to Ryser's algorithm for permanent computation. We also give a simple argument why the general exact set cover counting problem over a slightly superpolynomial sized family of subsets of an $n$ element ground set cannot be solved in $O^*(2^{(1-ε_1)n})$ time for any $ε_1>0$ unless there are $O^*(2^{(1-ε_2)n})$ time algorithms for computing an $n\times n$ 0/1 matrix permanent, for some $ε_2>0$ depending only on $ε_1$.
Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of detecting a small subset of defective items from a large set via non-adaptive "random pooling" group tests. We consider both the case when the measurements are noiseless, and the case when the measurements are noisy (the outcome of each group test may be independently faulty with probability q). Order-optimal results for these scenarios are known in the literature. We give information-theoretic lower bounds on the query complexity of these problems, and provide corresponding computationally efficient algorithms that match the lower bounds up to a constant factor. To the best of our knowledge this work is the first to explicitly estimate such a constant that characterizes the gap between the upper and lower bounds for these problems.
Solving Linear Constraints in Elementary Abelian p-Groups of Symmetries
Venue: arXiv cs.AI 2011
Year: 2011

Symmetries occur naturally in CSP or SAT problems and are not very difficult to discover, but using them to prune the search space tends to be very challenging. Indeed, this usually requires finding specific elements in a group of symmetries that can be huge, and the problem of their very existence is NP-hard. We formulate such an existence problem as a constraint problem on one variable (the symmetry to be used) ranging over a group, and try to find restrictions that may be solved in polynomial time. By considering a simple form of constraints (restricted by a cardinality k) and the class of groups that have the structure of Fp-vector spaces, we propose a partial algorithm based on linear algebra. This polynomial algorithm always applies when k=p=2, but may fail otherwise as we prove the problem to be NP-hard for all other values of k and p. Experiments show that this approach though restricted should allow for an efficient use of at least some groups of symmetries. We conclude with a few directions to be explored to efficiently solve this problem on the general case.
Groupstrategyproofness of the Egalitarian Mechanism for Constrained Rationing Problems
Venue: arXiv cs.GT 2011
Year: 2011

The key contribution of the paper is a comprehensive study of the egalitarian mechanism with respect to manipulation by a coalition of agents. Our main result is that the egalitarian mechanism is, in fact, peak group strategyproof : no coalition of agents can (weakly) benefit from jointly misreporting their peaks. Furthermore, we show that the egalitarian mechanism cannot be manipulated by any coalition of suppliers (or any coalition of demanders) in the model where both the suppliers and demanders are agents. Our proofs shed light on the structure of the two models and simpify some of the earlier proofs of strategyproofness in the earlier papers. An implication of our results is that the well known algorithm of Megiddo to compute a lexicographically optimal flow in a network is group strategyproof with respect to the source capacities (or sink capacities).
Collective Attention and the Dynamics of Group Deals
Venue: arXiv cs.CY 2011
Year: 2011

We present a study of the group purchasing behavior of daily deals in Groupon and LivingSocial and introduce a predictive dynamic model of collective attention for group buying behavior. In our model, the aggregate number of purchases at a given time comprises two types of processes: random discovery and social propagation. We find that these processes are very clearly separated by an inflection point. Using large data sets from both Groupon and LivingSocial we show how the model is able to predict the success of group deals as a function of time. We find that Groupon deals are easier to predict accurately earlier in the deal lifecycle than LivingSocial deals due to the final number of deal purchases saturating quicker. One possible explanation for this is that the incentive to socially propagate a deal is based on an individual threshold in LivingSocial, whereas in Groupon it is based on a collective threshold, which is reached very early. Furthermore, the personal benefit of propagating a deal is also greater in LivingSocial.
Constant-time filtering using shiftable kernels
Venue: arXiv cs.CV 2011
Year: 2011

It was recently demonstrated in [5] that the non-linear bilateral filter [14] can be efficiently implemented using a constant-time or O(1) algorithm. At the heart of this algorithm was the idea of approximating the Gaussian range kernel of the bilateral filter using trigonometric functions. In this letter, we explain how the idea in [5] can be extended to few other linear and non-linear filters [14, 17, 2]. While some of these filters have received a lot of attention in recent years, they are known to be computationally intensive. To extend the idea in [5], we identify a central property of trigonometric functions, called shiftability, that allows us to exploit the redundancy inherent in the filtering operations. In particular, using shiftable kernels, we show how certain complex filtering can be reduced to simply that of computing the moving sum of a stack of images. Each image in the stack is obtained through an elementary pointwise transform of the input image. This has a two-fold advantage. First, we can use fast recursive algorithms for computing the moving sum [15, 6], and, secondly, we can use parallel computation to further speed up the computation. We also show how shiftable kernels can also be used to approximate the (non-shiftable) Gaussian kernel that is ubiquitously used in image filtering.
Computing the obstacle number of a plane graph
Venue: arXiv cs.CG 2011
Year: 2011

An obstacle representation of a plane graph G is V(G) together with a set of opaque polygonal obstacles such that G is the visibility graph on V(G) determined by the obstacles. We investigate the problem of computing an obstacle representation of a plane graph (ORPG) with a minimum number of obstacles. We call this minimum size the obstacle number of G. First, we show that ORPG is NP-hard by reduction from planar vertex cover, resolving a question posed by [8]. Second, we give a reduction from ORPG to maximum degree 3 planar vertex cover. Since this reduction preserves solution values, it follows that ORPG is fixed parameter tractable (FPT) and admits a polynomial-time approximation scheme (PTAS).
Higher Order Programming to Mine Knowledge for a Modern Medical Expert System
Venue: arXiv cs.LO 2011
Year: 2011

Knowledge mining is the process of deriving new and useful knowledge from vast volumes of data and background knowledge. Modern healthcare organizations regularly generate huge amount of electronic data stored in the databases. These data are a valuable resource for mining useful knowledge to help medical practitioners making appropriate and accurate decision on the diagnosis and treatment of diseases. In this paper, we propose the design of a novel medical expert system based on a logic-programming framework. The proposed system includes a knowledge-mining component as a repertoire of tools for discovering useful knowledge. The implementation of classification and association mining tools based on the higher order and meta-level programming schemes using Prolog has been presented to express the power of logic-based language. Such language also provides a pattern matching facility, which is an essential function for the development of knowledge-intensive tasks. Besides the major goal of medical decision support, the knowledge discovered by our logic-based knowledge-mining component can also be deployed as background knowledge to pre-treatment data from other sources as well as to guard the data repositories against constraint violation. A framework for knowledge deployment is also presented.
MediaWiki Grammar Recovery
Venue: arXiv cs.MM 2011
Year: 2011

The paper describes in detail the recovery effort of one of the official MediaWiki grammars. Over two hundred grammar transformation steps are reported and annotated, leading to delivery of a level 2 grammar, semi-automatically extracted from a community created semi-formal text using at least five different syntactic notations, several non-enforced naming conventions, multiple misspellings, obsolete parsing technology idiosyncrasies and other problems commonly encountered in grammars that were not engineered properly. Having a quality grammar will allow to test and validate it further, without alienating the community with a separately developed grammar.
mizar-items: Exploring fine-grained dependencies in the Mizar Mathematical Library
Venue: arXiv cs.DL 2011
Year: 2011

The Mizar Mathematical Library (MML) is a rich database of formalized mathematical proofs (see http://mizar.org). Owing to its large size (it contains more than 1100 "articles" summing to nearly 2.5 million lines of text, expressing more than 50000 theorems and 10000 definitions using more than 7000 symbols), the nature of its contents (the MML is slanted toward pure mathematics), and its classical foundations (first-order logic, set theory, natural deduction), the MML is an especially attractive target for research on foundations of mathematics. We have implemented a system, mizar-items, on which a variety of such foundational experiements can be based. The heart of mizar-items is a method for decomposing the contents of the MML into fine-grained "items" (e.g., theorem, definition, notation, etc.) and computing dependency relations among these items. mizar-items also comes equipped with a website for exploring these dependencies and interacting with them.
Use Pronunciation by Analogy for text to speech system in Persian language
Venue: arXiv cs.CL 2011
Year: 2011

The interest in text to speech synthesis increased in the world .text to speech have been developed formany popular languages such as English, Spanish and French and many researches and developmentshave been applied to those languages. Persian on the other hand, has been given little attentioncompared to other languages of similar importance and the research in Persian is still in its infancy.Persian language possess many difficulty and exceptions that increase complexity of text to speechsystems. For example: short vowels is absent in written text or existence of homograph words. in thispaper we propose a new method for persian text to phonetic that base on pronunciations by analogy inwords, semantic relations and grammatical rules for finding proper phonetic. Keywords:PbA, text to speech, Persian language, FPbA