OpenRaiser/Intern-Atlas huggingface dataset:
The Fast Fibonacci Decompression Algorithm
Venue: arXiv cs.PF 2007
Year: 2007

Data compression has been widely applied in many data processing areas. Compression methods use variable-size codes with the shorter codes assigned to symbols or groups of symbols that appear in the data frequently. Fibonacci coding, as a representative of these codes, is used for compressing small numbers. Time consumption of a decompression algorithm is not usually as important as the time of a compression algorithm. However, efficiency of the decompression may be a critical issue in some cases. For example, a real-time compression of tree data structures follows this issue. Tree's pages are decompressed during every reading from a secondary storage into the main memory. In this case, the efficiency of a decompression algorithm is extremely important. We have developed a Fast Fibonacci decompression for this purpose. Our approach is up to $3.5\times$ faster than the original implementation.
A Universal Kernel for Learning Regular Languages
Venue: arXiv cs.LG 2007
Year: 2007

We give a universal kernel that renders all the regular languages linearly separable. We are not able to compute this kernel efficiently and conjecture that it is intractable, but we do have an efficient $\eps$-approximation.
Birthday attack to discrete logarithm
Venue: arXiv cs.CR 2007
Year: 2007

The discrete logarithm in a finite group of large order has been widely applied in public key cryptosystem. In this paper, we will present a probabilistic algorithm for discrete logarithm.
Discrete Nondeterminism and Nash Equilibria for Strategy-Based Games
Venue: arXiv cs.GT 2007
Year: 2007

Several notions of game enjoy a Nash-like notion of equilibrium without guarantee of existence. There are different ways of weakening a definition of Nash-like equilibrium in order to guarantee the existence of a weakened equilibrium. Nash's approach to the problem for strategic games is probabilistic, \textit{i.e.} continuous, and static. CP and BR approaches for CP and BR games are discrete and dynamic. This paper proposes an approach that lies between those two different approaches: a discrete and static approach. multi strategic games are introduced as a formalism that is able to express both sequential and simultaneous decision-making, which promises a good modelling power. multi strategic games are a generalisation of strategic games and sequential graph games that still enjoys a Cartesian product structure, \textit{i.e.} where agent actually choose their strategies. A pre-fixed point result allows guaranteeing existence of discrete and non deterministic equilibria. On the one hand, these equilibria can be computed with polynomial (low) complexity. On the other hand, they are effective in terms of recommendation, as shown by a numerical example.
Program algebra with a jump-shift instruction
Venue: arXiv cs.PL 2007
Year: 2007

We study sequential programs that are instruction sequences with jump-shift instructions in the setting of PGA (ProGram Algebra). Jump-shift instructions preceding a jump instruction increase the position to jump to. The jump-shift instruction is not found in programming practice. Its merit is that the expressive power of PGA extended with the jump-shift instruction, is not reduced if the reach of jump instructions is bounded. This is used to show that there exists a finite-state execution mechanism that by making use of a counter can produce each finite-state thread from some program that is a finite or periodic infinite sequence of instructions from a finite set.
Conceptions et usages des plates-formes de formation, Revue Sciences et Technologies de l'Information et de la Communication pour l'Éducation et la Formation
Venue: arXiv cs.HC 2007
Year: 2007

Educative platforms are at the heart of the development of online education. They can not only be reduced to technological aspects. Underlying models impact teaching and learning from the preparing of lessons to the learning sessions. Research related to these platforms are numerous and their stakes are important. For these reasons, we launched a call to a special issue on "Designs and uses of educative platforms" An educative platform is a computer system designed to automate various functions relating to the organization of the course, to the management of their content, to the monitoring of learners and supervision of persons in charge of various formations (Office de la langue française, 2005). So educative platforms are Learning Management Systems (LMS) which are specific to education contexts.
Conception d'outils de communication spécifiques au contexte éducatif
Venue: arXiv cs.HC 2007
Year: 2007

