OpenRaiser/Intern-Atlas huggingface dataset:
An L(1/3) algorithm for ideal class group and regulator computation in certain number fields
Venue: arXiv cs.CR 2009
Year: 2009

We analyse the complexity of the computation of the class group structure, regulator, and a system of fundamental units of a certain class of number fields. Our approach differs from Buchmann's, who proved a complexity bound of L(1/2,O(1)) when the discriminant tends to infinity with fixed degree. We achieve a subexponential complexity in O(L(1/3,O(1))) when both the discriminant and the degree of the extension tend to infinity by using techniques due to Enge and Gaudry in the context of algebraic curves over finite fields.
Efficient Gaussian Elimination on a 2D SIMD Array of Processors without Column Broadcasts
Venue: arXiv cs.DC 2009
Year: 2009

This paper presents an efficient method for implementing the Gaussian elimination technique for an nxm (m>=n) matrix, using a 2D SIMD array of nxm processors. The described algorithm consists of 2xn-1=O(n) iterations, which provides an optimal speed-up over the serial version. A particularity of the algorithm is that it only requires broadcasts on the rows of the processor matrix and not on its columns. The paper also presents several extensions and applications of the Gaussian elimination algorithm.
Computing a Discrete Logarithm in O(n^3)
Venue: arXiv cs.DS 2009
Year: 2009

This paper presents a means with time complexity of at worst O(n^3) to compute the discrete logarithm on cyclic finite groups of integers modulo p. The algorithm makes use of reduction of the problem to that of finding the concurrent zeros of two periodic functions in the real numbers. The problem is treated as an analog to a form of analog rotor-code computed cipher.
NeuralNetwork Based 3D Surface Reconstruction
Venue: arXiv cs.NE 2009
Year: 2009

This paper proposes a novel neural-network-based adaptive hybrid-reflectance three-dimensional (3-D) surface reconstruction model. The neural network combines the diffuse and specular components into a hybrid model. The proposed model considers the characteristics of each point and the variant albedo to prevent the reconstructed surface from being distorted. The neural network inputs are the pixel values of the two-dimensional images to be reconstructed. The normal vectors of the surface can then be obtained from the output of the neural network after supervised learning, where the illuminant direction does not have to be known in advance. Finally, the obtained normal vectors can be applied to integration method when reconstructing 3-D objects. Facial images were used for training in the proposed approach
Heart Rate Variability Analysis Using Threshold of Wavelet Package Coefficients
Venue: arXiv cs.CV 2009
Year: 2009

In this paper, a new efficient feature extraction method based on the adaptive threshold of wavelet package coefficients is presented. This paper especially deals with the assessment of autonomic nervous system using the background variation of the signal Heart Rate Variability HRV extracted from the wavelet package coefficients. The application of a wavelet package transform allows us to obtain a time-frequency representation of the signal, which provides better insight in the frequency distribution of the signal with time. A 6 level decomposition of HRV was achieved with db4 as mother wavelet, and the above two bands LF and HF were combined in 12 specialized frequencies sub-bands obtained in wavelet package transform. Features extracted from these coefficients can efficiently represent the characteristics of the original signal. ANOVA statistical test is used for the evaluation of proposed algorithm.
Identifying the Importance of Software Reuse in COCOMO81, COCOMOII
Venue: arXiv cs.SE 2009
Year: 2009

Software project management is an interpolation of project planning, project monitoring and project termination. The substratal goals of planning are to scout for the future, to diagnose the attributes that are essentially done for the consummation of the project successfully, animate the scheduling and allocate resources for the attributes. Software cost estimation is a vital role in preeminent software project decisions such as resource allocation and bidding. This paper articulates the conventional overview of software cost estimation modus operandi available. The cost, effort estimates of software projects done by the various companies are congregated, the results are segregated with the present cost models and the MRE (Mean Relative Error) is enumerated. We have administered the historical data to COCOMO 81, COCOMOII model and identified that the stellar predicament is that no cost model gives the exact estimate of a software project.
Algebraic totality, towards completeness
Venue: arXiv cs.LO 2009
Year: 2009

Finiteness spaces constitute a categorical model of Linear Logic (LL) whose objects can be seen as linearly topologised spaces, (a class of topological vector spaces introduced by Lefschetz in 1942) and morphisms as continuous linear maps. First, we recall definitions of finiteness spaces and describe their basic properties deduced from the general theory of linearly topologised spaces. Then we give an interpretation of LL based on linear algebra. Second, thanks to separation properties, we can introduce an algebraic notion of totality candidate in the framework of linearly topologised spaces: a totality candidate is a closed affine subspace which does not contain 0. We show that finiteness spaces with totality candidates constitute a model of classical LL. Finally, we give a barycentric simply typed lambda-calculus, with booleans ${\mathcal{B}}$ and a conditional operator, which can be interpreted in this model. We prove completeness at type ${\mathcal{B}}^n\to{\mathcal{B}}$ for every n by an algebraic method.
Limited Feedback for Temporally Correlated MIMO Channels with Other Cell Interference
Venue: arXiv cs.IT 2009
Year: 2009

