OpenRaiser/Intern-Atlas huggingface dataset:
A new algebraic technique for polynomial-time computing the number modulo 2 of Hamiltonian decompositions and similar partitions of a graph's edge set
Venue: arXiv cs.DM 2010
Year: 2010

In Graph Theory a number of results were devoted to studying the computational complexity of the number modulo 2 of a graph's edge set decompositions of various kinds, first of all including its Hamiltonian decompositions, as well as the number modulo 2 of, say, Hamiltonian cycles/paths etc. While the problems of finding a Hamiltonian decomposition and Hamiltonian cycle are NP-complete, counting these objects modulo 2 in polynomial time is yet possible for certain types of regular undirected graphs. Some of the most known examples are the theorems about the existence of an even number of Hamiltonian decompositions in a 4-regular graph and an even number of such decompositions where two given edges e and g belong to different cycles (Thomason, 1978), as well as an even number of Hamiltonian cycles passing through any given edge in a regular odd-degreed graph (Smith's theorem). The present article introduces a new algebraic technique which generalizes the notion of counting modulo 2 via applying fields of Characteristic 2 and determinants and, for instance, allows to receive a polynomial-time formula for the number modulo 2 of a 4-regular bipartite graph's Hamiltonian decompositions such that a given edge and a given path of length 2 belong to different Hamiltonian cycles - hence refining/extending (in a computational sense) Thomason's result for bipartite graphs. This technique also provides a polynomial-time calculation of the number modulo 2 of a graph's edge set decompositions into simple cycles each containing at least one element of a given set of its edges what is a similar kind of extension of Thomason's theorem as well.
Finding Your Literature Match -- A Recommender System
Venue: arXiv cs.DL 2010
Year: 2010

The universe of potentially interesting, searchable literature is expanding continuously. Besides the normal expansion, there is an additional influx of literature because of interdisciplinary boundaries becoming more and more diffuse. Hence, the need for accurate, efficient and intelligent search tools is bigger than ever. Even with a sophisticated search engine, looking for information can still result in overwhelming results. An overload of information has the intrinsic danger of scaring visitors away, and any organization, for-profit or not-for-profit, in the business of providing scholarly information wants to capture and keep the attention of its target audience. Publishers and search engine engineers alike will benefit from a service that is able to provide visitors with recommendations that closely meet their interests. Providing visitors with special deals, new options and highlights may be interesting to a certain degree, but what makes more sense (especially from a commercial point of view) than to let visitors do most of the work by the mere action of making choices? Hiring psychics is not an option, so a technological solution is needed to recommend items that a visitor is likely to be looking for. In this presentation we will introduce such a solution and argue that it is practically feasible to incorporate this approach into a useful addition to any information retrieval system with enough usage.
A Short Introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length (MDL)
Venue: arXiv cs.LG 2010
Year: 2010

The concept of overfitting in model selection is explained and demonstrated with an example. After providing some background information on information theory and Kolmogorov complexity, we provide a short explanation of Minimum Description Length and error minimization. We conclude with a discussion of the typical features of overfitting in model selection.
Proviola: A Tool for Proof Re-animation
Venue: arXiv cs.LO 2010
Year: 2010

To improve on existing models of interaction with a proof assistant (PA), in particular for storage and replay of proofs, we in- troduce three related concepts, those of: a proof movie, consisting of frames which record both user input and the corresponding PA response; a camera, which films a user's interactive session with a PA as a movie; and a proviola, which replays a movie frame-by-frame to a third party. In this paper we describe the movie data structure and we discuss a proto- type implementation of the camera and proviola based on the ProofWeb system. ProofWeb uncouples the interaction with a PA via a web- interface (the client) from the actual PA that resides on the server. Our camera films a movie by "listening" to the ProofWeb communication. The first reason for developing movies is to uncouple the reviewing of a formal proof from the PA used to develop it: the movie concept enables users to discuss small code fragments without the need to install the PA or to load a whole library into it. Other advantages include the possibility to develop a separate com- mentary track to discuss or explain the PA interaction. We assert that a combined camera+proviola provides a generic layer between a client (user) and a server (PA). Finally we claim that movies are the right type of data to be stored in an encyclopedia of formalized mathematics, based on our experience in filming the Coq standard library.
Surface Parametrization of Nonsimply Connected Planar Bézier Regions
Venue: arXiv cs.CG 2010
Year: 2010

