OpenRaiser/Intern-Atlas huggingface dataset:
Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell
Venue: arXiv cs.DS 2008
Year: 2008

We describe Haskell implementations of interesting combinatorial generation algorithms with focus on boolean functions and logic circuit representations. First, a complete exact combinational logic circuit synthesizer is described as a combination of catamorphisms and anamorphisms. Using pairing and unpairing functions on natural number representations of truth tables, we derive an encoding for Binary Decision Diagrams (BDDs) with the unique property that its boolean evaluation faithfully mimics its structural conversion to a a natural number through recursive application of a matching pairing function. We then use this result to derive ranking and unranking functions for BDDs and reduced BDDs. Finally, a generalization of the encoding techniques to Multi-Terminal BDDs is provided. The paper is organized as a self-contained literate Haskell program, available at http://logic.csci.unt.edu/tarau/research/2008/fBDD.zip . Keywords: exact combinational logic synthesis, binary decision diagrams, encodings of boolean functions, pairing/unpairing functions, ranking/unranking functions for BDDs and MTBDDs, declarative combinatorics in Haskell
Optimally Efficient Prefix Search and Multicast in Structured P2P Networks
Venue: arXiv cs.NI 2008
Year: 2008

Searching in P2P networks is fundamental to all overlay networks. P2P networks based on Distributed Hash Tables (DHT) are optimized for single key lookups, whereas unstructured networks offer more complex queries at the cost of increased traffic and uncertain success rates. Our Distributed Tree Construction (DTC) approach enables structured P2P networks to perform prefix search, range queries, and multicast in an optimal way. It achieves this by creating a spanning tree over the peers in the search area, using only information available locally on each peer. Because DTC creates a spanning tree, it can query all the peers in the search area with a minimal number of messages. Furthermore, we show that the tree depth has the same upper bound as a regular DHT lookup which in turn guarantees fast and responsive runtime behavior. By placing objects with a region quadtree, we can perform a prefix search or a range query in a freely selectable area of the DHT. Our DTC algorithm is DHT-agnostic and works with most existing DHTs. We evaluate the performance of DTC over several DHTs by comparing the performance to existing application-level multicast solutions, we show that DTC sends 30-250% fewer messages than common solutions.
On Bounded Integer Programming
Venue: arXiv cs.CC 2008
Year: 2008

We present an efficient reduction from the Bounded integer programming (BIP) to the Subspace avoiding problem (SAP) in lattice theory. The reduction has some special properties with some interesting consequences. The first is the new upper time bound for BIP, $poly(φ)\cdot n^{n+o(n)}$ (where $n$ and $φ$ are the dimension and the input size of the problem, respectively). This is the best bound up to now for BIP. The second consequence is the proof that #SAP, for some norms, is #P-hard under semi-reductions. It follows that the counting version of the Generalized closest vector problem is also #P-hard under semi-reductions. Furthermore, we also show that under some reasonable assumptions, BIP is solvable in probabilistic time $2^{O(n)}$.
A General Theory of Computational Scalability Based on Rational Functions
Venue: arXiv cs.PF 2008
Year: 2008

The universal scalability law of computational capacity is a rational function C_p = P(p)/Q(p) with P(p) a linear polynomial and Q(p) a second-degree polynomial in the number of physical processors p, that has been long used for statistical modeling and prediction of computer system performance. We prove that C_p is equivalent to the synchronous throughput bound for a machine-repairman with state-dependent service rate. Simpler rational functions, such as Amdahl's law and Gustafson speedup, are corollaries of this queue-theoretic bound. C_p is further shown to be both necessary and sufficient for modeling all practical characteristics of computational scalability.
Personal Semantic Web Through A Space Based Computing Environment
Venue: arXiv cs.NI 2008
Year: 2008

The Semantic Web through technologies such to support the canonical representation information and presenting it to users in a method by which its meaning can be understood or at least communi- cated and interpreted by all parties. As the Semantic Web evolves into more of a computing platform rather than an information platform more dynamic structures, interactions and behaviours will evolve leading to systems which localise and personalise this Dynamic Semantic Web.
Capacity of Symmetric K-User Gaussian Very Strong Interference Channels
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies a symmetric K user Gaussian interference channel with K transmitters and K receivers. A "very strong" interference regime is derived for this channel setup. A "very strong" interference regime is one where the capacity region of the interference channel is the same as the capacity region of the channel with no interference. In this regime, the interference can be perfectly canceled by all the receivers without incurring any rate penalties. A "very strong" interference condition for an example symmetric K user deterministic interference channel is also presented.
Parameterized Telescoping Proves Algebraic Independence of Sums
Venue: arXiv cs.SC 2008
Year: 2008