Limited feedback improves link reliability with a small amount of feedback from the receiver back to the transmitter. In cellular systems, the performance of limited feedback will be degraded in the presence of other cell interference, when the base stations have limited or no coordination. This paper establishes the degradation in sum rate of users in a cellular system, due to uncoordinated other cell interference and delay on the feedback channel. A goodput metric is defined as the rate when the bits are successfully received at the mobile station, and used to derive an upper bound on the performance of limited feedback systems with delay. This paper shows that the goodput gained from having delayed limited feedback decreases doubly exponentially as the delay increases. The analysis is extended to precoded spatial multiplexing systems where it is shown that the same upper bound can be used to evaluate the decay in the achievable sum rate. To reduce the effects of interference, zero forcing interference cancellation is applied at the receiver, where it is shown that the effect of the interference on the achievable sum rate can be suppressed by nulling out the interferer. Numerical results show that the decay rate of the goodput decreases when the codebook quantization size increases and when the doppler shift in the channel decreases.
Adapting Heuristic Mastermind Strategies to Evolutionary Algorithms
Venue: arXiv cs.NE 2009
Year: 2009

The art of solving the Mastermind puzzle was initiated by Donald Knuth and is already more than 30 years old; despite that, it still receives much attention in operational research and computer games journals, not to mention the nature-inspired stochastic algorithm literature. In this paper we try to suggest a strategy that will allow nature-inspired algorithms to obtain results as good as those based on exhaustive search strategies; in order to do that, we first review, compare and improve current approaches to solving the puzzle; then we test one of these strategies with an estimation of distribution algorithm. Finally, we try to find a strategy that falls short of being exhaustive, and is then amenable for inclusion in nature inspired algorithms (such as evolutionary or particle swarm algorithms). This paper proves that by the incorporation of local entropy into the fitness function of the evolutionary algorithm it becomes a better player than a random one, and gives a rule of thumb on how to incorporate the best heuristic strategies to evolutionary algorithms without incurring in an excessive computational cost.
Parallel symbolic state-space exploration is difficult, but what is the alternative?
Venue: arXiv cs.LO 2009
Year: 2009

State-space exploration is an essential step in many modeling and analysis problems. Its goal is to find the states reachable from the initial state of a discrete-state model described. The state space can used to answer important questions, e.g., "Is there a dead state?" and "Can N become negative?", or as a starting point for sophisticated investigations expressed in temporal logic. Unfortunately, the state space is often so large that ordinary explicit data structures and sequential algorithms cannot cope, prompting the exploration of (1) parallel approaches using multiple processors, from simple workstation networks to shared-memory supercomputers, to satisfy large memory and runtime requirements and (2) symbolic approaches using decision diagrams to encode the large structured sets and relations manipulated during state-space generation. Both approaches have merits and limitations. Parallel explicit state-space generation is challenging, but almost linear speedup can be achieved; however, the analysis is ultimately limited by the memory and processors available. Symbolic methods are a heuristic that can efficiently encode many, but not all, functions over a structured and exponentially large domain; here the pitfalls are subtler: their performance varies widely depending on the class of decision diagram chosen, the state variable order, and obscure algorithmic parameters. As symbolic approaches are often much more efficient than explicit ones for many practical models, we argue for the need to parallelize symbolic state-space generation algorithms, so that we can realize the advantage of both approaches. This is a challenging endeavor, as the most efficient symbolic algorithm, Saturation, is inherently sequential. We conclude by discussing challenges, efforts, and promising directions toward this goal.
An iterative approach for generating statistically realistic populations of households
Venue: arXiv cs.MA 2009
Year: 2009

Background: Many different simulation frameworks, in different topics, need to treat realistic datasets to initialize and calibrate the system. A precise reproduction of initial states is extremely important to obtain reliable forecast from the model. Methodology/Principal Findings: This paper proposes an algorithm to create an artificial population where individuals are described by their age, and are gathered in households respecting a variety of statistical constraints (distribution of household types, sizes, age of household head, difference of age between partners and among parents and children). Such a population is often the initial state of microsimulation or (agent) individual-based models. To get a realistic distribution of households is often very important, because this distribution has an impact on the demographic evolution. Usual techniques from microsimulation approach cross different sources of aggregated data for generating individuals. In our case the number of combinations of different households (types, sizes, age of participants) makes it computationally difficult to use directly such methods. Hence we developed a specific algorithm to make the problem more easily tractable. Conclusions/Significance: We generate the populations of two pilot municipalities in Auvergne region (France), to illustrate the approach. The generated populations show a good agreement with the available statistical datasets (not used for the generation) and are obtained in a reasonable computational time.
Specification and Verification of Side Channel Declassification
Venue: arXiv cs.CR 2009
Year: 2009