A technique is described for constructing three-dimensional vector graphics representations of planar regions bounded by cubic Bézier curves, such as smooth glyphs. It relies on a novel algorithm for compactly partitioning planar Bézier regions into nondegenerate Coons patches. New optimizations are also described for Bézier inside-outside tests and the computation of global bounds of directionally monotonic functions over a Bézier surface (such as its bounding box or optimal field-of-view angle). These algorithms underlie the three-dimensional illustration and typography features of the TeX-aware vector graphics language Asymptote.
Interactive Realizers and Monads
Venue: arXiv cs.LO 2010
Year: 2010

We propose a realizability interpretation of a system for quantifier free arithmetic which is equivalent to the fragment of classical arithmetic without "nested" quantifiers, called here EM1-arithmetic. We interpret classical proofs as interactive learning strategies, namely as processes going through several stages of knowledge and learning by interacting with the "environment" and with each other. We give a categorical presentation of the interpretation through the construction of two suitable monads.
Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving
Venue: arXiv cs.NA 2010
Year: 2010

Recent work in theoretical computer science and scientific computing has focused on nearly-linear-time algorithms for solving systems of linear equations. While introducing several novel theoretical perspectives, this work has yet to lead to practical algorithms. In an effort to bridge this gap, we describe in this paper two related results. Our first and main result is a simple algorithm to approximate the solution to a set of linear equations defined by a Laplacian (for a graph $G$ with $n$ nodes and $m \le n^2$ edges) constraint matrix. The algorithm is a non-recursive algorithm; even though it runs in $O(n^2 \cdot \polylog(n))$ time rather than $O(m \cdot polylog(n))$ time (given an oracle for the so-called statistical leverage scores), it is extremely simple; and it can be used to compute an approximate solution with a direct solver. In light of this result, our second result is a straightforward connection between the concept of graph resistance (which has proven useful in recent algorithms for linear equation solvers) and the concept of statistical leverage (which has proven useful in numerically-implementable randomized algorithms for large matrix problems and which has a natural data-analytic interpretation).
Verifiable Network-Performance Measurements
Venue: arXiv cs.NI 2010
Year: 2010

In the current Internet, there is no clean way for affected parties to react to poor forwarding performance: when a domain violates its Service Level Agreement (SLA) with a contractual partner, the partner must resort to ad-hoc probing-based monitoring to determine the existence and extent of the violation. Instead, we propose a new, systematic approach to the problem of forwarding-performance verification. Our mechanism relies on voluntary reporting, allowing each domain to disclose its loss and delay performance to its neighbors; it does not disclose any information regarding the participating domains' topology or routing policies beyond what is already publicly available. Most importantly, it enables verifiable performance measurements, i.e., domains cannot abuse it to significantly exaggerate their performance. Finally, our mechanism is tunable, allowing each participating domain to determine how many resources to devote to it independently (i.e., without any inter-domain coordination), exposing a controllable trade-off between performance-verification quality and resource consumption. Our mechanism comes at the cost of deploying modest functionality at the participating domains' border routers; we show that it requires reasonable processing and memory resources within modern network capabilities.
Haptics in computer music : a paradigm shift
Venue: arXiv cs.HC 2010
Year: 2010

With an historical point of view combined with a bibliographic overview, the article discusses the idea that haptic force feedback transducers correspond with a paradigm shift in our real-time tools for creating music. So doing, il shows that computer music may be regarded as a major field of research and application for haptics.
From granular avalanches to fluid turbulences through oozing pastes. A mesoscopic physically-based particle model
Venue: arXiv cs.GR 2010
Year: 2010

In this paper, we describe how we can precisely produce complex and various dynamic morphological features such as structured and chaotic features which occur in sand pilings (piles, avalanches, internal collapses, arches) , in flowing fluids (laminar flowing, Kelvin-Helmholtz and Von Karmann eddies), and in cohesive pastes (twist-and-turn oozing and packing) using only a single unified model, called "mesoscopic model". This model is a physically-based particle model whose behavior depends on only four simple, but easy to understand, physically-based parameters : elasticity, viscosity and their local areas of influence. It is fast to compute and easy to understand by non-physicist users.
Cellular Automata in Stream Ciphers
Venue: arXiv cs.CR 2010
Year: 2010

A wide family of nonlinear sequence generators, the so-called clock-controlled shrinking generators, has been analyzed and identified with a subset of linear cellular automata. The algorithm that converts the given generator into a linear model based on automata is very simple and can be applied in a range of practical interest. Due to the linearity of these automata as well as the characteristics of this class of generators, a cryptanalytic approach can be proposed. Linear cellular structures easily model keystream generators with application in stream cipher cryptography.
Efficient System-Enforced Deterministic Parallelism
Venue: arXiv cs.OS 2010
Year: 2010