Usually creative telescoping is used to derive recurrences for sums. In this article we show that the non-existence of a creative telescoping solution, and more generally, of a parameterized telescoping solution, proves algebraic independence of certain types of sums. Combining this fact with summation-theory shows transcendence of whole classes of sums. Moreover, this result throws new light on the question why, e.g., Zeilberger's algorithm fails to find a recurrence with minimal order.
Easily testable logical networks based on a 'widened long flip-flop'
Venue: arXiv cs.AR 2008
Year: 2008

The article describes an attempt to solve at once three basic problems arising at testing a complex digital equipment for defects: 1) the problem of an exponential increasing of the complexity of testing the equipment with the complexity of the equipment; 2) the problem of testing of the tester; 3) the problem of a mutual masking of defects. The proposed solution is nothing more than using certain limitations for connections between usual logical gates. Arbitrary multiple stuck-at-faults are supposed as defects.
Impact of Vehicular Communications Security on Transportation Safety
Venue: arXiv cs.CR 2008
Year: 2008

Transportation safety, one of the main driving forces of the development of vehicular communication (VC) systems, relies on high-rate safety messaging (beaconing). At the same time, there is consensus among authorities, industry, and academia on the need to secure VC systems. With specific proposals in the literature, a critical question must be answered: can secure VC systems be practical and satisfy the requirements of safety applications, in spite of the significant communication and processing overhead and other restrictions security and privacy-enhancing mechanisms impose? To answer this question, we investigate in this paper the following three dimensions for secure and privacy-enhancing VC schemes: the reliability of communication, the processing overhead at each node, and the impact on a safety application. The results indicate that with the appropriate system design, including sufficiently high processing power, applications enabled by secure VC can be in practice as effective as those enabled by unsecured VC.
Secure Neighbor Discovery in Wireless Networks: Formal Investigation of Possibility
Venue: arXiv cs.CR 2008
Year: 2008

Wireless communication enables a broad spectrum of applications, ranging from commodity to tactical systems. Neighbor discovery (ND), that is, determining which devices are within direct radio communication, is a building block of network protocols and applications, and its vulnerability can severely compromise their functionalities. A number of proposals to secure ND have been published, but none have analyzed the problem formally. In this paper, we contribute such an analysis: We build a formal model capturing salient characteristics of wireless systems, most notably obstacles and interference, and we provide a specification of a basic variant of the ND problem. Then, we derive an impossibility result for a general class of protocols we term "time-based protocols," to which many of the schemes in the literature belong. We also identify the conditions under which the impossibility result is lifted. Moreover, we explore a second class of protocols we term "time- and location-based protocols," and prove they can secure ND.
Efficient and Robust Secure Aggregation for Sensor Networks
Venue: arXiv cs.CR 2008
Year: 2008

Wireless Sensor Networks (WSNs) rely on in-network aggregation for efficiency, however, this comes at a price: A single adversary can severely influence the outcome by contributing an arbitrary partial aggregate value. Secure in-network aggregation can detect such manipulation. But as long as such faults persist, no aggregation result can be obtained. In contrast, the collection of individual sensor node values is robust and solves the problem of availability, yet in an inefficient way. Our work seeks to bridge this gap in secure data collection: We propose a system that enhances availability with an efficiency close to that of in-network aggregation. To achieve this, our scheme relies on costly operations to localize and exclude nodes that manipulate the aggregation, but \emph{only} when a failure is detected. The detection of aggregation disruptions and the removal of faulty nodes provides robustness. At the same time, after removing faulty nodes, the WSN can enjoy low cost (secure) aggregation. Thus, the high exclusion cost is amortized, and efficiency increases.
Fast Intrinsic Mode Decomposition and Filtering of Time Series Data
Venue: arXiv cs.NA 2008
Year: 2008

The intrinsic mode function (IMF) provides adaptive function bases for nonlinear and non-stationary time series data. A fast convergent iterative method is introduced in this paper to find the IMF components of the data, the method is faster and more predictable than the Empirical Mode Decomposition method devised by the author of Hilbert Huang Transform. The approach is to iteratively adjust the control points on the data function corresponding to the extrema of the refining IMF, the control points of the residue function are calculated as the median of the straight line segments passing through the data control points, the residue function is then constructed as the cubic spline function of the median points. The initial residue function is simply constructed as the straight line segments passing through the extrema of the first derivative of the data function. The refining IMF is the difference between the data function and the improved residue function. The IMF found reveals all the riding waves in the whole data set. A new data filtering method on frequency and amplitude of IMF is also presented with the similar approach of finding the residue on the part to be filtered out. The program to demonstrate the method is distributed under BSD open source license.
List Decoding of Burst Errors
Venue: arXiv cs.IT 2008
Year: 2008

A generalization of the Reiger bound is presented for the list decoding of burst errors. It is then shown that Reed-Solomon codes attain this bound.
On the Monotonicity of Work Function in k-Server Conjecture
Venue: arXiv cs.DS 2008
Year: 2008