In a distance learning context, providing usual communication tools (forum, chat, ...) is not always enough to create efficient interactions between learners and to favour collective knowledge building. A solution consists in setting-up collective activities which encourage learners to communicate. But, even in that case, tools can sometimes become a barrier to communication. We present in this paper examples of specific tools that are designed in order to favour and to guide communications in an educational context, but also to foster interactions during learning activities that are not inherently collaborative. We describe synchronous communication tools (semi-structured chat), asynchronous tools (temporally structured forum, contextual forum) and a system which promotes mutual aid between learners.
A case study of the difficulty of quantifier elimination in constraint databases: the alibi query in moving object databases
Venue: arXiv cs.LO 2007
Year: 2007

In the constraint database model, spatial and spatio-temporal data are stored by boolean combinations of polynomial equalities and inequalities over the real numbers. The relational calculus augmented with polynomial constraints is the standard first-order query language for constraint databases. Although the expressive power of this query language has been studied extensively, the difficulty of the efficient evaluation of queries, usually involving some form of quantifier elimination, has received considerably less attention. The inefficiency of existing quantifier-elimination software and the intrinsic difficulty of quantifier elimination have proven to be a bottle-neck for for real-world implementations of constraint database systems. In this paper, we focus on a particular query, called the \emph{alibi query}, that asks whether two moving objects whose positions are known at certain moments in time, could have possibly met, given certain speed constraints. This query can be seen as a constraint database query and its evaluation relies on the elimination of a block of three existential quantifiers. Implementations of general purpose elimination algorithms are in the specific case, for practical purposes, too slow in answering the alibi query and fail completely in the parametric case. The main contribution of this paper is an analytical solution to the parametric alibi query, which can be used to answer this query in the specific case in constant time. We also give an analytic solution to the alibi query at a fixed moment in time. The solutions we propose are based on geometric argumentation and they illustrate the fact that some practical problems require creative solutions, where at least in theory, existing systems could provide a solution.
Study of conditions of use of E-services accessible to visually disabled persons
Venue: arXiv cs.HC 2007
Year: 2007

The aim of this paper is to determine the expectations that French-speaking disabled persons have for electronic administrative sites (utility). At the same time, it is a matter of identifying the difficulties of use that the manipulation of these E-services poses concretely for blind people (usability) and of evaluating the psychosocial impacts on the way of life of these people with specific needs. We show that the lack of numerical accessibility is likely to accentuate the social exclusion of which these people are victim by establishing a numerical glass ceiling.
Optimal codes for correcting a single (wrap-around) burst of errors
Venue: arXiv cs.IT 2007
Year: 2007

In 2007, Martinian and Trott presented codes for correcting a burst of erasures with a minimum decoding delay. Their construction employs [n,k] codes that can correct any burst of erasures (including wrap-around bursts) of length n-k. The raised the question if such [n,k] codes exist for all integers k and n with 1<= k <= n and all fields (in particular, for the binary field). In this note, we answer this question affirmatively by giving two recursive constructions and a direct one.
A Dynamic ID-based Remote User Authentication Scheme
Venue: arXiv cs.CR 2007
Year: 2007

Password-based authentication schemes are the most widely used techniques for remote user authentication. Many static ID-based remote user authentication schemes both with and without smart cards have been proposed. Most of the schemes do not allow the users to choose and change their passwords, and maintain a verifier table to verify the validity of the user login. In this paper we present a dynamic ID-based remote user authentication scheme using smart cards. Our scheme allows the users to choose and change their passwords freely, and do not maintain any verifier table. The scheme is secure against ID-theft, and can resist the reply attacks, forgery attacks, guessing attacks, insider attacks and stolen verifier attacks.
Exact and Approximate Expressions for the Probability of Undetected Error of Varshamov-Tenengol'ts Codes
Venue: arXiv cs.IT 2007
Year: 2007