Side channel attacks have emerged as a serious threat to the security of both networked and embedded systems -- in particular through the implementations of cryptographic operations. Side channels can be difficult to model formally, but with careful coding and program transformation techniques it may be possible to verify security in the presence of specific side-channel attacks. But what if a program intentionally makes a tradeoff between security and efficiency and leaks some information through a side channel? In this paper we study such tradeoffs using ideas from recent research on declassification. We present a semantic model of security for programs which allow for declassification through side channels, and show how side-channel declassification can be verified using off-the-shelf software model checking tools. Finally, to make it simpler for verifiers to check that a program conforms to a particular side-channel declassification policy we introduce a further tradeoff between efficiency and verifiability: by writing programs in a particular "manifest form" security becomes considerably easier to verify.
Graph unique-maximum and conflict-free colorings
Venue: arXiv cs.DM 2009
Year: 2009

We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph.
Geometric and Combinatorial Properties of Well-Centered Triangulations in Three and Higher Dimensions
Venue: arXiv cs.CG 2009
Year: 2009

An n-simplex is said to be n-well-centered if its circumcenter lies in its interior. We introduce several other geometric conditions and an algebraic condition that can be used to determine whether a simplex is n-well-centered. These conditions, together with some other observations, are used to describe restrictions on the local combinatorial structure of simplicial meshes in which every simplex is well-centered. In particular, it is shown that in a 3-well-centered (2-well-centered) tetrahedral mesh there are at least 7 (9) edges incident to each interior vertex, and these bounds are sharp. Moreover, it is shown that, in stark contrast to the 2-dimensional analog, where there are exactly two vertex links that prevent a well-centered triangle mesh in R^2, there are infinitely many vertex links that prohibit a well-centered tetrahedral mesh in R^3.
New Generalization Bounds for Learning Kernels
Venue: arXiv cs.AI 2009
Year: 2009

This paper presents several novel generalization bounds for the problem of learning kernels based on the analysis of the Rademacher complexity of the corresponding hypothesis sets. Our bound for learning kernels with a convex combination of p base kernels has only a log(p) dependency on the number of kernels, p, which is considerably more favorable than the previous best bound given for the same problem. We also give a novel bound for learning with a linear combination of p base kernels with an L_2 regularization whose dependency on p is only in p^{1/4}.
Application of Graph Coloring to Biological Networks
Venue: arXiv cs.CE 2009
Year: 2009

We explore the application of graph coloring to biological networks, specifically protein-protein interaction (PPI) networks. First, we find that given similar conditions (i.e. number of nodes, number of links, degree distribution and clustering), fewer colors are needed to color disassortative (high degree nodes tend to connect to low degree nodes and vice versa) than assortative networks. Fewer colors create fewer independent sets which in turn imply higher concurrency potential for a network. Since PPI networks tend to be disassortative, we suggest that in addition to functional specificity and stability proposed previously by Maslov and Sneppen (Science 296, 2002), the disassortative nature of PPI networks may promote the ability of cells to perform multiple, crucial and functionally diverse tasks concurrently. Second, since graph coloring is closely related to the presence of cliques in a graph, the significance of node coloring information to the problem of identifying protein complexes, i.e. dense subgraphs in a PPI network, is investigated. We find that for PPI networks where 1% to 11% of nodes participate in at least one identified protein complex, such as H. sapien (DIP20070219, DIP20081014 and HPRD070609), DSATUR (a well-known complete graph coloring algorithm) node coloring information can improve the quality (homogeneity and separation) of initial candidate complexes. This finding may help to improve existing protein complex detection methods, and/or suggest new methods.
Designing ISP-friendly Peer-to-Peer Networks Using Game-based Control
Venue: arXiv cs.NI 2009
Year: 2009

