OpenRaiser/Intern-Atlas huggingface dataset:
Dynamical Neural Network: Information and Topology
Venue: arXiv cs.IR 2005
Year: 2005

A neural network works as an associative memory device if it has large storage capacity and the quality of the retrieval is good enough. The learning and attractor abilities of the network both can be measured by the mutual information (MI), between patterns and retrieval states. This paper deals with a search for an optimal topology, of a Hebb network, in the sense of the maximal MI. We use small-world topology. The connectivity $γ$ ranges from an extremely diluted to the fully connected network; the randomness $ω$ ranges from purely local to completely random neighbors. It is found that, while stability implies an optimal $MI(γ,ω)$ at $γ_{opt}(ω)\to 0$, for the dynamics, the optimal topology holds at certain $γ_{opt}>0$ whenever $0\leqω<0.3$.
Quantitative Models and Implicit Complexity
Venue: arXiv cs.LO 2005
Year: 2005

We give new proofs of soundness (all representable functions on base types lies in certain complexity classes) for Elementary Affine Logic, LFPL (a language for polytime computation close to realistic functional programming introduced by one of us), Light Affine Logic and Soft Affine Logic. The proofs are based on a common semantical framework which is merely instantiated in four different ways. The framework consists of an innovative modification of realizability which allows us to use resource-bounded computations as realisers as opposed to including all Turing computable functions as is usually the case in realizability constructions. For example, all realisers in the model for LFPL are polynomially bounded computations whence soundness holds by construction of the model. The work then lies in being able to interpret all the required constructs in the model. While being the first entirely semantical proof of polytime soundness for light logi cs, our proof also provides a notable simplification of the original already semantical proof of polytime soundness for LFPL. A new result made possible by the semantic framework is the addition of polymorphism and a modality to LFPL thus allowing for an internal definition of inductive datatypes.
Universal Codes as a Basis for Nonparametric Testing of Serial Independence for Time Series
Venue: arXiv cs.IT 2005
Year: 2005

We consider a stationary and ergodic source $p$ generated symbols $x_1 ... x_t$ from some finite set $A$ and a null hypothesis $H_0$ that $p$ is Markovian source with memory (or connectivity) not larger than $m, (m >= 0).$ The alternative hypothesis $H_1$ is that the sequence is generated by a stationary and ergodic source, which differs from the source under $H_0$. In particular, if $m= 0$ we have the null hypothesis $H_0$ that the sequence is generated by Bernoully source (or the hypothesis that $x_1 ...x_t$ are independent.) Some new tests which are based on universal codes and universal predictors, are suggested.
Polynomial Synthesis of Asynchronous Automata
Venue: arXiv cs.CC 2005
Year: 2005

Zielonka's theorem shows that each regular set of Mazurkiewicz traces can be implemented as a system of synchronized processes with a distributed control structure called asynchronous automaton. This paper gives a polynomial algorithm for the synthesis of a non-deterministic asynchronous automaton from a regular Mazurkiewicz trace language. This new construction is based on an unfolding approach that improves the complexity of Zielonka's and Pighizzini's techniques in terms of the number of states.
Security of mobile agents: a new concept of the integrity protection
Venue: arXiv cs.CR 2005
Year: 2005

The recent developments in the mobile technology (mobile phones, middleware) created a need for new methods of protecting the code transmitted through the network. The proposed mechanisms not only secure the compiled program, but also the data, that can be gathered during its "journey". The oldest and the simplest methods are more concentrated on integrity of the code itself and on the detection of unauthorized manipulation. Other, more advanced proposals protect not only the code but also the execution state and the collected data. The paper is divided into two parts. The first one is mostly devoted to different methods of securing the code and protecting its integrity; starting from watermarking and fingerprinting, up to methods designed specially for mobile agent systems: encrypted function, cryptographic traces, time limited black-box security, chained-MAC protocol, publicly-verifiable chained digital signatures The second part presents new concept for providing mobile agents with integrity protection, based on a zero-knowledge proof system.
Lattice Gas Cellular Automata for Computational Fluid Animation
Venue: arXiv cs.GR 2005
Year: 2005

The past two decades showed a rapid growing of physically-based modeling of fluids for computer graphics applications. In this area, a common top down approach is to model the fluid dynamics by Navier-Stokes equations and apply a numerical techniques such as Finite Differences or Finite Elements for the simulation. In this paper we focus on fluid modeling through Lattice Gas Cellular Automata (LGCA) for computer graphics applications. LGCA are discrete models based on point particles that move on a lattice, according to suitable and simple rules in order to mimic a fully molecular dynamics. By Chapman-Enskog expansion, a known multiscale technique in this area, it can be demonstrated that the Navier-Stokes model can be reproduced by the LGCA technique. Thus, with LGCA we get a fluid model that does not require solution of complicated equations. Therefore, we combine the advantage of the low computational cost of LGCA and its ability to mimic the realistic fluid dynamics to develop a new animating framework for computer graphics applications. In this work, we discuss the theoretical elements of our proposal and show experimental results.
Adapting CBPP platforms for instructional use
Venue: arXiv cs.DL 2005
Year: 2005

