OpenRaiser/Intern-Atlas huggingface dataset:
A Practical Ontology for the Large-Scale Modeling of Scholarly Artifacts and their Usage
Venue: arXiv cs.DL 2007
Year: 2007

The large-scale analysis of scholarly artifact usage is constrained primarily by current practices in usage data archiving, privacy issues concerned with the dissemination of usage data, and the lack of a practical ontology for modeling the usage domain. As a remedy to the third constraint, this article presents a scholarly ontology that was engineered to represent those classes for which large-scale bibliographic and usage data exists, supports usage research, and whose instantiation is scalable to the order of 50 million articles along with their associated artifacts (e.g. authors and journals) and an accompanying 1 billion usage events. The real world instantiation of the presented abstract ontology is a semantic network model of the scholarly community which lends the scholarly process to statistical analysis and computational support. We present the ontology, discuss its instantiation, and provide some example inference rules for calculating various scholarly artifact metrics.
Cost-minimising strategies for data labelling : optimal stopping and active learning
Venue: arXiv cs.LG 2007
Year: 2007

Supervised learning deals with the inference of a distribution over an output or label space $\CY$ conditioned on points in an observation space $\CX$, given a training dataset $D$ of pairs in $\CX \times \CY$. However, in a lot of applications of interest, acquisition of large amounts of observations is easy, while the process of generating labels is time-consuming or costly. One way to deal with this problem is {\em active} learning, where points to be labelled are selected with the aim of creating a model with better performance than that of an model trained on an equal number of randomly sampled points. In this paper, we instead propose to deal with the labelling cost directly: The learning goal is defined as the minimisation of a cost which is a function of the expected model performance and the total cost of the labels used. This allows the development of general strategies and specific algorithms for (a) optimal stopping, where the expected cost dictates whether label acquisition should continue (b) empirical evaluation, where the cost is used as a performance metric for a given combination of inference, stopping and sampling methods. Though the main focus of the paper is optimal stopping, we also aim to provide the background for further developments and discussion in the related field of active learning.
Wavelet Based Semi-blind Channel Estimation For Multiband OFDM
Venue: arXiv cs.NI 2007
Year: 2007

This paper introduces an expectation-maximization (EM) algorithm within a wavelet domain Bayesian framework for semi-blind channel estimation of multiband OFDM based UWB communications. A prior distribution is chosen for the wavelet coefficients of the unknown channel impulse response in order to model a sparseness property of the wavelet representation. This prior yields, in maximum a posteriori estimation, a thresholding rule within the EM algorithm. We particularly focus on reducing the number of estimated parameters by iteratively discarding ``unsignificant'' wavelet coefficients from the estimation process. Simulation results using UWB channels issued from both models and measurements show that under sparsity conditions, the proposed algorithm outperforms pilot based channel estimation in terms of mean square error and bit error rate and enhances the estimation accuracy with less computational complexity than traditional semi-blind methods.
Valid formulas, games and network protocols
Venue: arXiv cs.LO 2007
Year: 2007

We describe a remarkable relation between the notion of valid formula of predicate logic and the specification of network protocols. We give several examples such as the acknowledgement of one packet or of a sequence of packets. We show how to specify the composition of protocols.
A Light-Based Device for Solving the Hamiltonian Path Problem
Venue: arXiv cs.AR 2007
Year: 2007

In this paper we suggest the use of light for performing useful computations. Namely, we propose a special device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.
Solving the Hamiltonian path problem with a light-based computer
Venue: arXiv cs.AR 2007
Year: 2007

In this paper we propose a special computational device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.
Hybrid Branching-Time Logics
Venue: arXiv cs.LO 2007
Year: 2007

Hybrid branching-time logics are introduced as extensions of CTL-like logics with state variables and the downarrow-binder. Following recent work in the linear framework, only logics with a single variable are considered. The expressive power and the complexity of satisfiability of the resulting logics is investigated. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME-complete. These branching-time logics range from strict fragments of CTL to extensions of CTL that can talk about the past and express fairness-properties. The complexity gap relative to CTL is explained by a corresponding succinctness result. To prove the upper bound, the automata-theoretic approach to branching-time logics is extended to hybrid logics, showing that non-emptiness of alternating one-pebble Buchi tree automata is 2EXPTIME-complete.
Computational Simulation and 3D Virtual Reality Engineering Tools for Dynamical Modeling and Imaging of Composite Nanomaterials
Venue: arXiv cs.CE 2007
Year: 2007

