OpenRaiser/Intern-Atlas huggingface dataset:
Stackelberg Pricing is Hard to Approximate within $2-ε$
Venue: arXiv cs.GT 2009
Year: 2009

Stackelberg Pricing Games is a two-level combinatorial pricing problem studied in the Economics, Operation Research, and Computer Science communities. In this paper, we consider the decade-old shortest path version of this problem which is the first and most studied problem in this family. The game is played on a graph (representing a network) consisting of {\em fixed cost} edges and {\em pricable} or {\em variable cost} edges. The fixed cost edges already have some fixed price (representing the competitor's prices). Our task is to choose prices for the variable cost edges. After that, a client will buy the cheapest path from a node $s$ to a node $t$, using any combination of fixed cost and variable cost edges. The goal is to maximize the revenue on variable cost edges. In this paper, we show that the problem is hard to approximate within $2-ε$, improving the previous \APX-hardness result by Joret [to appear in {\em Networks}]. Our technique combines the existing ideas with a new insight into the price structure and its relation to the hardness of the instances.
Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
Venue: arXiv cs.IT 2009
Year: 2009

Consider the $n$-dimensional vector $y=X\be+\e$, where $\be \in \R^p$ has only $k$ nonzero entries and $\e \in \R^n$ is a Gaussian noise. This can be viewed as a linear system with sparsity constraints, corrupted by noise. We find a non-asymptotic upper bound on the probability that the optimal decoder for $β$ declares a wrong sparsity pattern, given any generic perturbation matrix $X$. In the case when $X$ is randomly drawn from a Gaussian ensemble, we obtain asymptotically sharp sufficient conditions for exact recovery, which agree with the known necessary conditions previously established.
A Survey of Biometric keystroke Dynamics: Approaches, Security and Challenges
Venue: arXiv cs.CR 2009
Year: 2009

Biometrics technologies are gaining popularity today since they provide more reliable and efficient means of authentication and verification. Keystroke Dynamics is one of the famous biometric technologies, which will try to identify the authenticity of a user when the user is working via a keyboard. The authentication process is done by observing the change in the typing pattern of the user. A comprehensive survey of the existing keystroke dynamics methods, metrics, different approaches are given in this study. This paper also discusses about the various security issues and challenges faced by keystroke dynamics.
Performance Evaluation of Wimax Physical Layer under Adaptive Modulation Techniques and Communication Channels
Venue: arXiv cs.PF 2009
Year: 2009

Wimax (Worldwide Interoperability for Microwave Access) is a promising technology which can offer high speed voice, video and data service up to the customer end. The aim of this paper is the performance evaluation of an Wimax system under different combinations of digital modulation (BPSK, QPSK, 4 QAM and 16 QAM) and different communication channels AWGN and fading channels (Rayleigh and Rician). And the Wimax system incorporates Reed Solomon (RS) encoder with Convolutional encoder with half and two third rated codes in FEC channel coding. The simulation results of estimated Bit Error Rate (BER) displays that the implementation of interleaved RS code (255, 239, 8) with two third rated Convolutional code under BPSK modulation technique is highly effective to combat in the Wimax communication system. To complete this performance analysis in Wimax based systems, a segment of audio signal is used for analysis. The transmitted audio message is found to have retrieved effectively under noisy situation.
Bidding for Representative Allocations for Display Advertising
Venue: arXiv cs.MA 2009
Year: 2009

Display advertising has traditionally been sold via guaranteed contracts -- a guaranteed contract is a deal between a publisher and an advertiser to allocate a certain number of impressions over a certain period, for a pre-specified price per impression. However, as spot markets for display ads, such as the RightMedia Exchange, have grown in prominence, the selection of advertisements to show on a given page is increasingly being chosen based on price, using an auction. As the number of participants in the exchange grows, the price of an impressions becomes a signal of its value. This correlation between price and value means that a seller implementing the contract through bidding should offer the contract buyer a range of prices, and not just the cheapest impressions necessary to fulfill its demand. Implementing a contract using a range of prices, is akin to creating a mutual fund of advertising impressions, and requires {\em randomized bidding}. We characterize what allocations can be implemented with randomized bidding, namely those where the desired share obtained at each price is a non-increasing function of price. In addition, we provide a full characterization of when a set of campaigns are compatible and how to implement them with randomized bidding strategies.
Interference Channels with One Cognitive Transmitter
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the problem of interference channels with one cognitive transmitter (ICOCT) where "cognitive" is defined from both the noncausal and causal perspectives. For the noncausal ICOCT, referred to as interference channels with degraded message sets (IC-DMS), we propose a new achievable rate region that generalizes existing achievable rate regions for IC-DMS. In the absence of the noncognitive transmitter, the proposed region coincides with Marton's region for the broadcast channel. Based on this result, the capacity region of a class of semi-deterministic IC-DMS is established. For the causal ICOCT, due to the complexity of the channel model, we focus primarily on the cognitive Z interference channel (ZIC), where the interference link from the cognitive transmitter to the primary receiver is assumed to be absent due to practical design considerations. Capacity bounds for such channels in different parameter regimes are obtained and the impact of such causal cognitive ability is carefully studied. In particular, depending on the channel parameters, the cognitive link may not be useful in terms of enlarging the capacity region. An optimal corner point of the capacity region is also established for the cognitive ZIC for a certain parameter regime.
Weak Kleene Algebra is Sound and (Possibly) Complete for Simulation
Venue: arXiv cs.LO 2009
Year: 2009

We show that the axioms of Weak Kleene Algebra (WKA) are sound and complete for the theory of regular expressions modulo simulation equivalence, assuming their completeness for monodic trees (as conjectured by Takai and Furusawa).
Design of network-coding based multi-edge type LDPC codes for multi-source relaying systems
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we investigate a multi-source LDPC scheme for a Gaussian relay system, where M sources communicate with the destination under the help of a single relay (M-1-1 system). Since various distributed LDPC schemes in the cooperative single-source system, e.g. bilayer LDPC and bilayer multi-edge type LDPC (BMET-LDPC), have been designed to approach the Shannon limit, these schemes can be applied to the $M-1-1$ system by the relay serving each source in a round-robin fashion. However, such a direct application is not optimal due to the lack of potential joint processing gain. In this paper, we propose a network coded multi-edge type LDPC (NCMET-LDPC) scheme for the multi-source scenario. Through an EXIT analysis, we conclude that the NCMET-LDPC scheme achieves higher extrinsic mutual information, relative to a separate application of BMET-LDPC to each source. Our new NCMET-LDPC scheme thus achieves a higher threshold relative to existing schemes.
Delay-Limited Cooperative Communication with Reliability Constraints in Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

We investigate optimal resource allocation for delay-limited cooperative communication in time varying wireless networks. Motivated by real-time applications that have stringent delay constraints, we develop a dynamic cooperation strategy that makes optimal use of network resources to achieve a target outage probability (reliability) for each user subject to average power constraints. Using the technique of Lyapunov optimization, we first present a general framework to solve this problem and then derive quasi-closed form solutions for several cooperative protocols proposed in the literature. Unlike earlier works, our scheme does not require prior knowledge of the statistical description of the packet arrival, channel state and node mobility processes and can be implemented in an online fashion.
Dynamic Demand-Capacity Balancing for Air Traffic Management Using Constraint-Based Local Search: First Results
Venue: arXiv cs.AI 2009
Year: 2009

Using constraint-based local search, we effectively model and efficiently solve the problem of balancing the traffic demands on portions of the European airspace while ensuring that their capacity constraints are satisfied. The traffic demand of a portion of airspace is the hourly number of flights planned to enter it, and its capacity is the upper bound on this number under which air-traffic controllers can work. Currently, the only form of demand-capacity balancing we allow is ground holding, that is the changing of the take-off times of not yet airborne flights. Experiments with projected European flight plans of the year 2030 show that already this first form of demand-capacity balancing is feasible without incurring too much total delay and that it can lead to a significantly better demand-capacity balance.
The Complexity of Infinite Computations In Models of Set Theory
Venue: arXiv cs.LO 2009
Year: 2009

We prove the following surprising result: there exist a 1-counter Büchi automaton and a 2-tape Büchi automaton such that the ω-language of the first and the infinitary rational relation of the second in one model of ZFC are π_2^0-sets, while in a different model of ZFC both are analytic but non Borel sets. This shows that the topological complexity of an ω-language accepted by a 1-counter Büchi automaton or of an infinitary rational relation accepted by a 2-tape Büchi automaton is not determined by the axiomatic system ZFC. We show that a similar result holds for the class of languages of infinite pictures which are recognized by Büchi tiling systems. We infer from the proof of the above results an improvement of the lower bound of some decision problems recently studied by the author.
Modular Traffic Sign Recognition applied to on-vehicle real-time visual detection of American and European speed limit signs
Venue: arXiv cs.CV 2009
Year: 2009

We present a new modular traffic signs recognition system, successfully applied to both American and European speed limit signs. Our sign detection step is based only on shape-detection (rectangles or circles). This enables it to work on grayscale images, contrary to most European competitors, which eases robustness to illumination conditions (notably night operation). Speed sign candidates are classified (or rejected) by segmenting potential digits inside them (which is rather original and has several advantages), and then applying a neural digit recognition. The global detection rate is ~90% for both (standard) U.S. and E.U. speed signs, with a misclassification rate <1%, and no validated false alarm in >150 minutes of video. The system processes in real-time ~20 frames/s on a standard high-end laptop.
Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion
Venue: arXiv cs.CC 2009
Year: 2009

In (Kabanets, Impagliazzo, 2004) it is shown how to decide the circuit polynomial identity testing problem (CPIT) in deterministic subexponential time, assuming hardness of some explicit multilinear polynomial family for arithmetical circuits. In this paper, a special case of CPIT is considered, namely low-degree non-singular matrix completion (NSMC). For this subclass of problems it is shown how to obtain the same deterministic time bound, using a weaker assumption in terms of determinantal complexity. Hardness-randomness tradeoffs will also be shown in the converse direction, in an effort to make progress on Valiant's VP versus VNP problem. To separate VP and VNP, it is known to be sufficient to prove that the determinantal complexity of the m-by-m permanent is $m^{ω(\log m)}$. In this paper it is shown, for an appropriate notion of explicitness, that the existence of an explicit multilinear polynomial family with determinantal complexity m^{ω(\log m)}$ is equivalent to the existence of an efficiently computable generator $G_n$ for multilinear NSMC with seed length $O(n^{1/\sqrt{\log n}})$. The latter is a combinatorial object that provides an efficient deterministic black-box algorithm for NSMC. ``Multilinear NSMC'' indicates that $G_n$ only has to work for matrices $M(x)$ of $poly(n)$ size in $n$ variables, for which $det(M(x))$ is a multilinear polynomial.
Near-Optimal Detection in MIMO Systems using Gibbs Sampling
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for solving the integer least-squares problem. In digital communication the problem is equivalent to performing Maximum Likelihood (ML) detection in Multiple-Input Multiple-Output (MIMO) systems. While the use of MCMC methods for such problems has already been proposed, our method is novel in that we optimize the "temperature" parameter so that in steady state, i.e. after the Markov chain has mixed, there is only polynomially (rather than exponentially) small probability of encountering the optimal solution. More precisely, we obtain the largest value of the temperature parameter for this to occur, since the higher the temperature, the faster the mixing. This is in contrast to simulated annealing techniques where, rather than being held fixed, the temperature parameter is tended to zero. Simulations suggest that the resulting Gibbs sampler provides a computationally efficient way of achieving approximative ML detection in MIMO systems having a huge number of transmit and receive dimensions. In fact, they further suggest that the Markov chain is rapidly mixing. Thus, it has been observed that even in cases were ML detection using, e.g. sphere decoding becomes infeasible, the Gibbs sampler can still offer a near-optimal solution using much less computations.
Estimating Entropy of Data Streams Using Compressed Counting
Venue: arXiv cs.DS 2009
Year: 2009

The Shannon entropy is a widely used summary statistic, for example, network traffic measurement, anomaly detection, neural computations, spike trains, etc. This study focuses on estimating Shannon entropy of data streams. It is known that Shannon entropy can be approximated by Reenyi entropy or Tsallis entropy, which are both functions of the p-th frequency moments and approach Shannon entropy as p->1. Compressed Counting (CC) is a new method for approximating the p-th frequency moments of data streams. Our contributions include: 1) We prove that Renyi entropy is (much) better than Tsallis entropy for approximating Shannon entropy. 2) We propose the optimal quantile estimator for CC, which considerably improves the previous estimators. 3) Our experiments demonstrate that CC is indeed highly effective approximating the moments and entropies. We also demonstrate the crucial importance of utilizing the variance-bias trade-off.
Cooperation with an Untrusted Relay: A Secrecy Perspective
Venue: arXiv cs.IT 2009
Year: 2009