Commons based peer-production (CBPP) is the de-centralized, net-based approach to the creation and dissemination of information resources. Underlying every CBPP system is a virtual community brought together by an internet tool (such as a web site) and structured by a specific collaboration protocol. In this talk we will argue that the value of such platforms can be leveraged by adapting them for pedagogical purposes. We report on one such recent adaptation. The Noosphere system is a web-based collaboration environment that underlies the popular Planetmath website, a collaboratively written encyclopedia of mathematics licensed under the GNU Free Documentation License (FDL). Recently, the system was used to host a graduate-level mathematics course at Dalhousie University, in Halifax, Canada. The course consisted of regular lectures and assignment problems. The students in the course collaborated on a set of course notes, encapsulating the lecture content and giving solutions of assigned problems. The successful outcome of this experiment demonstrated that a dedicated Noosphere system is well suited for classroom applications. We argue that this ``proof of concept'' experience also strongly suggests that every successful CBPP platform possesses latent pedagogical value.
Multiresolution Kernels
Venue: arXiv cs.LG 2005
Year: 2005

We present in this work a new methodology to design kernels on data which is structured with smaller components, such as text, images or sequences. This methodology is a template procedure which can be applied on most kernels on measures and takes advantage of a more detailed "bag of components" representation of the objects. To obtain such a detailed description, we consider possible decompositions of the original bag into a collection of nested bags, following a prior knowledge on the objects' structure. We then consider these smaller bags to compare two objects both in a detailed perspective, stressing local matches between the smaller bags, and in a global or coarse perspective, by considering the entire bag. This multiresolution approach is likely to be best suited for tasks where the coarse approach is not precise enough, and where a more subtle mixture of both local and global similarities is necessary to compare objects. The approach presented here would not be computationally tractable without a factorization trick that we introduce before presenting promising results on an image retrieval task.
Enhancing Global SLS-Resolution with Loop Cutting and Tabling Mechanisms
Venue: arXiv cs.LO 2005
Year: 2005

Global SLS-resolution is a well-known procedural semantics for top-down computation of queries under the well-founded model. It inherits from SLDNF-resolution the {\em linearity} property of derivations, which makes it easy and efficient to implement using a simple stack-based memory structure. However, like SLDNF-resolution it suffers from the problem of infinite loops and redundant computations. To resolve this problem, in this paper we develop a new procedural semantics, called {\em SLTNF-resolution}, by enhancing Global SLS-resolution with loop cutting and tabling mechanisms. SLTNF-resolution is sound and complete w.r.t. the well-founded semantics for logic programs with the bounded-term-size property, and is superior to existing linear tabling procedural semantics such as SLT-resolution.
Upper Bound on the Number of Vertices of Polyhedra with $0,1$-Constraint Matrices
Venue: arXiv cs.CG 2005
Year: 2005

In this note we show that the maximum number of vertices in any polyhedron $P=\{x\in \mathbb{R}^d : Ax\leq b\}$ with $0,1$-constraint matrix $A$ and a real vector $b$ is at most $d!$.
Inferring AS Relationships: Dead End or Lively Beginning?
Venue: arXiv cs.NI 2005
Year: 2005

Recent techniques for inferring business relationships between ASs have yielded maps that have extremely few invalid BGP paths in the terminology of Gao. However, some relationships inferred by these newer algorithms are incorrect, leading to the deduction of unrealistic AS hierarchies. We investigate this problem and discover what causes it. Having obtained such insight, we generalize the problem of AS relationship inference as a multiobjective optimization problem with node-degree-based corrections to the original objective function of minimizing the number of invalid paths. We solve the generalized version of the problem using the semidefinite programming relaxation of the MAX2SAT problem. Keeping the number of invalid paths small, we obtain a more veracious solution than that yielded by recent heuristics.
FPL Analysis for Adaptive Bandits
Venue: arXiv cs.LG 2005
Year: 2005