This paper presents a mistake in work function algorithm of k-server conjecture. That is, the monotonicity of the work function is not always true.
The discrete Fourier transform: A canonical basis of eigenfunctions
Venue: arXiv cs.IT 2008
Year: 2008

The discrete Fourier transform (DFT) is an important operator which acts on the Hilbert space of complex valued functions on the ring Z/NZ. In the case where N=p is an odd prime number, we exhibit a canonical basis of eigenvectors for the DFT. The transition matrix from the standard basis to the canonical basis defines a novel transform which we call the "discrete oscillator transform" (DOT for short). Finally, we describe a fast algorithm for computing the DOT in certain cases.
Offloading Cognition onto Cognitive Technology
Venue: arXiv cs.MA 2008
Year: 2008

"Cognizing" (e.g., thinking, understanding, and knowing) is a mental state. Systems without mental states, such as cognitive technology, can sometimes contribute to human cognition, but that does not make them cognizers. Cognizers can offload some of their cognitive functions onto cognitive technology, thereby extending their performance capacity beyond the limits of their own brain power. Language itself is a form of cognitive technology that allows cognizers to offload some of their cognitive functions onto the brains of other cognizers. Language also extends cognizers' individual and joint performance powers, distributing the load through interactive and collaborative cognition. Reading, writing, print, telecommunications and computing further extend cognizers' capacities. And now the web, with its network of cognizers, digital databases and software agents, all accessible anytime, anywhere, has become our 'Cognitive Commons,' in which distributed cognizers and cognitive technology can interoperate globally with a speed, scope and degree of interactivity inconceivable through local individual cognition alone. And as with language, the cognitive tool par excellence, such technological changes are not merely instrumental and quantitative: they can have profound effects on how we think and encode information, on how we communicate with one another, on our mental states, and on our very nature.
Critique du rapport signal à bruit en communications numériques -- Questioning the signal to noise ratio in digital communications
Venue: arXiv cs.IT 2008
Year: 2008

The signal to noise ratio, which plays such an important rôle in information theory, is shown to become pointless for digital communications where the demodulation is achieved via new fast estimation techniques. Operational calculus, differential algebra, noncommutative algebra and nonstandard analysis are the main mathematical tools.
On the strength of proof-irrelevant type theories
Venue: arXiv cs.LO 2008
Year: 2008

We present a type theory with some proof-irrelevance built into the conversion rule. We argue that this feature is useful when type theory is used as the logical formalism underlying a theorem prover. We also show a close relation with the subset types of the theory of PVS. We show that in these theories, because of the additional extentionality, the axiom of choice implies the decidability of equality, that is, almost classical logic. Finally we describe a simple set-theoretic semantics.
The Stochastic Logarithmic Norm for Stability Analysis of Stochastic Differential Equations
Venue: arXiv cs.NA 2008
Year: 2008

To analyze the stability of Itô stochastic differential equations with multiplicative noise, we introduce the stochastic logarithmic norm. The logarithmic norm was originally introduced by G. Dahlquist in 1958 as a tool to study the growth of solutions to ordinary differential equations and for estimating the error growth in discretization methods for their approximate solutions. We extend the concept to the stability analysis of Itô stochastic differential equations with multiplicative noise. Stability estimates for linear Itô SDEs using the one, two and $\infty$-norms in the $l$-th mean, where $1 \leq l < \infty $, are derived and the application of the stochastic logarithmic norm is illustrated with examples.
Underwater Acoustic Networks: Channel Models and Network Coding based Lower Bound to Transmission Power for Multicast
Venue: arXiv cs.IT 2008
Year: 2008

The goal of this paper is two-fold. First, to establish a tractable model for the underwater acoustic channel useful for network optimization in terms of convexity. Second, to propose a network coding based lower bound for transmission power in underwater acoustic networks, and compare this bound to the performance of several network layer schemes. The underwater acoustic channel is characterized by a path loss that depends strongly on transmission distance and signal frequency. The exact relationship among power, transmission band, distance and capacity for the Gaussian noise scenario is a complicated one. We provide a closed-form approximate model for 1) transmission power and 2) optimal frequency band to use, as functions of distance and capacity. The model is obtained through numerical evaluation of analytical results that take into account physical models of acoustic propagation loss and ambient noise. Network coding is applied to determine a lower bound to transmission power for a multicast scenario, for a variety of multicast data rates and transmission distances of interest for practical systems, exploiting physical properties of the underwater acoustic channel. The results quantify the performance gap in transmission power between a variety of routing and network coding schemes and the network coding based lower bound. We illustrate results numerically for different network scenarios.
Network Tomography Based on Additive Metrics
Venue: arXiv cs.NI 2008
Year: 2008