We consider the communication scenario where a source-destination pair wishes to keep the information secret from a relay node despite wanting to enlist its help. For this scenario, an interesting question is whether the relay node should be deployed at all. That is, whether cooperation with an untrusted relay node can ever be beneficial. We first provide an achievable secrecy rate for the general untrusted relay channel, and proceed to investigate this question for two types of relay networks with orthogonal components. For the first model, there is an orthogonal link from the source to the relay. For the second model, there is an orthogonal link from the relay to the destination. For the first model, we find the equivocation capacity region and show that answer is negative. In contrast, for the second model, we find that the answer is positive. Specifically, we show by means of the achievable secrecy rate based on compress-and-forward, that, by asking the untrusted relay node to relay information, we can achieve a higher secrecy rate than just treating the relay as an eavesdropper. For a special class of the second model, where the relay is not interfering itself, we derive an upper bound for the secrecy rate using an argument whose net effect is to separate the eavesdropper from the relay. The merit of the new upper bound is demonstrated on two channels that belong to this special class. The Gaussian case of the second model mentioned above benefits from this approach in that the new upper bound improves the previously known bounds. For the Cover-Kim deterministic relay channel, the new upper bound finds the secrecy capacity when the source-destination link is not worse than the source-relay link, by matching with the achievable rate we present.
An algebraic framework for information theory: Classical Information
Venue: arXiv cs.IT 2009
Year: 2009