Deterministic execution offers many benefits for debugging, fault tolerance, and security. Running parallel programs deterministically is usually difficult and costly, however - especially if we desire system-enforced determinism, ensuring precise repeatability of arbitrarily buggy or malicious software. Determinator is a novel operating system that enforces determinism on both multithreaded and multi-process computations. Determinator's kernel provides only single-threaded, "shared-nothing" address spaces interacting via deterministic synchronization. An untrusted user-level runtime uses distributed computing techniques to emulate familiar abstractions such as Unix processes, file systems, and shared memory multithreading. The system runs parallel applications deterministically both on multicore PCs and across nodes in a cluster. Coarse-grained parallel benchmarks perform and scale comparably to - sometimes better than - conventional systems, though determinism is costly for fine-grained parallel applications.
Evolution with Drifting Targets
Venue: arXiv cs.LG 2010
Year: 2010

We consider the question of the stability of evolutionary algorithms to gradual changes, or drift, in the target concept. We define an algorithm to be resistant to drift if, for some inverse polynomial drift rate in the target function, it converges to accuracy 1 -- ε, with polynomial resources, and then stays within that accuracy indefinitely, except with probability ε, at any one time. We show that every evolution algorithm, in the sense of Valiant (2007; 2009), can be converted using the Correlational Query technique of Feldman (2008), into such a drift resistant algorithm. For certain evolutionary algorithms, such as for Boolean conjunctions, we give bounds on the rates of drift that they can resist. We develop some new evolution algorithms that are resistant to significant drift. In particular, we give an algorithm for evolving linear separators over the spherically symmetric distribution that is resistant to a drift rate of O(ε/n), and another algorithm over the more general product normal distributions that resists a smaller drift rate. The above translation result can be also interpreted as one on the robustness of the notion of evolvability itself under changes of definition. As a second result in that direction we show that every evolution algorithm can be converted to a quasi-monotonic one that can evolve from any starting point without the performance ever dipping significantly below that of the starting point. This permits the somewhat unnatural feature of arbitrary performance degradations to be removed from several known robustness translations.
Threshold effects in parameter estimation as phase transitions in statistical mechanics
Venue: arXiv cs.IT 2010
Year: 2010

Threshold effects in the estimation of parameters of non-linearly modulated, continuous-time, wide-band waveforms, are examined from a statistical physics perspective. These threshold effects are shown to be analogous to phase transitions of certain disordered physical systems in thermal equilibrium. The main message, in this work, is in demonstrating that this physical point of view may be insightful for understanding the interactions between two or more parameters to be estimated, from the aspects of the threshold effect.
Nominal Unification from a Higher-Order Perspective
Venue: arXiv cs.LO 2010
Year: 2010

Nominal Logic is a version of first-order logic with equality, name-binding, renaming via name-swapping and freshness of names. Contrarily to higher-order logic, bindable names, called atoms, and instantiable variables are considered as distinct entities. Moreover, atoms are capturable by instantiations, breaking a fundamental principle of lambda-calculus. Despite these differences, nominal unification can be seen from a higher-order perspective. From this view, we show that nominal unification can be reduced to a particular fragment of higher-order unification problems: Higher-Order Pattern Unification. This reduction proves that nominal unification can be decided in quadratic deterministic time, using the linear algorithm for Higher-Order Pattern Unification. We also prove that the translation preserves most generality of unifiers.
A Scheme of Concatenated Quantum Code to Protect against both Computational Error and an Erasure
Venue: arXiv cs.IT 2010
Year: 2010

We present a description of encoding/decoding for a concatenated quantum code that enables both protection against quantum computational errors and the occurrence of one quantum erasure. For this, it is presented how encoding and decoding for quantum graph codes are done, which will provide the protection against the occurrence of computational errors (external code). As internal code is used encoding and decoding via scheme of GHZ states for protection against the occurrence of one quantum erasure.
Optical phase extraction algorithm based on the continuous wavelet and the Hilbert transforms
Venue: arXiv cs.CE 2010
Year: 2010

In this paper we present an algorithm for optical phase evaluation based on the wavelet transform technique. The main advantage of this method is that it requires only one fringe pattern. This algorithm is based on the use of a second π/2 phase shifted fringe pattern where it is calculated via the Hilbert transform. To test its validity, the algorithm was used to demodulate a simulated fringe pattern giving the phase distribution with a good accuracy.
Dissertations Repository System Using Context Module
Venue: arXiv cs.DL 2010
Year: 2010

Without a doubt, the electronic learning makes education quite flexible. Nowadays, all organizations and institutions are trying to avoid Monotony and the delay and inertia. As well the universities should be improving their systems continually to achieve success. Whereas, the students need to access the dissertations in the library. In this paper we will present Dissertations Repository System Using Context Module to allow the students to benefit the dissertations which is in the library flexibly.
Classification of LULC Change Detection using Remotely Sensed Data for Coimbatore City, Tamilnadu, India
Venue: arXiv cs.CV 2010
Year: 2010