A main problem of "Follow the Perturbed Leader" strategies for online decision problems is that regret bounds are typically proven against oblivious adversary. In partial observation cases, it was not clear how to obtain performance guarantees against adaptive adversary, without worsening the bounds. We propose a conceptually simple argument to resolve this problem. Using this, a regret bound of O(t^(2/3)) for FPL in the adversarial multi-armed bandit problem is shown. This bound holds for the common FPL variant using only the observations from designated exploration rounds. Using all observations allows for the stronger bound of O(t^(1/2)), matching the best bound known so far (and essentially the known lower bound) for adversarial bandits. Surprisingly, this variant does not even need explicit exploration, it is self-stabilizing. However the sampling probabilities have to be either externally provided or approximated to sufficient accuracy, using O(t^2 log t) samples in each step.
Termination of rewriting strategies: a generic approach
Venue: arXiv cs.LO 2005
Year: 2005

We propose a generic termination proof method for rewriting under strategies, based on an explicit induction on the termination property. Rewriting trees on ground terms are modeled by proof trees, generated by alternatively applying narrowing and abstracting steps. The induction principle is applied through the abstraction mechanism, where terms are replaced by variables representing any of their normal forms. The induction ordering is not given a priori, but defined with ordering constraints, incrementally set during the proof. Abstraction constraints can be used to control the narrowing mechanism, well known to easily diverge. The generic method is then instantiated for the innermost, outermost and local strategies.
A Fast Greedy Algorithm for Outlier Mining
Venue: arXiv cs.DB 2005
Year: 2005

The task of outlier detection is to find small groups of data objects that are exceptional when compared with rest large amount of data. In [38], the problem of outlier detection in categorical data is defined as an optimization problem and a local-search heuristic based algorithm (LSA) is presented. However, as is the case with most iterative type algorithms, the LSA algorithm is still very time-consuming on very large datasets. In this paper, we present a very fast greedy algorithm for mining outliers under the same optimization model. Experimental results on real datasets and large synthetic datasets show that: (1) Our algorithm has comparable performance with respect to those state-of-art outlier detection algorithms on identifying true outliers and (2) Our algorithm can be an order of magnitude faster than LSA algorithm.
On parity check collections for iterative erasure decoding that correct all correctable erasure patterns of a given size
Venue: arXiv cs.IT 2005
Year: 2005

Recently there has been interest in the construction of small parity check sets for iterative decoding of the Hamming code with the property that each uncorrectable (or stopping) set of size three is the support of a codeword and hence uncorrectable anyway. Here we reformulate and generalise the problem, and improve on this construction. First we show that a parity check collection that corrects all correctable erasure patterns of size m for the r-th order Hamming code (i.e, the Hamming code with codimension r) provides for all codes of codimension $r$ a corresponding ``generic'' parity check collection with this property. This leads naturally to a necessary and sufficient condition on such generic parity check collections. We use this condition to construct a generic parity check collection for codes of codimension r correcting all correctable erasure patterns of size at most m, for all r and m <= r, thus generalising the known construction for m=3. Then we discussoptimality of our construction and show that it can be improved for m>=3 and r large enough. Finally we discuss some directions for further research.
A Secure Traitor Tracing Scheme against Key Exposure
Venue: arXiv cs.CR 2005
Year: 2005

Copyright protection is a major issue in distributing digital content. On the other hand, improvements to usability are sought by content users. In this paper, we propose a secure {\it traitor tracing scheme against key exposure (TTaKE)} which contains the properties of both a traitor tracing scheme and a forward secure public key cryptosystem. Its structure fits current digital broadcasting systems and it may be useful in preventing traitors from making illegal decoders and in minimizing the damage from accidental key exposure. It can improve usability through these properties.
On the Minimal Pseudo-Codewords of Codes from Finite Geometries
Venue: arXiv cs.IT 2005
Year: 2005

In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Although our numerical results are only for codes of very modest length, they suggest that these code families exhibit an interesting property. Namely, all minimal pseudo-codewords that are not multiples of a minimal codeword have an AWGNC pseudo-weight that is strictly larger than the minimum Hamming weight of the code. This observation has positive consequences not only for LP decoding but also for iterative decoding.
Toward Compact Interdomain Routing
Venue: arXiv cs.NI 2005
Year: 2005

Despite prevailing concerns that the current Internet interdomain routing system will not scale to meet the needs of the 21st century global Internet, networking research has not yet led to the construction of a new routing architecture with satisfactory and mathematically provable scalability characteristics. Worse, continuing empirical trends of the existing routing and topology structure of the Internet are alarming: the foundational principles of the current routing and addressing architecture are an inherently bad match for the naturally evolving structure of Internet interdomain topology. We are fortunate that a sister discipline, theory of distributed computation, has developed routing algorithms that offer promising potential for genuinely scalable routing on realistic Internet-like topologies. Indeed, there are many recent breakthroughs in the area of compact routing, which has been shown to drastically outperform, in terms of efficiency and scalability, even the boldest proposals developed in networking research. Many open questions remain, but we believe the applicability of compact routing techniques to Internet interdomain routing is a research area whose potential payoff for the future of networking is too high to ignore.
Simple Maximum-Likelihood Decoding of Generalized First-order Reed-Muller Codes
Venue: arXiv cs.IT 2005
Year: 2005