An adventure at engineering design and modeling is possible with a Virtual Reality Environment (VRE) that uses multiple computer-generated media to let a user experience situations that are temporally and spatially prohibiting. In this paper, an approach to developing some advanced architecture and modeling tools is presented to allow multiple frameworks work together while being shielded from the application program. This architecture is being developed in a framework of workbench interactive tools for next generation nanoparticle-reinforced damping/dynamic systems. Through the use of system, an engineer/programmer can respectively concentrate on tailoring an engineering design concept of novel system and the application software design while using existing databases/software outputs.
On Edge-Disjoint Pairs Of Matchings
Venue: arXiv cs.DM 2007
Year: 2007

For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for |M|/|H|.
Lower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Frechet Distance
Venue: arXiv cs.CG 2007
Year: 2007

We give lower bounds for the combinatorial complexity of the Voronoi diagram of polygonal curves under the discrete Frechet distance. We show that the Voronoi diagram of n curves in R^d with k vertices each, has complexity Omega(n^{dk}) for dimension d=1,2 and Omega(n^{d(k-1)+2}) for d>2.
Exact Cover with light
Venue: arXiv cs.AR 2007
Year: 2007

We suggest a new optical solution for solving the YES/NO version of the Exact Cover problem by using the massive parallelism of light. The idea is to build an optical device which can generate all possible solutions of the problem and then to pick the correct one. In our case the device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. The nodes are connected by arcs in a special way which lets us to generate all possible covers (exact or not) of the given set. For selecting the correct solution we assign to each item, from the set to be covered, a special integer number. These numbers will actually represent delays induced to light when it passes through arcs. The solution is represented as a subray arriving at a certain moment in the destination node. This will tell us if an exact cover does exist or not.
Derivative of BICM Mutual Information
Venue: arXiv cs.IT 2007
Year: 2007

In this letter we determine the derivative of the mutual information corresponding to bit-interleaved coded modulation systems. The derivative follows as a linear combination of minimum-mean-squared error functions of coded modulation sets. The result finds applications to the analysis of communications systems in the wideband regime and to the design of power allocation over parallel channels.
Attribute Estimation and Testing Quasi-Symmetry
Venue: arXiv cs.CC 2007
Year: 2007

A Boolean function is symmetric if it is invariant under all permutations of its arguments; it is quasi-symmetric if it is symmetric with respect to the arguments on which it actually depends. We present a test that accepts every quasi-symmetric function and, except with an error probability at most delta>0, rejects every function that differs from every quasi-symmetric function on at least a fraction epsilon>0 of the inputs. For a function of n arguments, the test probes the function at O((n/epsilon)\log(n/delta)) inputs. Our quasi-symmetry test acquires information concerning the arguments on which the function actually depends. To do this, it employs a generalization of the property testing paradigm that we call attribute estimation. Like property testing, attribute estimation uses random sampling to obtain results that have only "one-sided'' errors and that are close to accurate with high probability.
The study of a new gerrymandering methodology
Venue: arXiv cs.CY 2007
Year: 2007

This paper is to obtain a simple dividing-diagram of the congressional districts, where the only limit is that each district should contain the same population if possibly. In order to solve this problem, we introduce three different standards of the "simple" shape. The first standard is that the final shape of the congressional districts should be of a simplest figure and we apply a modified "shortest split line algorithm" where the factor of the same population is considered only. The second standard is that the gerrymandering should ensure the integrity of the current administrative area as the convenience for management. Thus we combine the factor of the administrative area with the first standard, and generate an improved model resulting in the new diagram in which the perimeters of the districts are along the boundaries of some current counties. Moreover, the gerrymandering should consider the geographic features.The third standard is introduced to describe this situation. Finally, it can be proved that the difference between the supporting ratio of a certain party in each district and the average supporting ratio of that particular party in the whole state obeys the Chi-square distribution approximately. Consequently, we can obtain an archetypal formula to check whether the gerrymandering we propose is fair.
Randomized algorithm for the k-server problem on decomposable spaces
Venue: arXiv cs.DS 2007
Year: 2007

We study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(log k). This method yields o(k)-competitive algorithms solving the randomized k-server problem, for some special underlying metric spaces, e.g. HSTs of "small" height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces.
On a constructive characterization of a class of trees related to pairs of disjoint matchings
Venue: arXiv cs.DM 2007
Year: 2007

