OpenRaiser/Intern-Atlas huggingface dataset:
Classical Authentication Aided Three-Stage Quantum Protocol
Venue: arXiv cs.CR 2006
Year: 2006

This paper modifies Kak's three-stage protocol so that it can guarantee secure transmission of information. Although avoiding man-in-the-middle attack is our primary objective in the introduction of classical authentication inside the three-stage protocol, we also benefit from the inherent advantages of the chosen classical authentication protocol. We have tried to implement ideas like key distribution center, session key, time-stamp, and nonce, within the quantum cryptography protocol.
Error Exponents and Cutoff Rate for Noncoherent Rician Fading Channels
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, random coding error exponents and cutoff rate are studied for noncoherent Rician fading channels, where neither the receiver nor the transmitter has channel side information. First, it is assumed that the input is subject only to an average power constraint. In this case, a lower bound to the random coding error exponent is considered and the optimal input achieving this lower bound is shown to have a discrete amplitude and uniform phase. If the input is subject to both average and peak power constraints, it is proven that the optimal input achieving the random coding error exponent has again a discrete nature. Finally, the cutoff rate is analyzed, and the optimality of the single-mass input amplitude distribution in the low-power regime is discussed.
Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker bounds
Venue: arXiv cs.IT 2006
Year: 2006

We describe and analyze sparse graphical code constructions for the problems of source coding with decoder side information (the Wyner-Ziv problem), and channel coding with encoder side information (the Gelfand-Pinsker problem). Our approach relies on a combination of low-density parity check (LDPC) codes and low-density generator matrix (LDGM) codes, and produces sparse constructions that are simultaneously good as both source and channel codes. In particular, we prove that under maximum likelihood encoding/decoding, there exist low-density codes (i.e., with finite degrees) from our constructions that can saturate both the Wyner-Ziv and Gelfand-Pinsker bounds.
Network Inference from Co-Occurrences
Venue: arXiv cs.IT 2006
Year: 2006

The recovery of network structure from experimental data is a basic and fundamental problem. Unfortunately, experimental data often do not directly reveal structure due to inherent limitations such as imprecision in timing or other observation mechanisms. We consider the problem of inferring network structure in the form of a directed graph from co-occurrence observations. Each observation arises from a transmission made over the network and indicates which vertices carry the transmission without explicitly conveying their order in the path. Without order information, there are an exponential number of feasible graphs which agree with the observed data equally well. Yet, the basic physical principles underlying most networks strongly suggest that all feasible graphs are not equally likely. In particular, vertices that co-occur in many observations are probably closely connected. Previous approaches to this problem are based on ad hoc heuristics. We model the experimental observations as independent realizations of a random walk on the underlying graph, subjected to a random permutation which accounts for the lack of order information. Treating the permutations as missing data, we derive an exact expectation-maximization (EM) algorithm for estimating the random walk parameters. For long transmission paths the exact E-step may be computationally intractable, so we also describe an efficient Monte Carlo EM (MCEM) algorithm and derive conditions which ensure convergence of the MCEM algorithm with high probability. Simulations and experiments with Internet measurements demonstrate the promise of this approach.
Parsing Transformative LR(1) Languages
Venue: arXiv cs.PL 2006
Year: 2006

We consider, as a means of making programming languages more flexible and powerful, a parsing algorithm in which the parser may freely modify the grammar while parsing. We are particularly interested in a modification of the canonical LR(1) parsing algorithm in which, after the reduction of certain productions, we examine the source sentence seen so far to determine the grammar to use to continue parsing. A naive modification of the canonical LR(1) parsing algorithm along these lines cannot be guaranteed to halt; as a result, we develop a test which examines the grammar as it changes, stopping the parse if the grammar changes in a way that would invalidate earlier assumptions made by the parser. With this test in hand, we can develop our parsing algorithm and prove that it is correct. That being done, we turn to earlier, related work; the idea of programming languages which can be extended to include new syntactic constructs has existed almost as long as the idea of high-level programming languages. Early efforts to construct such a programming language were hampered by an immature theory of formal languages. More recent efforts to construct transformative languages relied either on an inefficient chain of source-to-source translators; or they have a defect, present in our naive parsing algorithm, in that they cannot be known to halt. The present algorithm does not have these undesirable properties, and as such, it should prove a useful foundation for a new kind of programming language.
An outer bound to the capacity region of the broadcast channel
Venue: arXiv cs.IT 2006
Year: 2006

An outer bound to the capacity region of the two-receiver discrete memoryless broadcast channel is given. The outer bound is tight for all cases where the capacity region is known. When specialized to the case of no common information, this outer bound is contained in the Korner-Marton outer bound. This containment is shown to be strict for the binary skew-symmetric broadcast channel. Thus, this outer bound is in general tighter than all other known outer bounds on the discrete memoryless broadcast channel.
Mapping the Bid Behavior of Conference Referees
Venue: arXiv cs.DL 2006
Year: 2006

