OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Counting and Quantum Computation
Venue: arXiv cs.CC 2009
Year: 2009

Motivated by the result that an `approximate' evaluation of the Jones polynomial of a braid at a $5^{th}$ root of unity can be used to simulate the quantum part of any algorithm in the quantum complexity class BQP, and results relating BQP to the counting class GapP, we introduce a form of additive approximation which can be used to simulate a function in BQP. We show that all functions in the classes #P and GapP have such an approximation scheme under certain natural normalisations. However we are unable to determine whether the particular functions we are motivated by, such as the above evaluation of the Jones polynomial, can be approximated in this way. We close with some open problems motivated by this work.
The Berlekamp-Massey Algorithm and the Euclidean Algorithm: a Closer Link
Venue: arXiv cs.IT 2009
Year: 2009

The two primary decoding algorithms for Reed-Solomon codes are the Berlekamp-Massey algorithm and the Sugiyama et al. adaptation of the Euclidean algorithm, both designed to solve a key equation. In this article an alternative version of the key equation and a new way to use the Euclidean algorithm to solve it are presented, which yield the Berlekamp-Massey algorithm. This results in a new, simpler, and compacter presentation of the Berlekamp-Massey algorithm.
Being Fat and Friendly is Not Enough
Venue: arXiv cs.CG 2009
Year: 2009

We show that there is no $(1+\eps)$-approximation algorithm for the problem of covering points in the plane by minimum number of fat triangles of similar size (with the minimum angle of the triangles being close to 45 degrees). Here, the available triangles are prespecified in advance. Since a constant factor approximation algorithm is known for this problem \cite{cv-iaags-07}, this settles the approximability of this problem. We also investigate some related problems, including cover by friendly fat shapes, and independent set of triangles in three dimensions.
Power Allocation Strategies and Lattice Based Coding schemes for Bi-directional relaying
Venue: arXiv cs.IT 2009
Year: 2009

We consider a communication system where two transmitters wish to exchange information through a half-duplex relay in the middle. The channels between the transmitters and the relay have asymmetric channel gains. More specifically, the channels are assumed to be synchronized with complex inputs and complex fading coefficients with an average power constraint on the inputs to the channels. The noise at the receivers have the same power spectral density and are assumed to be white and Gaussian. We restrict our attention to transmission schemes where information from the two nodes are simultaneously sent to the relay during a medium access phase followed by a broadcast phase where the relay broadcasts information to both the nodes. An upper bound on the capacity for the two phase protocol under a sum power constraint on the transmit power from all the nodes is obtained as a solution to a convex optimization problem. We show that a scheme using channel inversion with lattice decoding can obtain a rate a small constant 0.09 bits from the upper bound at high signal-to-noise ratios. Numerical results show that the proposed scheme can perform very close to the upper bound.
Detecting all regular polygons in a point set
Venue: arXiv cs.CG 2009
Year: 2009

In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our result depends on the parameter alpha, which has been used to bound the maximum number of isosceles triangles that can be formed by n points. This bound has been expressed as O(n^{2+2alpha+epsilon}), and the current best value for alpha is ~0.068. Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through the set of points, while larger polygons are found by random sampling. We can find all regular polygons with high probability in O(n^{2+alpha+epsilon}) expected time for every positive epsilon. This compares well to the O(n^{2+2alpha+epsilon}) deterministic algorithm of Brass.
A Rate-Distortion Perspective on Multiple Decoding Attempts for Reed-Solomon Codes
Venue: arXiv cs.IT 2009
Year: 2009

Recently, a number of authors have proposed decoding schemes for Reed-Solomon (RS) codes based on multiple trials of a simple RS decoding algorithm. In this paper, we present a rate-distortion (R-D) approach to analyze these multiple-decoding algorithms for RS codes. This approach is first used to understand the asymptotic performance-versus-complexity trade-off of multiple error-and-erasure decoding of RS codes. By defining an appropriate distortion measure between an error pattern and an erasure pattern, the condition for a single error-and-erasure decoding to succeed reduces to a form where the distortion is compared to a fixed threshold. Finding the best set of erasure patterns for multiple decoding trials then turns out to be a covering problem which can be solved asymptotically by rate-distortion theory. Next, this approach is extended to analyze multiple algebraic soft-decision (ASD) decoding of RS codes. Both analytical and numerical computations of the R-D functions for the corresponding distortion measures are discussed. Simulation results show that proposed algorithms using this approach perform better than other algorithms with the same complexity.
Informal specification-based performance evaluation of security protocols
Venue: arXiv cs.CR 2009
Year: 2009

We propose a performance evaluation method for security protocols. Based on the informal specification, we construct a canonical model which includes, alongside protocol messages, cryptographic operations performed by participants in the process of message construction. Each cryptographic operation is assigned a cost modeled as a function of the size of processed message components. We model not only the size of regular message components but also the size of ciphertext produced by various cryptographic operations. We illustrate the applicability of our method by comparatively analyzing the performance of the original CCITT X.509 protocol and a slightly modified version of the same protocol.
Design and Implementation of a Distributed Middleware for Parallel Execution of Legacy Enterprise Applications
Venue: arXiv cs.DC 2009
Year: 2009

A typical enterprise uses a local area network of computers to perform its business. During the off-working hours, the computational capacities of these networked computers are underused or unused. In order to utilize this computational capacity an application has to be recoded to exploit concurrency inherent in a computation which is clearly not possible for legacy applications without any source code. This thesis presents the design an implementation of a distributed middleware which can automatically execute a legacy application on multiple networked computers by parallelizing it. This middleware runs multiple copies of the binary executable code in parallel on different hosts in the network. It wraps up the binary executable code of the legacy application in order to capture the kernel level data access system calls and perform them distributively over multiple computers in a safe and conflict free manner. The middleware also incorporates a dynamic scheduling technique to execute the target application in minimum time by scavenging the available CPU cycles of the hosts in the network. This dynamic scheduling also supports the CPU availability of the hosts to change over time and properly reschedule the replicas performing the computation to minimize the execution time. A prototype implementation of this middleware has been developed as a proof of concept of the design. This implementation has been evaluated with a few typical case studies and the test results confirm that the middleware works as expected.
Rate Constrained Random Access over a Fading Channel
Venue: arXiv cs.GT 2009
Year: 2009

In this paper, we consider uplink transmissions involving multiple users communicating with a base station over a fading channel. We assume that the base station does not coordinate the transmissions of the users and hence the users employ random access communication. The situation is modeled as a non-cooperative repeated game with incomplete information. Each user attempts to minimize its long term power consumption subject to a minimum rate requirement. We propose a two timescale stochastic gradient algorithm (TTSGA) for tuning the users' transmission probabilities. The algorithm includes a 'waterfilling threshold update mechanism' that ensures that the rate constraints are satisfied. We prove that under the algorithm, the users' transmission probabilities converge to a Nash equilibrium. Moreover, we also prove that the rate constraints are satisfied; this is also demonstrated using simulation studies.
Mathematical Modeling of Aerodynamic Space -to - Surface Flight with Trajectory for Avoid Intercepting Process for Safety and Security Issues
Venue: arXiv cs.OH 2009
Year: 2009

The research project has been made for mathematical modeling of aerospace system Space-to-Surface for avoid intercepting process by flight objects Surface-to-Air. The research has been completed and created mathematical models which used for research and statistical analysis. In mathematical modeling has been including a few models: Model of atmosphere, Model of speed of sound, Model of flight head in space, Model of flight in atmosphere, Models of navigation and guidance, Model and statistical analysis of approximation of aerodynamic characteristics. Modeling has been created for a Space-to-Surface system defined for an optimal trajectory in terminal phase. The modeling includes models for simulation atmosphere, aerodynamic flight and navigation by an infrared system. The modeling simulation includes statistical analysis of the modeling results.
Interpolation-Based QR Decomposition in MIMO-OFDM Systems
Venue: arXiv cs.IT 2009
Year: 2009

Detection algorithms for multiple-input multiple-output (MIMO) wireless systems based on orthogonal frequency-division multiplexing (OFDM) typically require the computation of a QR decomposition for each of the data-carrying OFDM tones. The resulting computational complexity will, in general, be significant, as the number of data-carrying tones ranges from 48 (as in the IEEE 802.11a/g standards) to 1728 (as in the IEEE 802.16e standard). Motivated by the fact that the channel matrices arising in MIMO-OFDM systems are highly oversampled polynomial matrices, we formulate interpolation-based QR decomposition algorithms. An in-depth complexity analysis, based on a metric relevant for very large scale integration (VLSI) implementations, shows that the proposed algorithms, for sufficiently high number of data-carrying tones and sufficiently small channel order, provably exhibit significantly smaller complexity than brute-force per-tone QR decomposition.
On the Second Order Statistics of the Multihop Rayleigh Fading Channel
Venue: arXiv cs.IT 2009
Year: 2009

Second order statistics provides a dynamic representation of a fading channel and plays an important role in the evaluation and design of the wireless communication systems. In this paper, we present a novel analytical framework for the evaluation of important second order statistical parameters, as the level crossing rate (LCR) and the average fade duration (AFD) of the amplify-and-forward multihop Rayleigh fading channel. More specifically, motivated by the fact that this channel is a cascaded one and can be modeled as the product of N fading amplitudes, we derive novel analytical expressions for the average LCR and the AFD of the product of N Rayleigh fading envelopes (or of the recently so-called N*Rayleigh channel). Furthermore, we derive simple and efficient closed-form approximations to the aforementioned parameters, using the multivariate Laplace approximation theorem. It is shown that our general results reduce to the corresponding ones of the specific dual-hop case, previously published. Numerical and computer simulation examples verify the accuracy of the presented mathematical analysis and show the tightness of the proposed approximations.
Maximizing profit using recommender systems
Venue: arXiv cs.CY 2009
Year: 2009

Traditional recommendation systems make recommendations based solely on the customer's past purchases, product ratings and demographic data without considering the profitability the items being recommended. In this work we study the question of how a vendor can directly incorporate the profitability of items into its recommender so as to maximize its expected profit while still providing accurate recommendations. Our approach uses the output of any traditional recommender system and adjust them according to item profitabilities. Our approach is parameterized so the vendor can control how much the recommendation incorporating profits can deviate from the traditional recommendation. We study our approach under two settings and show that it achieves approximately 22% more profit than traditional recommendations.
A parameterization process as a categorical construction
Venue: arXiv cs.LO 2009
Year: 2009

The parameterization process used in the symbolic computation systems Kenzo and EAT is studied here as a general construction in a categorical framework. This parameterization process starts from a given specification and builds a parameterized specification by transforming some operations into parameterized operations, which depend on one additional variable called the parameter. Given a model of the parameterized specification, each interpretation of the parameter, called an argument, provides a model of the given specification. Moreover, under some relevant terminality assumption, this correspondence between the arguments and the models of the given specification is a bijection. It is proved in this paper that the parameterization process is provided by a free functor and the subsequent parameter passing process by a natural transformation. Various categorical notions are used, mainly adjoint functors, pushouts and lax colimits.
An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
Venue: arXiv cs.DS 2009
Year: 2009

We consider the single-source (or single-sink) buy-at-bulk problem with an unknown concave cost function. We want to route a set of demands along a graph to or from a designated root node, and the cost of routing x units of flow along an edge is proportional to some concave, non-decreasing function f such that f(0) = 0. We present a polynomial time algorithm that finds a distribution over trees such that the expected cost of a tree for any f is within an O(1)-factor of the optimum cost for that f. The previous best simultaneous approximation for this problem, even ignoring computation time, was O(log |D|), where D is the multi-set of demand nodes. We design a simple algorithmic framework using the ellipsoid method that finds an O(1)-approximation if one exists, and then construct a separation oracle using a novel adaptation of the Guha, Meyerson, and Munagala algorithm for the single-sink buy-at-bulk problem that proves an O(1) approximation is possible for all f. The number of trees in the support of the distribution constructed by our algorithm is at most 1+log |D|.
A Dynamic Boundary Guarding Problem with Translating Targets
Venue: arXiv cs.RO 2009
Year: 2009

We introduce a problem in which a service vehicle seeks to guard a deadline (boundary) from dynamically arriving mobile targets. The environment is a rectangle and the deadline is one of its edges. Targets arrive continuously over time on the edge opposite the deadline, and move towards the deadline at a fixed speed. The goal for the vehicle is to maximize the fraction of targets that are captured before reaching the deadline. We consider two cases; when the service vehicle is faster than the targets, and; when the service vehicle is slower than the targets. In the first case we develop a novel vehicle policy based on computing longest paths in a directed acyclic graph. We give a lower bound on the capture fraction of the policy and show that the policy is optimal when the distance between the target arrival edge and deadline becomes very large. We present numerical results which suggest near optimal performance away from this limiting regime. In the second case, when the targets are slower than the vehicle, we propose a policy based on servicing fractions of the translational minimum Hamiltonian path. In the limit of low target speed and high arrival rate, the capture fraction of this policy is within a small constant factor of the optimal.
Semi-algebraic Range Reporting and Emptiness Searching with Applications
Venue: arXiv cs.CG 2009
Year: 2009

In a typical range emptiness searching (resp., reporting) problem, we are given a set $P$ of $n$ points in $\reals^d$, and wish to preprocess it into a data structure that supports efficient range emptiness (resp., reporting) queries, in which we specify a range $σ$, which, in general, is a semi-algebraic set in $\reals^d$ of constant description complexity, and wish to determine whether $P\capσ=\emptyset$, or to report all the points in $P\capσ$. Range emptiness searching and reporting arise in many applications, and have been treated by Matoušek \cite{Ma:rph} in the special case where the ranges are halfspaces bounded by hyperplanes. As shown in \cite{Ma:rph}, the two problems are closely related, and have solutions (for the case of halfspaces) with similar performance bounds. In this paper we extend the analysis to general semi-algebraic ranges, and show how to adapt Matoušek's technique, without the need to {\em linearize} the ranges into a higher-dimensional space. This yields more efficient solutions to several useful problems, and we demonstrate the new technique in four applications.
Distributed Averaging via Lifted Markov Chains
Venue: arXiv cs.IT 2009
Year: 2009

Motivated by applications of distributed linear estimation, distributed control and distributed optimization, we consider the question of designing linear iterative algorithms for computing the average of numbers in a network. Specifically, our interest is in designing such an algorithm with the fastest rate of convergence given the topological constraints of the network. As the main result of this paper, we design an algorithm with the fastest possible rate of convergence using a non-reversible Markov chain on the given network graph. We construct such a Markov chain by transforming the standard Markov chain, which is obtained using the Metropolis-Hastings method. We call this novel transformation pseudo-lifting. We apply our method to graphs with geometry, or graphs with doubling dimension. Specifically, the convergence time of our algorithm (equivalently, the mixing time of our Markov chain) is proportional to the diameter of the network graph and hence optimal. As a byproduct, our result provides the fastest mixing Markov chain given the network topological constraints, and should naturally find their applications in the context of distributed optimization, estimation and control.
Consideration Points Detecting Cross-Site Scripting
Venue: arXiv cs.CR 2009
Year: 2009

Web application (WA) expands its usages to provide more and more services and it has become one of the most essential communication channels between service providers and the users. To augment the users experience many web applications are using client side scripting languages such as JavaScript but this growing of JavaScript is increasing serious security vulnerabilities in web application too, such as cross site scripting (XSS). In this paper, I survey all the techniques those have been used to detect XSS and arrange a number of analyses to evaluate performances of those methodologies. This paper points major difficulties to detect XSS. I do not implement any solution of this vulnerability problem because my focus is for reviewing this issue. But, I believe that this assessment will be cooperative for further research on this concern as this treatise figure out everything on this transcendent security problem.
Coding Improves the Throughput-Delay Trade-off in Mobile Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

We study the throughput-delay performance tradeoff in large-scale wireless ad hoc networks. It has been shown that the per source-destination pair throughput can be improved from Theta(1/sqrt(n log n)) to Theta(1) if nodes are allowed to move and a 2-hop relay scheme is employed. The price paid for such an improvement on throughput is large delay. Indeed, the delay scaling of the 2-hop relay scheme is Theta(n log n) under the random walk mobility model. In this paper, we employ coding techniques to improve the throughput-delay trade-off for mobile wireless networks. For the random walk mobility model, we improve the delay from Theta(n log n) to Theta(n) by employing Reed-Solomon codes. Our approach maintains the diversity gained by mobility while decreasing the delay.
Visualization of Mined Pattern and Its Human Aspects
Venue: arXiv cs.HC 2009
Year: 2009

Researchers got success in mining the Web usage data effectively and efficiently. But representation of the mined patterns is often not in a form suitable for direct human consumption. Hence mechanisms and tools that can represent mined patterns in easily understandable format are utilized. Different techniques are used for pattern analysis, one of them is visualization. Visualization can provide valuable assistance for data analysis and decision making tasks. In the data visualization process, technical representations of web pages are replaced by user attractive text interpretations. Experiments with the real world problems showed that the visualization can significantly increase the quality and usefulness of web log mining results. However, how decision makers perceive and interact with a visual representation can strongly influence their understanding of the data as well as the usefulness of the visual presentation. Human factors therefore contribute significantly to the visualization process and should play an important role in the design and evaluation of visualization tools. This electronic document is a live template. The various components of your paper, title, text, heads, etc., are already defined on the style sheet, as illustrated by the portions given in this document.
A parameterization process, functorially
Venue: arXiv cs.LO 2009
Year: 2009

The parameterization process used in the symbolic computation systems Kenzo and EAT is studied here as a general construction in a categorical framework. This parameterization process starts from a given specification and builds a parameterized specification by adding a parameter as a new variable to some operations. Given a model of the parameterized specification, each interpretation of the parameter, called an argument, provides a model of the given specification. Moreover, under some relevant terminality assumption, this correspondence between the arguments and the models of the given specification is a bijection. It is proved in this paper that the parameterization process is provided by a functor and the subsequent parameter passing process by a natural transformation. Various categorical notions are used, mainly adjoint functors, pushouts and lax colimits.