For a graph consider the pairs of disjoint matchings which union contains as many edges as possible, and define a parameter $α$ which eqauls the cardinality of the largest matching in those pairs. Also, define $\betta$ to be the cardinality of a maximum matching of the graph. We give a constructive characterization of trees which satisfy the $α$=$\betta$ equality. The proof of our main theorem is based on a new decomposition algorithm obtained for trees.
On the AAGL Protocol
Venue: arXiv cs.CR 2007
Year: 2007

Recently the AAGL (Anshel-Anshel-Goldfeld-Lemieux) has been proposed which can be used for RFID tags. We give algorithms for the problem (we call the MSCSPv) on which the security of the AAGL protocol is based upon. Hence we give various attacks for general parameters on the recent AAGL protocol proposed. One of our attacks is a deterministic algorithm which has space complexity and time complexity both atleast exponentialin the worst case. In a better case using a probabilistic algorithm the time complexity canbe O(|XSS(ui')^L5*(n^(1+e)) and the space complexity can be O(|XSS(ui')|^L6), where the element ui' is part of a public key, n is the index of braid group, XSS is a summit type set and e is a constant in a limit. The above shows the AAGL protocol is potentially not significantly more secure as using key agreement protocols based on the conjugacy problem such as the AAG (Anshel-Anshel-Goldfeld) protocol because both protocols can be broken with complexity which do not significantly differ. We think our attacks can be improved.
User Participation in Social Media: Digg Study
Venue: arXiv cs.CY 2007
Year: 2007

The social news aggregator Digg allows users to submit and moderate stories by voting on (digging) them. As is true of most social sites, user participation on Digg is non-uniformly distributed, with few users contributing a disproportionate fraction of content. We studied user participation on Digg, to see whether it is motivated by competition, fueled by user ranking, or social factors, such as community acceptance. For our study we collected activity data of the top users weekly over the course of a year. We computed the number of stories users submitted, dugg or commented on weekly. We report a spike in user activity in September 2006, followed by a gradual decline, which seems unaffected by the elimination of user ranking. The spike can be explained by a controversy that broke out at the beginning of September 2006. We believe that the lasting acrimony that this incident has created led to a decline of top user participation on Digg.
Eigenvalue bounds on the pseudocodeword weight of expander codes
Venue: arXiv cs.IT 2007
Year: 2007

Four different ways of obtaining low-density parity-check codes from expander graphs are considered. For each case, lower bounds on the minimum stopping set size and the minimum pseudocodeword weight of expander (LDPC) codes are derived. These bounds are compared with the known eigenvalue-based lower bounds on the minimum distance of expander codes. Furthermore, Tanner's parity-oriented eigenvalue lower bound on the minimum distance is generalized to yield a new lower bound on the minimum pseudocodeword weight. These bounds are useful in predicting the performance of LDPC codes under graph-based iterative decoding and linear programming decoding.
Complexity of the Minimum Cost Homomorphism Problem for Semicomplete Digraphs with Possible Loops
Venue: arXiv cs.DM 2007
Year: 2007

For digraphs $D$ and $H$, a mapping $f: V(D)\dom V(H)$ is a homomorphism of $D$ to $H$ if $uv\in A(D)$ implies $f(u)f(v)\in A(H).$ For a fixed digraph $H$, the homomorphism problem is to decide whether an input digraph $D$ admits a homomorphism to $H$ or not, and is denoted as HOM($H$). An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in \cite{gutinDAM154a}. If each vertex $u \in V(D)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of the homomorphism $f$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. For each fixed digraph $H$, we have the {\em minimum cost homomorphism problem for} $H$ and denote it as MinHOM($H$). The problem is to decide, for an input graph $D$ with costs $c_i(u),$ $u \in V(D), i\in V(H)$, whether there exists a homomorphism of $D$ to $H$ and, if one exists, to find one of minimum cost. Although a complete dichotomy classification of the complexity of MinHOM($H$) for a digraph $H$ remains an unsolved problem, complete dichotomy classifications for MinHOM($H$) were proved when $H$ is a semicomplete digraph \cite{gutinDAM154b}, and a semicomplete multipartite digraph \cite{gutinDAM}. In these studies, it is assumed that the digraph $H$ is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in \cite{gutinRMS}.\footnote{This paper was submitted to SIAM J. Discrete Math. on October 27, 2006}
The universal evolutionary computer based on super-recursive algorithms of evolvability
Venue: arXiv cs.NE 2007
Year: 2007