Computation of the undetected error probability for error correcting codes over the Z-channel is an important issue, explored only in part in previous literature. In this paper we consider the case of Varshamov-Tenengol'ts codes, by presenting some analytical, numerical, and heuristic methods for unveiling this additional feature. Possible comparisons with Hamming codes are also shown and discussed.
Human-Machine Symbiosis, 50 Years On
Venue: arXiv cs.DC 2007
Year: 2007

Licklider advocated in 1960 the construction of computers capable of working symbiotically with humans to address problems not easily addressed by humans working alone. Since that time, many of the advances that he envisioned have been achieved, yet the time spent by human problem solvers in mundane activities remains large. I propose here four areas in which improved tools can further advance the goal of enhancing human intellect: services, provenance, knowledge communities, and automation of problem-solving protocols.
A New Theoretic Foundation for Cross-Layer Optimization
Venue: arXiv cs.NI 2007
Year: 2007

Cross-layer optimization solutions have been proposed in recent years to improve the performance of network users operating in a time-varying, error-prone wireless environment. However, these solutions often rely on ad-hoc optimization approaches, which ignore the different environmental dynamics experienced at various layers by a user and violate the layered network architecture of the protocol stack by requiring layers to provide access to their internal protocol parameters to other layers. This paper presents a new theoretic foundation for cross-layer optimization, which allows each layer to make autonomous decisions individually, while maximizing the utility of the wireless user by optimally determining what information needs to be exchanged among layers. Hence, this cross-layer framework does not change the current layered architecture. Specifically, because the wireless user interacts with the environment at various layers of the protocol stack, the cross-layer optimization problem is formulated as a layered Markov decision process (MDP) in which each layer adapts its own protocol parameters and exchanges information (messages) with other layers in order to cooperatively maximize the performance of the wireless user. The message exchange mechanism for determining the optimal cross-layer transmission strategies has been designed for both off-line optimization and on-line dynamic adaptation. We also show that many existing cross-layer optimization algorithms can be formulated as simplified, sub-optimal, versions of our layered MDP framework.
On Lower Bound for W(K_{2n})
Venue: arXiv cs.DM 2007
Year: 2007

The lower bound W(K_{2n})>=3n-2 is proved for the greatest possible number of colors in an interval edge coloring of the complete graph K_{2n}.
Is the injectivity of the global function of a cellular automaton in the hyperbolic plane undecidable?
Venue: arXiv cs.DM 2007
Year: 2007

In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994. In the present paper, we give a partial answer: when the configurations are restricted to a certain condition, the problem is undecidable.
Stop That Subversive Spreadsheet!
Venue: arXiv cs.GL 2007
Year: 2007

This paper documents the formation of the European Spreadsheet Risks Interest Group (EuSpRIG www.eusprig.org) and outlines some of the research undertaken and reported upon by interested parties in EuSpRIG publications
A New Lower Bound for A(17,6,6)
Venue: arXiv cs.IT 2007
Year: 2007

We construct a record-breaking binary code of length 17, minimal distance 6, constant weight 6, and containing 113 codewords.
Evolving XSLT stylesheets
Venue: arXiv cs.NE 2007
Year: 2007

This paper introduces a procedure based on genetic programming to evolve XSLT programs (usually called stylesheets or logicsheets). XSLT is a general purpose, document-oriented functional language, generally used to transform XML documents (or, in general, solve any problem that can be coded as an XML document). The proposed solution uses a tree representation for the stylesheets as well as diverse specific operators in order to obtain, in the studied cases and a reasonable time, a XSLT stylesheet that performs the transformation. Several types of representation have been compared, resulting in different performance and degree of success.
Optimal Memoryless Encoding for Low Power Off-Chip Data Buses
Venue: arXiv cs.AR 2007
Year: 2007

Off-chip buses account for a significant portion of the total system power consumed in embedded systems. Bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. In this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. Our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful.
Convex sets in acyclic digraphs
Venue: arXiv cs.DM 2007
Year: 2007