An efficient decoder for the generalized first-order Reed-Muller code RM_q(1,m) is essential for the decoding of various block-coding schemes for orthogonal frequency-division multiplexing with reduced peak-to-mean power ratio. We present an efficient and simple maximum-likelihood decoding algorithm for RM_q(1,m). It is shown that this algorithm has lower complexity than other previously known maximum-likelihood decoders for RM_q(1,m).
Codes for error detection, good or not good
Venue: arXiv cs.IT 2005
Year: 2005

Linear codes for error detection on a q-ary symmetric channel are studied. It is shown that for given dimension k and minimum distance d, there exists a value μ(d,k) such that if C is a code of length n >= μ(d,k), then neither C nor its dual are good for error detection. For d >> k or k << d good approximations for μ(d,k) are given. A generalization to non-linear codes is also given.
Characterizations of Pseudo-Codewords of LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

An important property of high-performance, low complexity codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message passing algorithms and decoding based on linear programming, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so called fundamental cone in Euclidean space which is a function of a given parity check matrix of a code, rather than of the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental polytope as the Newton polytope of the Hashimoto edge zeta function of the underlying graph.
Algorithms for Discrete Denoising Under Channel Uncertainty
Venue: arXiv cs.IT 2005
Year: 2005

The goal of a denoising algorithm is to reconstruct a signal from its noise-corrupted observations. Perfect reconstruction is seldom possible and performance is measured under a given fidelity criterion. In a recent work, the authors addressed the problem of denoising unknown discrete signals corrupted by a discrete memoryless channel when the channel, rather than being completely known, is only known to lie in some uncertainty set of possible channels. A sequence of denoisers was derived for this case and shown to be asymptotically optimal with respect to a worst-case criterion argued most relevant to this setting. In the present work we address the implementation and complexity of this denoiser for channels parametrized by a scalar, establishing its practicality. We show that for symmetric channels, the problem can be mapped into a convex optimization problem, which can be solved efficiently. We also present empirical results suggesting the potential of these schemes to do well in practice. A key component of our schemes is an estimator of the subset of channels in the uncertainty set that are feasible in the sense of being able to give rise to the noise-corrupted signal statistics for some channel input distribution. We establish the efficiency of this estimator, both algorithmically and experimentally. We also present a modification of the recently developed discrete universal denoiser (DUDE) that assumes a channel based on the said estimator, and show that, in practice, the resulting scheme performs well. For concreteness, we focus on the binary alphabet case and binary symmetric channels, but also discuss the extensions of the algorithms to general finite alphabets and to general channels parameterized by a scalar.
SciBlog : A Tool for Scientific Collaboration
Venue: arXiv cs.CY 2005
Year: 2005

I describe a newly developed online scientific web-log (SciBlog). The online facility consists of several moduls needed in a common and conventional research activity. I show that this enables scientists around the world to perform an online collaboration over the net.
Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes
Venue: arXiv cs.IT 2005
Year: 2005

We describe message-passing and decimation approaches for lossy source coding using low-density generator matrix (LDGM) codes. In particular, this paper addresses the problem of encoding a Bernoulli(0.5) source: for randomly generated LDGM codes with suitably irregular degree distributions, our methods yield performance very close to the rate distortion limit over a range of rates. Our approach is inspired by the survey propagation (SP) algorithm, originally developed by Mezard et al. for solving random satisfiability problems. Previous work by Maneva et al. shows how SP can be understood as belief propagation (BP) for an alternative representation of satisfiability problems. In analogy to this connection, our approach is to define a family of Markov random fields over generalized codewords, from which local message-passing rules can be derived in the standard way. The overall source encoding method is based on message-passing, setting a subset of bits to their preferred values (decimation), and reducing the code.
Re-visiting the One-Time Pad
Venue: arXiv cs.CR 2005
Year: 2005

In 1949, Shannon proved the perfect secrecy of the Vernam cryptographic system,also popularly known as the One-Time Pad (OTP). Since then, it has been believed that the perfectly random and uncompressible OTP which is transmitted needs to have a length equal to the message length for this result to be true. In this paper, we prove that the length of the transmitted OTP which actually contains useful information need not be compromised and could be less than the message length without sacrificing perfect secrecy. We also provide a new interpretation for the OTP encryption by treating the message bits as making True/False statements about the pad, which we define as a private-object. We introduce the paradigm of private-object cryptography where messages are transmitted by verifying statements about a secret-object. We conclude by suggesting the use of Formal Axiomatic Systems for investing N bits of secret.