This work proposes a complete algebraic model for classical information theory. As a precursor the essential probabilistic concepts have been defined and analyzed in the algebraic setting. Examples from probability and information theory demonstrate that in addition to theoretical insights provided by the algebraic model one obtains new computational and anlytical tools. Several important theorems of classical probahility and information theory are formulated and proved in the algebraic framework.
Modified Basis Pursuit Denoising(MODIFIED-BPDN) for Noisy Compressive Sensing with Partially Known Support
Venue: arXiv cs.IT 2009
Year: 2009

In this work, we study the problem of reconstructing a sparse signal from a limited number of linear 'incoherent' noisy measurements, when a part of its support is known. The known part of the support may be available from prior knowledge or from the previous time instant (in applications requiring recursive reconstruction of a time sequence of sparse signals, e.g. dynamic MRI). We study a modification of Basis Pursuit Denoising (BPDN) and bound its reconstruction error. A key feature of our work is that the bounds that we obtain are computable. Hence, we are able to use Monte Carlo to study their average behavior as the size of the unknown support increases. We also demonstrate that when the unknown support size is small, modified-BPDN bounds are much tighter than those for BPDN, and hold under much weaker sufficient conditions (require fewer measurements).
Decomposition of forging die for high speed machining
Venue: arXiv cs.RO 2009
Year: 2009