A non-empty set $X$ of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by $X$ is connected and it is called convex if no two vertices of $X$ are connected by a directed path in which some vertices are not in $X$. The set of convex sets (connected convex sets) of an acyclic digraph $D$ is denoted by $\sco(D)$ ($\scc(D)$) and its size by $\co(D)$ ($\cc(D)$). Gutin, Johnstone, Reddington, Scott, Soleimanfallah, and Yeo (Proc. ACiD'07) conjectured that the sum of the sizes of all (connected) convex sets in $D$ equals $Θ(n \cdot \co(D))$ ($Θ(n \cdot \cc(D))$) where $n$ is the order of $D$. In this paper we exhibit a family of connected acyclic digraphs with $\sum_{C\in \sco(D)}|C| = o(n\cdot \co(D))$ and $\sum_{C\in \scc(D)}|C| = o(n\cdot \cc(D))$. We also show that the number of connected convex sets of order $k$ in any connected acyclic digraph of order $n$ is at least $n-k+1$. This is a strengthening of a theorem by Gutin and Yeo.
Density estimation in linear time
Venue: arXiv cs.LG 2007
Year: 2007

We consider the problem of choosing a density estimate from a set of distributions F, minimizing the L1-distance to an unknown distribution (Devroye, Lugosi 2001). Devroye and Lugosi analyze two algorithms for the problem: Scheffe tournament winner and minimum distance estimate. The Scheffe tournament estimate requires fewer computations than the minimum distance estimate, but has strictly weaker guarantees than the latter. We focus on the computational aspect of density estimation. We present two algorithms, both with the same guarantee as the minimum distance estimate. The first one, a modification of the minimum distance estimate, uses the same number (quadratic in |F|) of computations as the Scheffe tournament. The second one, called ``efficient minimum loss-weight estimate,'' uses only a linear number of computations, assuming that F is preprocessed. We also give examples showing that the guarantees of the algorithms cannot be improved and explore randomized algorithms for density estimation.
Joint Source-Channel Coding Revisited: Information-Spectrum Approach
Venue: arXiv cs.IT 2007
Year: 2007

Given a general source with countably infinite source alphabet and a general channel with arbitrary abstract channel input/channel output alphabets, we study the joint source-channel coding problem from the information-spectrum point of view. First, we generalize Feinstein's lemma (direct part) and Verdu-Han's lemma (converse part) so as to be applicable to the general joint source-channel coding problem. Based on these lemmas, we establish a sufficient condition as well as a necessary condition for the source to be reliably transmissible over the channel with asymptotically vanishing probability of error. It is shown that our sufficient condition is equivalent to the sufficient condition derived by Vembu, Verdu and Steinberg, whereas our necessary condition is shown to be stronger than or equivalent to the necessary condition derived by them. It turns out, as a direct consequence, that separation principle in a relevantly generalized sense holds for a wide class of sources and channels, as was shown in a quite dfifferent manner by Vembu, Verdu and Steinberg. It should also be remarked that a nice duality is found between our necessary and sufficient conditions, whereas we cannot fully enjoy such a duality between the necessary condition and the sufficient condition by Vembu, Verdu and Steinberg. In addition, we demonstrate a sufficient condition as well as a necessary condition for the epsilon-transmissibility. Finally, the separation theorem of the traditional standard form is shown to hold for the class of sources and channels that satisfy the semi-strong converse property.
Error Rate Analysis for Peaky Signaling over Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the performance of signaling strategies with high peak-to-average power ratio is analyzed over both coherent and noncoherent fading channels. Two modulation schemes, namely on-off phase-shift keying (OOPSK) and on-off frequency-shift keying (OOFSK), are considered. Initially, uncoded systems are analyzed. For OOPSK and OOFSK, the optimal detector structures are identified and analytical expressions for the error probabilities are obtained for arbitrary constellation sizes. Numerical techniques are employed to compute the error probabilities. It is concluded that increasing the peakedness of the signals results in reduced error rates for a given power level and hence equivalently improves the energy efficiency for fixed error probabilities. The coded performance is also studied by analyzing the random coding error exponents achieved by OOPSK and OOFSK signaling.
Computer- and robot-assisted urological surgery
Venue: arXiv cs.OH 2007
Year: 2007

The author reviews the computer and robotic tools available to urologists to help in diagnosis and technical procedures. The first part concerns the contribution of robotics and presents several systems at various stages of development (laboratory prototypes, systems under validation or marketed systems). The second part describes image fusion tools and navigation systems currently under development or evaluation. Several studies on computerized simulation of urological procedures are also presented.
On Exponential Time Lower Bound of Knapsack under Backtracking
Venue: arXiv cs.CC 2007
Year: 2007

M.Aleknovich et al. have recently proposed a model of algorithms, called BT model, which generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model by Woeginger. BT model can be further divided into three kinds of fixed, adaptive and fully adaptive ones. They have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem. Their exact lower bound is $Ω(2^{0.5n}/\sqrt{n})$, in this paper, we slightly improve the exact lower bound to about $Ω(2^{0.69n}/\sqrt{n})$, by the same technique, with related parameters optimized.
Controlling Delay-induced Hopf bifurcation in Internet congestion control system
Venue: arXiv cs.NI 2007
Year: 2007

This paper focuses on Hopf bifurcation control in a dual model of Internet congestion control algorithms which is modeled as a delay differential equation (DDE). By choosing communication delay as a bifurcation parameter, it has been demonstrated that the system loses stability and a Hopf bifurcation occurs when communication delay passes through a critical value. Therefore, a time-delayed feedback control method is applied to the system for delaying the onset of undesirable Hopf bifurcation. Theoretical analysis and numerical simulations confirm that the delayed feedback controller is efficient in controlling Hopf bifurcation in Internet congestion control system. Moreover, the direction of the Hopf bifurcation and the stability of the bifurcating periodic solutions are determinated by applying the center manifold theorem and the normal form theory.
Tighter and Stable Bounds for Marcum Q-Function
Venue: arXiv cs.IT 2007
Year: 2007

This paper proposes new bounds for Marcum Q-function, which prove extremely tight and outperform all the bounds previously proposed in the literature. What is more, the proposed bounds are good and stable both for large values and small values of the parameters of the Marcum Q-function, where the previously introduced bounds are bad and even useless under some conditions. The new bounds are derived by refined approximations for the 0th order modified Bessel function in the integration region of the Marcum Q-function. They should be useful since they are always tight no matter the parameters are large or small.
QIS-XML: A metadata specification for Quantum Information Science
Venue: arXiv cs.SE 2007
Year: 2007

While Quantum Information Science (QIS) is still in its infancy, the ability for quantum based hardware or computers to communicate and integrate with their classical counterparts will be a major requirement towards their success. Little attention however has been paid to this aspect of QIS. To manage and exchange information between systems, today's classic Information Technology (IT) commonly uses the eXtensible Markup Language (XML) and its related tools. XML is composed of numerous specifications related to various fields of expertise. No such global specification however has been defined for quantum computers. QIS-XML is a proposed XML metadata specification for the description of fundamental components of QIS (gates & circuits) and a platform for the development of a hardware independent low level pseudo-code for quantum algorithms. This paper lays out the general characteristics of the QIS-XML specification and outlines practical applications through prototype use cases.
Faster polynomial multiplication via multipoint Kronecker substitution
Venue: arXiv cs.SC 2007
Year: 2007

We give several new algorithms for dense polynomial multiplication based on the Kronecker substitution method. For moderately sized input polynomials, the new algorithms improve on the performance of the standard Kronecker substitution by a sizeable constant, both in theory and in empirical tests.