Maps are used to describe far-off places . It is an aid for navigation and military strategies. Mapping of the lands are important and the mapping work is based on (i). Natural resource management & development (ii). Information technology ,(iii). Environmental development ,(iv). Facility management and (v). e-governance. The Landuse / Landcover system espoused by almost all Organisations and scientists, engineers and remote sensing community who are involved in mapping of earth surface features, is a system which is derived from the united States Geological Survey (USGS) LULC classification system. The application of RS and GIS involves influential of homogeneous zones, drift analysis of land use integration of new area changes or change detection etc.,National Remote Sensing Agency(NRSA) Govt. of India has devised a generalized LULC classification system respect to the Indian conditions based on the various categories of Earth surface features , resolution of available satellite data, capabilities of sensors and present and future applications. The profusion information of the earth surface offered by the high resolution satellite images for remote sensing applications. Using change detection methodologies to extract the target changes in the areas from high resolution images and rapidly updates geodatabase information processing.Traditionally, classification approaches have focused on per-pixel technologies. Pixels within areas assumed to be automatically homogeneous are analyzed independently.
Bayesian Incentive Compatibility via Fractional Assignments
Venue: arXiv cs.GT 2010
Year: 2010

Very recently, Hartline and Lucier studied single-parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive-Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an eps-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an eps-BIC mechanism that achieves constant approximation.
Classification and Performance of AQM-Based Schemes for Congestion Avoidance
Venue: arXiv cs.NI 2010
Year: 2010

Internet faces the problem of congestion due to its increased use. AQM algorithm is a solution to the problem of congestion control in the Internet. There are various existing algorithms that have evolved over the past few years to solve the problem of congestion in IP networks. Congested link causes many problems such as large delay, underutilization of the link and packet drops in burst. There are various existing algorithms that have evolved over the past few years to solve the problem of congestion in IP networks. In this paper, study of these existing algorithms is done. This paper discusses algorithms based on various congestion-metrics and classifies them based on certain factors. This helps in identifying the algorithms that regulate the congestion more effectively.
Facial Recognition Technology: An analysis with scope in India
Venue: arXiv cs.MA 2010
Year: 2010

A facial recognition system is a computer application for automatically identifying or verifying a person from a digital image or a video frame from a video source. One of the way is to do this is by comparing selected facial features from the image and a facial database.It is typically used in security systems and can be compared to other biometrics such as fingerprint or eye iris recognition systems. In this paper we focus on 3-D facial recognition system and biometric facial recognision system. We do critics on facial recognision system giving effectiveness and weaknesses. This paper also introduces scope of recognision system in India.
Clustering Time Series Data Stream - A Literature Survey
Venue: arXiv cs.IR 2010
Year: 2010

Mining Time Series data has a tremendous growth of interest in today's world. To provide an indication various implementations are studied and summarized to identify the different problems in existing applications. Clustering time series is a trouble that has applications in an extensive assortment of fields and has recently attracted a large amount of research. Time series data are frequently large and may contain outliers. In addition, time series are a special type of data set where elements have a temporal ordering. Therefore clustering of such data stream is an important issue in the data mining process. Numerous techniques and clustering algorithms have been proposed earlier to assist clustering of time series data streams. The clustering algorithms and its effectiveness on various applications are compared to develop a new method to solve the existing problem. This paper presents a survey on various clustering algorithms available for time series datasets. Moreover, the distinctiveness and restriction of previous research are discussed and several achievable topics for future study are recognized. Furthermore the areas that utilize time series clustering are also summarized.
Scheduling Packets with Values and Deadlines in Size-bounded Buffers
Venue: arXiv cs.DS 2010
Year: 2010

Motivated by providing quality-of-service differentiated services in the Internet, we consider buffer management algorithms for network switches. We study a multi-buffer model. A network switch consists of multiple size-bounded buffers such that at any time, the number of packets residing in each individual buffer cannot exceed its capacity. Packets arrive at the network switch over time; they have values, deadlines, and designated buffers. In each time step, at most one pending packet is allowed to be sent and this packet can be from any buffer. The objective is to maximize the total value of the packets sent by their respective deadlines. A 9.82-competitive online algorithm has been provided for this model (Azar and Levy. SWAT 2006), but no offline algorithms have been known yet. In this paper, We study the offline setting of the multi-buffer model. Our contributions include a few optimal offline algorithms for some variants of the model. Each variant has its unique and interesting algorithmic feature. These offline algorithms help us understand the model better in designing online algorithms.