The peer-review process, in its present form, has been repeatedly criticized. Of the many critiques ranging from publication delays to referee bias, this paper will focus specifically on the issue of how submitted manuscripts are distributed to qualified referees. Unqualified referees, without the proper knowledge of a manuscript's domain, may reject a perfectly valid study or potentially more damaging, unknowingly accept a faulty or fraudulent result. In this paper, referee competence is analyzed with respect to referee bid data collected from the 2005 Joint Conference on Digital Libraries (JCDL). The analysis of the referee bid behavior provides a validation of the intuition that referees are bidding on conference submissions with regards to the subject domain of the submission. Unfortunately, this relationship is not strong and therefore suggests that there exists other factors beyond subject domain that may be influencing referees to bid for particular submissions.
A Lattice-Based MIMO Broadcast Precoder for Multi-Stream Transmission
Venue: arXiv cs.IT 2006
Year: 2006

Precoding with block diagonalization is an attractive scheme for approaching sum capacity in multiuser multiple input multiple output (MIMO) broadcast channels. This method requires either global channel state information at every receiver or an additional training phase, which demands additional system planning. In this paper we propose a lattice based multi-user precoder that uses block diagonalization combined with pre-equalization and perturbation for the multiuser MIMO broadcast channel. An achievable sum rate of the proposed scheme is derived and used to show that the proposed technique approaches the achievable sum rate of block diagonalization with water-filling but does not require the additional information at the receiver. Monte Carlo simulations with equal power allocation show that the proposed method provides better bit error rate and diversity performance than block diagonalization with a zero-forcing receiver. Additionally, the proposed method shows similar performance to the maximum likelihood receiver but with much lower receiver complexity.
Pseudocodeword weights for non-binary LDPC codes
Venue: arXiv cs.IT 2006
Year: 2006

Pseudocodewords of q-ary LDPC codes are examined and the weight of a pseudocodeword on the q-ary symmetric channel is defined. The weight definition of a pseudocodeword on the AWGN channel is also extended to two-dimensional q-ary modulation such as q-PAM and q-PSK. The tree-based lower bounds on the minimum pseudocodeword weight are shown to also hold for q-ary LDPC codes on these channels.
Understanding Design Fundamentals: How Synthesis and Analysis Drive Creativity, Resulting in Emergence
Venue: arXiv cs.AI 2006
Year: 2006

This paper presents results of an ongoing interdisciplinary study to develop a computational theory of creativity for engineering design. Human design activities are surveyed, and popular computer-aided design methodologies are examined. It is argued that semiotics has the potential to merge and unite various design approaches into one fundamental theory that is naturally interpretable and so comprehensible in terms of computer use. Reviewing related work in philosophy, psychology, and cognitive science provides a general and encompassing vision of the creativity phenomenon. Basic notions of algebraic semiotics are given and explained in terms of design. This is to define a model of the design creative process, which is seen as a process of semiosis, where concepts and their attributes represented as signs organized into systems are evolved, blended, and analyzed, resulting in the development of new concepts. The model allows us to formally describe and investigate essential properties of the design process, namely its dynamics and non-determinism inherent in creative thinking. A stable pattern of creative thought - analogical and metaphorical reasoning - is specified to demonstrate the expressive power of the modeling approach; illustrative examples are given. The developed theory is applied to clarify the nature of emergence in design: it is shown that while emergent properties of a product may influence its creative value, emergence can simply be seen as a by-product of the creative process. Concluding remarks summarize the research, point to some unresolved issues, and outline directions for future work.
Modeling Hypermedia-Based Communication
Venue: arXiv cs.HC 2006
Year: 2006

In this article, we explore two approaches to modeling hypermedia-based communication. It is argued that the classical conveyor-tube framework is not applicable to the case of computer- and Internet- mediated communication. We then present a simple but very general system-theoretic model of the communication process, propose its mathematical interpretation, and derive several formulas, which qualitatively and quantitatively accord with data obtained on-line. The devised theoretical results generalize and correct the Zipf-Mandelbrot law and can be used in information system design. At the paper's end, we give some conclusions and draw implications for future work.
Semantics and Complexity of SPARQL
Venue: arXiv cs.DB 2006
Year: 2006

SPARQL is the W3C candidate recommendation query language for RDF. In this paper we address systematically the formal study of SPARQL, concentrating in its graph pattern facility. We consider for this study a fragment without literals and a simple version of filters which encompasses all the main issues yet is simple to formalize. We provide a compositional semantics, prove there are normal forms, prove complexity bounds, among others that the evaluation of SPARQL patterns is PSPACE-complete, compare our semantics to an alternative operational semantics, give simple and natural conditions when both semantics coincide and discuss optimizations procedures.
Combinational Logic Circuit Design with the Buchberger Algorithm
Venue: arXiv cs.AR 2006
Year: 2006