The rapid growth of peer-to-peer (P2P) networks in the past few years has brought with it increases in transit cost to Internet Service Providers (ISPs), as peers exchange large amounts of traffic across ISP boundaries. This ISP oblivious behavior has resulted in misalignment of incentives between P2P networks--that seek to maximize user quality--and ISPs--that would seek to minimize costs. Can we design a P2P overlay that accounts for both ISP costs as well as quality of service, and attains a desired tradeoff between the two? We design a system, which we call MultiTrack, that consists of an overlay of multiple \emph{mTrackers} whose purpose is to align these goals. mTrackers split demand from users among different ISP domains while trying to minimize their individual costs (delay plus transit cost) in their ISP domain. We design the signals in this overlay of mTrackers in such a way that potentially competitive individual optimization goals are aligned across the mTrackers. The mTrackers are also capable of doing admission control in order to ensure that users who are from different ISP domains have a fair chance of being admitted into the system, while keeping costs in check. We prove analytically that our system is stable and achieves maximum utility with minimum cost. Our design decisions and control algorithms are validated by Matlab and ns-2 simulations.
Efficient Linear Programming Decoding of HDPC Codes
Venue: arXiv cs.IT 2009
Year: 2009

We propose several improvements for Linear Programming (LP) decoding algorithms for High Density Parity Check (HDPC) codes. First, we use the automorphism groups of a code to create parity check matrix diversity and to generate valid cuts from redundant parity checks. Second, we propose an efficient mixed integer decoder utilizing the branch and bound method. We further enhance the proposed decoders by removing inactive constraints and by adapting the parity check matrix prior to decoding according to the channel observations. Based on simulation results the proposed decoders achieve near-ML performance with reasonable complexity.
Modeling and Application of Series Elastic Actuators for Force Control Multi Legged Robots
Venue: arXiv cs.RO 2009
Year: 2009

Series Elastic Actuators provide many benefits in force control of robots in unconstrained environments. These benefits include high force fidelity, extremely low impedance, low friction, and good force control bandwidth. Series Elastic Actuators employ a novel mechanical design architecture which goes against the common machine design principal of "stiffer is better". A compliant element is placed between the gear train and driven load to intentionally reduce the stiffness of the actuator. A position sensor measures the deflection, and the force output is accurately calculated using Hooke's Law (F=Kx). A control loop then servos the actuator to the desired output force. The resulting actuator has inherent shock tolerance, high force fidelity and extremely low impedance. These characteristics are desirable in many applications including legged robots, exoskeletons for human performance amplification, robotic arms, haptic interfaces, and adaptive suspensions. We describe several variations of Series Elastic Actuators that have been developed using both electric and hydraulic components.
Realization of Semantic Atom Blog
Venue: arXiv cs.IR 2009
Year: 2009

Web blog is used as a collaborative platform to publish and share information. The information accumulated in the blog intrinsically contains the knowledge. The knowledge shared by the community of people has intangible value proposition. The blog is viewed as a multimedia information resource available on the Internet. In a blog, information in the form of text, image, audio and video builds up exponentially. The multimedia information contained in an Atom blog does not have the capability, which is required by the software processes so that Atom blog content can be accessed, processed and reused over the Internet. This shortcoming is addressed by exploring OWL knowledge modeling, semantic annotation and semantic categorization techniques in an Atom blog sphere. By adopting these techniques, futuristic Atom blogs can be created and deployed over the Internet.
Optimal Design of Fuzzy Based Power System Stabilizer Self Tuned by Robust Search Algorithm
Venue: arXiv cs.NE 2009
Year: 2009

In the interconnected power system network, instability problems are caused mainly by the low frequency oscillations of 0.2 to 2.5 Hz. The supplementary control signal in addition with AVR and high gain excitation systems are provided by means of Power System Stabilizer (PSS). Conventional power system stabilizers provide effective damping only on a particular operating point. But fuzzy based PSS provides good damping for a wide range of operating points. The bottlenecks faced in designing a fuzzy logic controller can be minimized by using appropriate optimization techniques like Genetic Algorithm, Particle Swam Optimization, Ant Colony Optimization etc.In this paper the membership functions of FLC are optimized by the new breed optimization technique called Genetic Algorithm. This design methodology is implemented on a Single Machine Infinite Bus (SMIB) system. Simulation results on SMIB show the effectiveness and robustness of the proposed PSS over a wide range of operating conditions and system configurations.
Enhancing Multi-Agent Based Simulation with Human-Agents Interactive Spatial Behaviour
Venue: arXiv cs.MA 2009
Year: 2009

We are exploring the enhancement of models of agent behaviour with more "human-like" decision making strategies than are presently available. Our motivation is to developed with a view to as the decision analysis and support for electric taxi company under the mission of energy saving and reduction of CO2, in particular car-pool and car-sharing management policies. In order to achieve the object of decision analysis for user, we provide a human-agents interactive spatial behaviour to support user making decision real time. We adopt passenger average waiting time and electric taxi average idle time as the performance measures and decision support fro electric taxi company. Finally, according to the analysis result, we demonstrate that our multi-agent simulation and GUI can help users or companies quickly make a quality and accurate decision to reduce the decision-making cost and time.