Today's forging die manufacturing process must be adapted to several evolutions in machining process generation: CAD/CAM models, CAM software solutions and High Speed Machining (HSM). In this context, the adequacy between die shape and HSM process is in the core of machining preparation and process planning approaches. This paper deals with an original approach of machining preparation integrating this adequacy in the main tasks carried out. In this approach, the design of the machining process is based on two levels of decomposition of the geometrical model of a given die with respect to HSM cutting conditions (cutting speed and feed rate) and technological constrains (tool selection, features accessibility). This decomposition assists machining assistant to generate an HSM process. The result of this decomposition is the identification of machining features.
Définition d'une pièce test pour la caractérisation d'une machine UGV
Venue: arXiv cs.RO 2009
Year: 2009

In several fields like aeronautics, die and automotive, the machining of the parts is done more and more on high speed machines tools. Today, the offer for purchasing these machine tools is very wide. This situation poses the problem of the judicious and objective choice meeting industrial needs that must be necessary well expressed. The choice remains difficult insofar as the technical data provided to the customers by the manufacturers of machine tools are insufficient as well quantitatively as qualitatively. In this paper we present a protocol for the characterization of machines tools in order to direct the choice. The protocol is based on the one hand on no-load complementary tests to those recommended by the standards ISO 230 and ISO 10791 and on the other hand on the tests in load on a part test. In the first part, we present the industrial needs as well as an analysis of the technical data of machine tools. The second part is devoted to the study of the standards, the description of the protocol and the presentation of the results.
Finding a sun in building-free graphs
Venue: arXiv cs.DM 2009
Year: 2009

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3}, m^{1.5}n^2\}$) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.
Password Based a Generalize Robust Security System Design Using Neural Network
Venue: arXiv cs.CR 2009
Year: 2009

Among the various means of available resource protection including biometrics, password based system is most simple, user friendly, cost effective and commonly used. But this method having high sensitivity with attacks. Most of the advanced methods for authentication based on password encrypt the contents of password before storing or transmitting in physical domain. But all conventional cryptographic based encryption methods are having its own limitations, generally either in terms of complexity or in terms of efficiency. Multi-application usability of password today forcing users to have a proper memory aids. Which itself degrades the level of security. In this paper a method to exploit the artificial neural network to develop the more secure means of authentication, which is more efficient in providing the authentication, at the same time simple in design, has given. Apart from protection, a step toward perfect security has taken by adding the feature of intruder detection along with the protection system. This is possible by analysis of several logical parameters associated with the user activities. A new method of designing the security system centrally based on neural network with intrusion detection capability to handles the challenges available with present solutions, for any kind of resource has presented.