We detail a procedure for the computation of the polynomial form of an electronic combinational circuit from the design equations in a truth table. The method uses the Buchberger algorithm rather than current traditional methods based on search algorithms. We restrict the analysis to a single output, but the procedure can be generalized to multiple outputs. The procedure is illustrated with the design of a simple arithmetic and logic unit with two 3-bit operands and two control bits.
Intégration de la synthèse mémoire dans l'outil de synthèse d'architecture GAUT Low Power
Venue: arXiv cs.AR 2006
Year: 2006

The systems supporting signal and image applications process large amount of data. That involves an intensive use of the memory which becomes the bottleneck of systems. Memory limits performances and represents a significant proportion of total consumption. In the development high level synthesis tool called GAUT Low Power, we are interested in the synthesis of the memory unit. In this work, we integrate the data storage and data transfert to constraint the high level synthesis of the datapath's execution unit.
A Framework for the Development of Manufacturing Simulators: Towards New Generation of Simulation Systems
Venue: arXiv cs.CE 2006
Year: 2006

In this paper, an attempt is made to systematically discuss the development of simulation systems for manufacturing system design. General requirements on manufacturing simulators are formulated and a framework to address the requirements is suggested. Problems of information representation as an activity underlying simulation are considered. This is to form the necessary mathematical foundation for manufacturing simulations. The theoretical findings are explored through a pilot study. A conclusion about the suitability of the suggested approach to the development of simulation systems for manufacturing system design is made, and implications for future research are described.
A parent-centered radial layout algorithm for interactive graph visualization and animation
Venue: arXiv cs.HC 2006
Year: 2006

We have developed (1) a graph visualization system that allows users to explore graphs by viewing them as a succession of spanning trees selected interactively, (2) a radial graph layout algorithm, and (3) an animation algorithm that generates meaningful visualizations and smooth transitions between graphs while minimizing edge crossings during transitions and in static layouts. Our system is similar to the radial layout system of Yee et al. (2001), but differs primarily in that each node is positioned on a coordinate system centered on its own parent rather than on a single coordinate system for all nodes. Our system is thus easy to define recursively and lends itself to parallelization. It also guarantees that layouts have many nice properties, such as: it guarantees certain edges never cross during an animation. We compared the layouts and transitions produced by our algorithms to those produced by Yee et al. Results from several experiments indicate that our system produces fewer edge crossings during transitions between graph drawings, and that the transitions more often involve changes in local scaling rather than structure. These findings suggest the system has promise as an interactive graph exploration tool in a variety of settings.
From semiotics of hypermedia to physics of semiosis: A view from system theory
Venue: arXiv cs.HC 2006
Year: 2006

Given that theoretical analysis and empirical validation is fundamental to any model, whether conceptual or formal, it is surprising that these two tools of scientific discovery are so often ignored in the contemporary studies of communication. In this paper, we pursued the ideas of a) correcting and expanding the modeling approaches of linguistics, which are otherwise inapplicable (more precisely, which should not but are widely applied), to the general case of hypermedia-based communication, and b) developing techniques for empirical validation of semiotic models, which are nowadays routinely used to explore (in fact, to conjecture about) internal mechanisms of complex systems, yet on a purely speculative basis. This study thus offers two experimentally tested substantive contributions: the formal representation of communication as the mutually-orienting behavior of coupled autonomous systems, and the mathematical interpretation of the semiosis of communication, which together offer a concrete and parsimonious understanding of diverse communication phenomena.
Consecutive Support: Better Be Close!
Venue: arXiv cs.AI 2006
Year: 2006

We propose a new measure of support (the number of occur- rences of a pattern), in which instances are more important if they occur with a certain frequency and close after each other in the stream of trans- actions. We will explain this new consecutive support and discuss how patterns can be found faster by pruning the search space, for instance using so-called parent support recalculation. Both consecutiveness and the notion of hypercliques are incorporated into the Eclat algorithm. Synthetic examples show how interesting phenomena can now be discov- ered in the datasets. The new measure can be applied in many areas, ranging from bio-informatics to trade, supermarkets, and even law en- forcement. E.g., in bio-informatics it is important to find patterns con- tained in many individuals, where patterns close together in one chro- mosome are more significant.
Belief Calculus
Venue: arXiv cs.AI 2006
Year: 2006