This work exposes which mechanisms and procesess in the Nature of evolution compute a function not computable by Turing machine. The computer with intelligence that is not higher than one bacteria population could have, but with efficency to solve the problems that are non-computable by Turing machine is represented. This theoretical construction is called Universal Evolutinary Computer and it is based on the superecursive algorithms of evolvability.
Optimal Sequential Frame Synchronization
Venue: arXiv cs.IT 2007
Year: 2007

We consider the `one-shot frame synchronization problem' where a decoder wants to locate a sync pattern at the output of a channel on the basis of sequential observations. We assume that the sync pattern of length N starts being emitted at a random time within some interval of size A, that characterizes the asynchronism level between the transmitter and the receiver. We show that a sequential decoder can optimally locate the sync pattern, i.e., exactly, without delay, and with probability approaching one as N tends to infinity, if and only if the asynchronism level grows as O(exp(N*k)), with k below the `synchronization threshold,' a constant that admits a simple expression depending on the channel. This constant is the same as the one that characterizes the limit for reliable asynchronous communication, as was recently reported by the authors. If k exceeds the synchronization threshold, any decoder, sequential or non-sequential, locates the sync pattern with an error that tends to one as N tends to infinity. Hence, a sequential decoder can locate a sync pattern as well as the (non-sequential) maximum likelihood decoder that operates on the basis of output sequences of maximum length A+N-1, but with much fewer observations.
The Fuzzy Vault for fingerprints is Vulnerable to Brute Force Attack
Venue: arXiv cs.CV 2007
Year: 2007

The \textit{fuzzy vault} approach is one of the best studied and well accepted ideas for binding cryptographic security into biometric authentication. The vault has been implemented in connection with fingerprint data by Uludag and Jain. We show that this instance of the vault is vulnerable to brute force attack. An interceptor of the vault data can recover both secret and template data using only generally affordable computational resources. Some possible alternatives are then discussed and it is suggested that cryptographic security may be preferable to the one - way function approach to biometric security.
Explicit formulas for efficient multiplication in F_{3^{6m}}
Venue: arXiv cs.CR 2007
Year: 2007

Efficient computation of the Tate pairing is an important part of pairing-based cryptography. Recently with the introduction of the Duursma-Lee method special attention has been given to the fields of characteristic 3. Especially multiplication in F_{3^{6m}}, where m is prime, is an important operation in the above method. In this paper we propose a new method to reduce the number of F_{3^m} multiplications for multiplication in F_{3^{6m}} from 18 in recent implementations to 15. The method is based on the fast Fourier tranmsform and explicit formulas are given. The execution times of our software implementations for F_{3^{6m}} show the efficiency of our results.
Voice Service Support in Mobile Ad Hoc Networks
Venue: arXiv cs.IT 2007
Year: 2007

Mobile ad hoc networks are expected to support voice traffic. The requirement for small delay and jitter of voice traffic poses a significant challenge for medium access control (MAC) in such networks. User mobility makes it more complex due to the associated dynamic path attenuation. In this paper, a MAC scheme for mobile ad hoc networks supporting voice traffic is proposed. With the aid of a low-power probe prior to DATA transmissions, resource reservation is achieved in a distributed manner, thus leading to small delay and jitter. The proposed scheme can automatically adapt to dynamic path attenuation in a mobile environment. Simulation results demonstrate the effectiveness of the proposed scheme.
Multi and Independent Block Approach in Public Cluster
Venue: arXiv cs.DC 2007
Year: 2007

We present extended multi block approach in the LIPI Public Cluster. The multi block approach enables a cluster to be divided into several independent blocks which run jobs owned by different users simultaneously. Previously, we have maintained the blocks using single master node for all blocks due to efficiency and resource limitations. Following recent advancements and expansion of nodeś number, we have modified the multi block approach with multiple master nodes, each of them is responsible for a single block. We argue that this approach improves the overall performance significantly, for especially data intensive computational works.
An Early Warning System for Bankruptcy Prediction: lessons from the Venezuelan Bank Crisis
Venue: arXiv cs.CE 2007
Year: 2007

During 1993-94 Venezuela experienced a severe banking crisis which ended up with 18 commercial banks intervened by the government. Here we develop an early warning system for detecting credit related bankruptcy through discriminant functions developed on financial and macroeconomic data predating the crisis. A robustness test performed on these functions shows high precision in error estimation. The model calibrated on pre-crisis data could detect abnormal financial tension in the late Banco Capital many months before it was intervened and liquidated.