Inference of the network structure (e.g., routing topology) and dynamics (e.g., link performance) is an essential component in many network design and management tasks. In this paper we propose a new, general framework for analyzing and designing routing topology and link performance inference algorithms using ideas and tools from phylogenetic inference in evolutionary biology. The framework is applicable to a variety of measurement techniques. Based on the framework we introduce and develop several polynomial-time distance-based inference algorithms with provable performance. We provide sufficient conditions for the correctness of the algorithms. We show that the algorithms are consistent (return correct topology and link performance with an increasing sample size) and robust (can tolerate a certain level of measurement errors). In addition, we establish certain optimality properties of the algorithms (i.e., they achieve the optimal $l_\infty$-radius) and demonstrate their effectiveness via model simulation.
Colliding Message Pairs for 23 and 24-step SHA-512
Venue: arXiv cs.CR 2008
Year: 2008

Recently, Indesteege et al. [1] had described attacks against 23 and 24-step SHA-512 at SAC '08. Their attacks are based on the differential path by Nikolic and Biryukov [2]. The reported complexities are $2^{44.9}$ and $2^{53}$ calls to the respective step reduced SHA-512 hash function. They provided colliding message pairs for 23-step SHA-512 but did not provide a colliding message pair for 24-step SHA-512. In this note we provide a colliding message pair for 23-step SHA-512 and the first colliding message pair for 24-step SHA-512. Our attacks use the differential path first described by Sanadhya and Sarkar at ACISP '08 [3]. The complexities of our attacks are $2^{16.5}$ and $2^{34.5}$ calls to the respective step reduced SHA-512 hash function. Complete details of the attacks will be provided in an extended version of this note.
Foundations of the Pareto Iterated Local Search Metaheuristic
Venue: arXiv cs.AI 2008
Year: 2008

The paper describes the proposition and application of a local search metaheuristic for multi-objective optimization problems. It is based on two main principles of heuristic search, intensification through variable neighborhoods, and diversification through perturbations and successive iterations in favorable regions of the search space. The concept is successfully tested on permutation flow shop scheduling problems under multiple objectives. While the obtained results are encouraging in terms of their quality, another positive attribute of the approach is its' simplicity as it does require the setting of only very few parameters. The implementation of the Pareto Iterated Local Search metaheuristic is based on the MOOPPS computer system of local search heuristics for multi-objective scheduling which has been awarded the European Academic Software Award 2002 in Ronneby, Sweden (http://www.easa-award.net/, http://www.bth.se/llab/easa_2002.nsf)
Genetic Algorithms for multiple objective vehicle routing
Venue: arXiv cs.AI 2008
Year: 2008

The talk describes a general approach of a genetic algorithm for multiple objective optimization problems. A particular dominance relation between the individuals of the population is used to define a fitness operator, enabling the genetic algorithm to adress even problems with efficient, but convex-dominated alternatives. The algorithm is implemented in a multilingual computer program, solving vehicle routing problems with time windows under multiple objectives. The graphical user interface of the program shows the progress of the genetic algorithm and the main parameters of the approach can be easily modified. In addition to that, the program provides powerful decision support to the decision maker. The software has proved it's excellence at the finals of the European Academic Software Award EASA, held at the Keble college/ University of Oxford/ Great Britain.
Agent Models of Political Interactions
Venue: arXiv cs.AI 2008
Year: 2008

Looks at state interactions from an agent based AI perspective to see state interactions as an example of emergent intelligent behavior. Exposes basic principles of game theory.
Rational Generating Functions and Integer Programming Games
Venue: arXiv cs.GT 2008
Year: 2008

We explore the computational complexity of computing pure Nash equilibria for a new class of strategic games called integer programming games with difference of piecewise linear convex payoffs. Integer programming games are games where players' action sets are integer points inside of polytopes. Using recent results from the study of short rational generating functions for encoding sets of integer points pioneered by Alexander Barvinok, we present efficient algorithms for enumerating all pure Nash equilibria, and other computations of interest, such as the pure price of anarchy, and pure threat point, when the dimension and number of "convex" linear pieces in the payoff functions are fixed. Sequential games where a leader is followed by competing followers (a Stackelberg--Nash setting) are also considered.
Microcontroller-based System for Modular Networked Robot
Venue: arXiv cs.RO 2008
Year: 2008

A prototype of modular networked robot for autonomous monitoring works with full control over web through wireless connection has been developed. The robot is equipped with a particular set of built-in analyzing tools and appropriate censors, depending on its main purposes, to enable self-independent and real-time data acquisition and processing. The paper is focused on the microcontroller-based system to realize the modularity. The whole system is divided into three modules : main unit, data acquisition and data processing, while the analyzed results and all aspects of control and monitoring systems are fully accessible over an integrated web-interface. This concept leads to some unique features : enhancing flexibility due to enabling partial replacement of the modules according to user needs, easy access over web for remote users, and low development and maintenance cost due to software dominated components.