OpenRaiser/Intern-Atlas huggingface dataset:
Lambda-Free Logical Frameworks
Venue: arXiv cs.LO 2008
Year: 2008

We present the definition of the logical framework TF, the Type Framework. TF is a lambda-free logical framework; it does not include lambda-abstraction or product kinds. We give formal proofs of several results in the metatheory of TF, and show how it can be conservatively embedded in the logical framework LF: its judgements can be seen as the judgements of LF that are in beta-normal, eta-long normal form. We show how several properties, such as adequacy theorems for object theories and the injectivity of constants, can be proven more easily in TF, and then `lifted' to LF.
The F.A.S.T.-Model
Venue: arXiv cs.MA 2008
Year: 2008

A discrete model of pedestrian motion is presented that is implemented in the Floor field- and Agentbased Simulation Tool (F.A.S.T.) which has already been applicated to a variety of real life scenarios.
Analytical correlation of routing table length index and routing path length index in hierarchical routing model
Venue: arXiv cs.NI 2008
Year: 2008

In Kleinrock and Kamoun's paper, the inverse relation of routing table length index and routing path length index in hierarchical routing model is illustrated. In this paper we give the analytical correlation of routing table length index and routing path length index in hierarchical routing model.
Optimal Mechansim Design and Money Burning
Venue: arXiv cs.GT 2008
Year: 2008

Mechanism design is now a standard tool in computer science for aligning the incentives of self-interested agents with the objectives of a system designer. There is, however, a fundamental disconnect between the traditional application domains of mechanism design (such as auctions) and those arising in computer science (such as networks): while monetary transfers (i.e., payments) are essential for most of the known positive results in mechanism design, they are undesirable or even technologically infeasible in many computer systems. Classical impossibility results imply that the reach of mechanisms without transfers is severely limited. Computer systems typically do have the ability to reduce service quality--routing systems can drop or delay traffic, scheduling protocols can delay the release of jobs, and computational payment schemes can require computational payments from users (e.g., in spam-fighting systems). Service degradation is tantamount to requiring that users burn money}, and such ``payments'' can be used to influence the preferences of the agents at a cost of degrading the social surplus. We develop a framework for the design and analysis of money-burning mechanisms to maximize the residual surplus--the total value of the chosen outcome minus the payments required.
Truthful Unsplittable Flow for Large Capacity Networks
Venue: arXiv cs.DS 2008
Year: 2008

In this paper, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests characteristics, and may be dishonest about them. It is worth noting that in game theoretic settings many standard techniques, such as randomized rounding, violate certain monotonicity properties, which are imperative for truthfulness, and therefore cannot be employed. In light of this state of affairs, we design a monotone deterministic algorithm, which is based on a primal-dual machinery, which attains an approximation ratio of $\frac{e}{e-1}$, up to a disparity of $ε$ away. This implies an improvement on the current best truthful mechanism, as well as an improvement on the current best combinatorial algorithm for the problem under consideration. Surprisingly, we demonstrate that any algorithm in the family of reasonable iterative path minimizing algorithms, cannot yield a better approximation ratio. Consequently, it follows that in order to achieve a monotone PTAS, if exists, one would have to exert different techniques. We also consider the large capacities \textit{single-minded multi-unit combinatorial auction problem}. This problem is closely related to the unsplittable flow problem since one can formulate it as a special case of the integer linear program of the unsplittable flow problem. Accordingly, we obtain a comparable performance guarantee by refining the algorithm suggested for the unsplittable flow problem.
Products of Ordinary Differential Operators by Evaluation and Interpolation
Venue: arXiv cs.SC 2008
Year: 2008

It is known that multiplication of linear differential operators over ground fields of characteristic zero can be reduced to a constant number of matrix products. We give a new algorithm by evaluation and interpolation which is faster than the previously-known one by a constant factor, and prove that in characteristic zero, multiplication of differential operators and of matrices are computationally equivalent problems. In positive characteristic, we show that differential operators can be multiplied in nearly optimal time. Theoretical results are validated by intensive experiments.
Fast Conversion Algorithms for Orthogonal Polynomials
Venue: arXiv cs.SC 2008
Year: 2008

We discuss efficient conversion algorithms for orthogonal polynomials. We describe a known conversion algorithm from an arbitrary orthogonal basis to the monomial basis, and deduce a new algorithm of the same complexity for the converse operation.
Decentralized Knowledge and Learning in Strategic Multi-user Communication
Venue: arXiv cs.GT 2008
Year: 2008

Please see the content of this report.
Identifying 'Hidden' Communities of Practice within Electronic Networks: Some Preliminary Premises
Venue: arXiv cs.HC 2008
Year: 2008

This paper examines the possibility of discovering 'hidden' (potential) Communities of Practice (CoPs) inside electronic networks, and then using this knowledge to nurture them into a fully developed Virtual Community of Practice (VCoP). Starting from the standpoint of the need to manage knowledge, it discusses several questions related to this subject: the characteristics of 'hidden' communities; the relation between CoPs, Virtual Communities (VCs), Distributed Communities of Practice (DCoPs) and Virtual Communities of Practice (VCoPs); the methods used to search for 'hidden' CoPs; and the possible ways of changing 'hidden' CoPs into fully developed VCoPs. The paper also presents some preliminary findings from a semi-structured interview conducted in The Higher Education Academy Psychology Network (UK). These findings are contrasted against the theory discussed and some additional proposals are suggested at the end.
Parameterized Low-distortion Embeddings - Graph metrics into lines and trees
Venue: arXiv cs.DS 2008
Year: 2008

We revisit the issue of low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective.Let $M=M(G)$ be the shortest path metric of an edge weighted graph $G=(V,E)$ on $n$ vertices. We describe algorithms for the problem of finding a low distortion non-contracting embedding of $M$ into line and tree metrics. We give an $O(nd^4(2d+1)^{2d})$ time algorithm that for an unweighted graph metric $M$ and integer $d$ either constructs an embedding of $M$ into the line with distortion at most $d$, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is $O(n(dW)^4(2d+1)^{2dW})$ where $W$ is the largest edge weight of the input graph. We also show that deciding whether a weighted graph metric $M(G)$ with maximum weight $W < |V(G)|$ can be embedded into the line with distortion at most $d$ is NP-Complete for every fixed rational $d \geq 2$. This rules out any possibility of an algorithm with running time $O((nW)^{h(d)})$ where $h$ is a function of $d$ alone. We generalize the result on embedding into the line by proving that for any tree $T$ with maximum degree $Δ$, embedding of $M$ into a shortest path metric of $T$ is FPT, parameterized by $(Δ,d)$.
Size matters: performance declines if your pixels are too big or too small
Venue: arXiv cs.GR 2008
Year: 2008

We present a conceptual model that describes the effect of pixel size on target acquisition. We demonstrate the use of our conceptual model by applying it to predict and explain the results of an experiment to evaluate users' performance in a target acquisition task involving three distinct display sizes: standard desktop, small and large displays. The results indicate that users are fastest on standard desktop displays, undershoots are the most common error on small displays and overshoots are the most common error on large displays. We propose heuristics to maintain usability when changing displays. Finally, we contribute to the growing body of evidence that amplitude does affect performance in a display-based pointing task.
Partial Cross-Correlation of D-Sequences based CDMA System
Venue: arXiv cs.IT 2008
Year: 2008

Like other pseudorandom sequences, decimal sequences may be used in designing a Code Division Multiple Access (CDMA) system. They appear to be ideally suited for this since the cross-correlation of d-sequences taken over the LCM of their periods is zero. But a practical system will not, in most likelihood, satisfy the condition that the number of chips per bit is equal to the LCM for all sequences that are assigned to different users. It is essential, therefore, to determine the partial cross-correlation properties of d-sequences. This paper has performed experiments on d-sequences and found that the partial cross-correlation is less than for PN sequences, indicating that d-sequences can be effective for use in CDMA.
On Multiuser Power Region of Fading Multiple-Access Channel with Multiple Antennas
Venue: arXiv cs.IT 2008
Year: 2008

This paper is concerned with the fading MIMO-MAC with multiple receive antennas at the base station (BS) and multiple transmit antennas at each mobile terminal (MT). Two multiple-access techniques are considered for scheduling transmissions from each MT to the BS at the same frequency, which are space-division multiple-access (SDMA) and time-division multiple-access (TDMA). For SDMA, all MTs transmit simultaneously to the BS and their individual signals are resolved at the BS via multiple receive antennas while for TDMA, each MT transmits independently to the BS during mutually orthogonal time slots. It is assumed that the channel-state information (CSI) of the fading channel from each MT to the BS is unknown at each MT transmitter, but is perfectly known at the BS receiver. Thereby, the BS can acquire the long-term channel-distribution information (CDI) for each MT. This paper extends the well-known transmit-covariance feedback scheme for the point-to-point fading MIMO channel to the fading MIMO-MAC, whereby the BS jointly optimizes the transmit signal covariance matrices for all MTs based on their CDI, and then sends each transmit covariance matrix back to the corresponding MT via a feedback channel. The main goal of this paper is to characterize the so-called multiuser power region under the multiuser transmit-covariance feedback scheme for both SDMA and TDMA. The power region is defined as the constitution of all user transmit power-tuples that can achieve reliable transmissions for a given set of user target rates. Simulation results show that SDMA can achieve substantial power savings over TDMA for the fading MIMO-MAC. Moreover, this paper demonstrates the usefulness of the multiuser power region for maintaining proportionally-fair power consumption among the MTs.
Wadge Degrees of Infinitary Rational Relations
Venue: arXiv cs.LO 2008
Year: 2008

We show that, from the topological point of view, 2-tape Büchi automata have the same accepting power as Turing machines equipped with a Büchi acceptance condition. The Borel and the Wadge hierarchies of the class RAT_omega of infinitary rational relations accepted by 2-tape Büchi automata are equal to the Borel and the Wadge hierarchies of omega-languages accepted by real-time Büchi 1-counter automata or by Büchi Turing machines. In particular, for every non-null recursive ordinal $α$, there exist some $Σ^0_α$-complete and some $Π^0_α$-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal $γ^1_2$ which is strictly greater than the first non-recursive ordinal $ω_1^{CK}$. This very surprising result gives answers to questions of Simonnet (1992) and of Lescow and Thomas (1988,1994).
Sixteen New Linear Codes With Plotkin Sum
Venue: arXiv cs.IT 2008
Year: 2008

Sixteen new linear codes are presented: three of them improve the lower bounds on the minimum distance for a linear code and the rest are an explicit construction of unknown codes attaining the lower bounds on the minimum distance. They are constructed using the Plotkin sum of two linear codes, also called $(u|u+v)$ construction. The computations have been achieved using an exhaustiv search.
Isotropic PCA and Affine-Invariant Clustering
Venue: arXiv cs.LG 2008
Year: 2008

We present a new algorithm for clustering points in R^n. The key property of the algorithm is that it is affine-invariant, i.e., it produces the same partition for any affine transformation of the input. It has strong guarantees when the input is drawn from a mixture model. For a mixture of two arbitrary Gaussians, the algorithm correctly classifies the sample assuming only that the two components are separable by a hyperplane, i.e., there exists a halfspace that contains most of one Gaussian and almost none of the other in probability mass. This is nearly the best possible, improving known results substantially. For k > 2 components, the algorithm requires only that there be some (k-1)-dimensional subspace in which the emoverlap in every direction is small. Here we define overlap to be the ratio of the following two quantities: 1) the average squared distance between a point and the mean of its component, and 2) the average squared distance between a point and the mean of the mixture. The main result may also be stated in the language of linear discriminant analysis: if the standard Fisher discriminant is small enough, labels are not needed to estimate the optimal subspace for projection. Our main tools are isotropic transformation, spectral projection and a simple reweighting technique. We call this combination isotropic PCA.
Link Enhancer for Vehicular Wireless ATM Communications
Venue: arXiv cs.NI 2008
Year: 2008

Majority of the applications used in defense are voice, video and data oriented and has strict QoS requirements. One of the technologies that enabled this is Asynchronous Transfer Mode (ATM) networking. Traditional ATM networks are wired networks. But Tactical networks are meant to be mobile and this necessitates the use of radio relays for Vehicle-to-Infrastructure (V2I) and Vehicle-to-Vehicle (V2V) communications. ATM networks assume a physical link layer BER of 10^-9 or better because of the availability of reliable media like optical fiber links. But this assumption is no longer valid when ATM switches are connected through radio relay where error rates are in the rage of 10^-3. This paper presents the architecture of a Link Enhancer meant to improve the Bit Error Rate of the Wireless links used for V2I and V2V communications from 1 in 10^4 to 1 in 10^8
Virtual Reality Simulation of Fire Fighting Robot Dynamic and Motion
Venue: arXiv cs.RO 2008
Year: 2008

This paper presents one approach in designing a Fire Fighting Robot which has been contested annually in a robotic student competition in many countries following the rules initiated at the Trinity College. The approach makes use of computer simulation and animation in a virtual reality environment. In the simulation, the amount of time, starting from home until the flame is destroyed, can be confirmed. The efficacy of algorithms and parameter values employed can be easily evaluated. Rather than spending time building the real robot in a trial and error fashion, now students can explore more variation of algorithm, parameter and sensor-actuator configuration in the early stage of design. Besides providing additional excitement during learning process and enhancing students understanding to the engineering aspects of the design, this approach could become a useful tool to increase the chance of winning the contest.
Heading Lock Maneuver Testing of Autonomous Underwater Vehicle
Venue: arXiv cs.RO 2008
Year: 2008

In recent years, Autonomous Underwater Vehicle (UAV) research and development at Bandung Institute of Technology in Indonesia has achieved the testing stage in the field. This testing was still being classified as the early testing, since some of the preliminary tests were carried out in the scale of the laboratory. The paper would discuss the laboratory test and several tests that were done in the field. Discussions were stressed in the procedure and the aim that will be achieved, along with several early results. The testing was carried out in the lake with the area around 8300 Ha and the maximum depth of 50 meters. The location of the testing was chosen with consideration of minimizing the effect of the current and the wave, as well as the location that was not too far from the Laboratory. The type of testing that will be discussed in paper was Heading Lock Maneuver Testing. The vehicle was tested to move with a certain cruising speed, afterwards it was commanded by an arbitrarily selected heading direction. The response and the behavior of the vehicle were recorded as the data produced by the testing.
Development of Architectures for Internet Telerobotics Systems
Venue: arXiv cs.RO 2008
Year: 2008

This paper presents our experience in developing and implementing Internet telerobotics system. Internet telerobotics system refers to a robot system controlled and monitored remotely through the Internet. A robot manipulator with five degrees of freedom, called Mentor, is employed. Client-server architecture is chosen as a platform for our Internet telerobotics system. Three generations of telerobotics systems have evolved in this research. The first generation was based on CGI and two tiered architecture, where a client presents a Graphical User Interface to the user, and utilizes the user's data entry and actions to perform requests to robot server running on a different machine. The second generation was developed using Java. We also employ Java 3D for creating and manipulating 3D geometry of manipulator links and for constructing the structures used in rendering that geometry, resulting in 3D robot movement simulation presented to the users(clients) through their web browser. Recent development in our Internet telerobotics includes object recognition through image captured by a camera, which poses challenging problem, given the undeterministic latency of the Internet. The third generation is centered around the use of CORBA for development platform of distributed internet telerobotics system, aimed at distributing task of telerobotics system.
First Principle Approach to Modeling of Small Scale Helicopter
Venue: arXiv cs.RO 2008
Year: 2008

The establishment of global helicopter linear model is very precious and useful for the design of the linear control laws, since it is never afforded in the published literatures. In the first principle approach, the mathematical model was developed using basic helicopter theory accounting for particular characteristic of the miniature helicopter. No formal system identification procedures are required for the proposed model structure. The relevant published literatures however did not present the linear models required for the design of linear control laws. The paper presents a step by step development of linear model for small scale helicopter based on first-principle approach. Beyond the previous work in literatures, the calculation of the stability derivatives is presented in detail. A computer program is used to solve the equilibrium conditions and then calculate the change in aerodynamics forces and moments due to the change in each degree of freedom and control input. The detail derivation allows the comprehensive analysis of relative dominance of vehicle states and input variables to force and moment components. Hence it facilitates the development of minimum complexity small scale helicopter dynamics model.
Time Dependent Contraction Hierarchies -- Basic Algorithmic Ideas
Venue: arXiv cs.DS 2008
Year: 2008

Contraction hierarchies are a simple hierarchical routing technique that has proved extremely efficient for static road networks. We explain how to generalize them to networks with time-dependent edge weights. This is the first hierarchical speedup technique for time-dependent routing that allows bidirectional query algorithms.
Sketching and Streaming Entropy via Approximation Theory
Venue: arXiv cs.DS 2008
Year: 2008

We conclude a sequence of work by giving near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertions and deletions. This improves on prior results that obtain suboptimal space bounds in the general model, and near-optimal bounds in the insertion-only model without sketching. Our high-level approach is simple: we give algorithms to estimate Renyi and Tsallis entropy, and use them to extrapolate an estimate of Shannon entropy. The accuracy of our estimates is proven using approximation theory arguments and extremal properties of Chebyshev polynomials, a technique which may be useful for other problems. Our work also yields the best-known and near-optimal additive approximations for entropy, and hence also for conditional entropy and mutual information.
Explaining the Logical Nature of Electrical Solitons in Neural Circuits
Venue: arXiv cs.NE 2008
Year: 2008

Neurons are modeled electrically based on ferroelectric membranes thin enough to permit charge transfer, conjectured to be the tunneling result of thermally energetic ions and random electrons. These membranes can be triggered to produce electrical solitons, the main signals for brain associative memory and logical processing. Dendritic circuits are modeled, and electrical solitons are simulated to demonstrate the nature of soliton propagation, soliton reflection, the collision of solitons, as well as soliton OR gates, AND gates, XOR gates and NOT gates.
Free Distance Bounds for Protograph-Based Regular LDPC Convolutional Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper asymptotic methods are used to form lower bounds on the free distance to constraint length ratio of several ensembles of regular, asymptotically good, protograph-based LDPC convolutional codes. In particular, we show that the free distance to constraint length ratio of the regular LDPC convolutional codes exceeds that of the minimum distance to block length ratio of the corresponding LDPC block codes.
Generalized Degrees of Freedom of the Symmetric Gaussian $K$ User Interference Channel
Venue: arXiv cs.IT 2008
Year: 2008

We characterize the generalized degrees of freedom of the $K$ user symmetric Gaussian interference channel where all desired links have the same signal-to-noise ratio (SNR) and all undesired links carrying interference have the same interference-to-noise ratio, ${INR}={SNR}^α$. We find that the number of generalized degrees of freedom per user, $d(α)$, does not depend on the number of users, so that the characterization is identical to the 2 user interference channel with the exception of a singularity at $α=1$ where $d(1)=\frac{1}{K}$. The achievable schemes use multilevel coding with a nested lattice structure that opens the possibility that the sum of interfering signals can be decoded at a receiver even though the messages carried by the interfering signals are not decodable.