In Dempster-Shafer belief theory, general beliefs are expressed as belief mass distribution functions over frames of discernment. In Subjective Logic beliefs are expressed as belief mass distribution functions over binary frames of discernment. Belief representations in Subjective Logic, which are called opinions, also contain a base rate parameter which express the a priori belief in the absence of evidence. Philosophically, beliefs are quantitative representations of evidence as perceived by humans or by other intelligent agents. The basic operators of classical probability calculus, such as addition and multiplication, can be applied to opinions, thereby making belief calculus practical. Through the equivalence between opinions and Beta probability density functions, this also provides a calculus for Beta probability density functions. This article explains the basic elements of belief calculus.
A secure archive for Voice-over-IP conversations
Venue: arXiv cs.CR 2006
Year: 2006

An efficient archive securing the integrity of VoIP-based two-party conversations is presented. The solution is based on chains of hashes and continuously chained electronic signatures. Security is concentrated in a single, efficient component, allowing for a detailed analysis.
Enabling user-driven Checkpointing strategies in Reverse-mode Automatic Differentiation
Venue: arXiv cs.DS 2006
Year: 2006

This paper presents a new functionality of the Automatic Differentiation (AD) tool Tapenade. Tapenade generates adjoint codes which are widely used for optimization or inverse problems. Unfortunately, for large applications the adjoint code demands a great deal of memory, because it needs to store a large set of intermediates values. To cope with that problem, Tapenade implements a sub-optimal version of a technique called checkpointing, which is a trade-off between storage and recomputation. Our long-term goal is to provide an optimal checkpointing strategy for every code, not yet achieved by any AD tool. Towards that goal, we first introduce modifications in Tapenade in order to give the user the choice to select the checkpointing strategy most suitable for their code. Second, we conduct experiments in real-size scientific codes in order to gather hints that help us to deduce an optimal checkpointing strategy. Some of the experimental results show memory savings up to 35% and execution time up to 90%.
Fast and Simple Methods For Computing Control Points
Venue: arXiv cs.CC 2006
Year: 2006

The purpose of this paper is to present simple and fast methods for computing control points for polynomial curves and polynomial surfaces given explicitly in terms of polynomials (written as sums of monomials). We give recurrence formulae w.r.t. arbitrary affine frames. As a corollary, it is amusing that we can also give closed-form expressions in the case of the frame (r, s) for curves, and the frame ((1, 0, 0), (0, 1, 0), (0, 0, 1) for surfaces. Our methods have the same low polynomial (time and space) complexity as the other best known algorithms, and are very easy to implement.
Approximability of Bounded Occurrence Max Ones
Venue: arXiv cs.CC 2006
Year: 2006

We study the approximability of Max Ones when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are included) we give a complete classification when the number of occurrences is three or more and a partial classification when the bound is two. For the non-conservative case we prove that it is either trivial or equivalent to the corresponding conservative problem under polynomial-time many-one reductions.
Security and Non-Repudiation for Voice-Over-IP Conversations
Venue: arXiv cs.CR 2006
Year: 2006

We present a concept to achieve non-repudiation for natural language conversations by electronically signing packet-based, digital, voice communication. Signing a VoIP-based conversation means to protect the integrity and authenticity of the bidirectional data stream and its temporal sequence which together establish the security context of the communication. Our concept is conceptually close to the protocols that embody VoIP and provides a high level of inherent security. It enables signatures over voice as true declarations of will, in principle between unacquainted speakers. We point to trusted computing enabled devices as possible trusted signature terminals for voice communication.
Ten-Year Cross-Disciplinary Comparison of the Growth of Open Access and How it Increases Research Citation Impact
Venue: arXiv cs.DL 2006
Year: 2006

Lawrence (2001)found computer science articles that were openly accessible (OA) on the Web were cited more. We replicated this in physics. We tested 1,307,038 articles published across 12 years (1992-2003) in 10 disciplines (Biology, Psychology, Sociology, Health, Political Science, Economics, Education, Law, Business, Management). A robot trawls the Web for full-texts using reference metadata ISI citation data (signal detectability d'=2.45; bias = 0.52). Percentage OA (relative to total OA + NOA) articles varies from 5%-16% (depending on discipline, year and country) and is slowly climbing annually (correlation r=.76, sample size N=12, probability p < 0.005). Comparing OA and NOA articles in the same journal/year, OA articles have consistently more citations, the advantage varying from 36%-172% by discipline and year. Comparing articles within six citation ranges (0, 1, 2-3, 4-7, 8-15, 16+ citations), the annual percentage of OA articles is growing significantly faster than NOA within every citation range (r > .90, N=12, p < .0005) and the effect is greater with the more highly cited articles (r = .98, N=6, p < .005). Causality cannot be determined from these data, but our prior finding of a similar pattern in physics, where percent OA is much higher (and even approaches 100% in some subfields), makes it unlikely that the OA citation advantage is merely or mostly a self-selection bias (for making only one's better articles OA). Further research will analyze the effect's timing, causal components and relation to other variables.