OpenRaiser/Intern-Atlas huggingface dataset:
Online Vertex Cover and Matching: Beating the Greedy Algorithm
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we explicitly study the online vertex cover problem, which is a natural generalization of the well-studied ski-rental problem. In the online vertex cover problem, we are required to maintain a monotone vertex cover in a graph whose vertices arrive online. When a vertex arrives, all its incident edges to previously arrived vertices are revealed to the algorithm. For bipartite graphs with the left vertices offline (i.e. all of the left vertices arrive first before any right vertex), there are algorithms achieving the optimal competitive ratio of $\frac{1}{1-1/e}\approx 1.582$. Our first result is a new optimal water-filling algorithm for this case. One major ingredient of our result is a new charging-based analysis, which can be generalized to attack the online fractional vertex cover problem in general graphs. The main contribution of this paper is a 1.901-competitive algorithm for this problem. When the underlying graph is bipartite, our fractional solution can be rounded to an integral solution. In other words, we can obtain a vertex cover with expected size at most 1.901 of the optimal vertex cover in bipartite graphs. The next major result is a primal-dual analysis of our algorithm for the online fractional vertex cover problem in general graphs, which implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. Notice that both problems admit a well-known 2-competitive greedy algorithm. Our result in this paper is the first successful attempt to beat the greedy algorithm for these two problems. On the hardness side, we show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.
On attribute-based usage control policy ratification for cooperative computing context
Venue: arXiv cs.CR 2013
Year: 2013

In an open information systems paradigm, real-time context-awareness is vital for the success of cooperation, therefore dynamic security attributes of partners should considered in coalition for avoiding security conflicts. Furthermore, the cross-boundary asset sharing activities and risks associated to loss of governance call for a continuous regulation of partners' behavior, paying attention to the resource sharing and consuming activities. This paper describes an attribute-based usage control policy shceme compline to this needs. A concise syntax with EBNF is used to summarize the base policy model. The semantics of negotiation process is disambiguated with abductive constraint logic programming (ACLP) and Event Calculus (EC). Then we propose a policy ratification method based on a policy aggregation algebra that elaborate the request space and policy rule relation. This method ensures that, when policies are aggregated due to resource sharing and merging activities, the resulting policy correctly interprets the original security goals of the providers' policies.
Mobile Recommender Systems Methods: An Overview
Venue: arXiv cs.IR 2013
Year: 2013

The information that mobiles can access becomes very wide nowadays, and the user is faced with a dilemma: there is an unlimited pool of information available to him but he is unable to find the exact information he is looking for. This is why the current research aims to design Recommender Systems (RS) able to continually send information that matches the user's interests in order to reduce his navigation time. In this paper, we treat the different approaches to recommend.
Quantized Iterative Hard Thresholding: Bridging 1-bit and High-Resolution Quantized Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we show that reconstructing a sparse signal from quantized compressive measurement can be achieved in an unified formalism whatever the (scalar) quantization resolution, i.e., from 1-bit to high resolution assumption. This is achieved by generalizing the iterative hard thresholding (IHT) algorithm and its binary variant (BIHT) introduced in previous works to enforce the consistency of the reconstructed signal with respect to the quantization model. The performance of this algorithm, simply called quantized IHT (QIHT), is evaluated in comparison with other approaches (e.g., IHT, basis pursuit denoise) for several quantization scenarios.
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we show how to accelerate randomized coordinate descent methods and achieve faster convergence rates without paying per-iteration costs in asymptotic running time. In particular, we show how to generalize and efficiently implement a method proposed by Nesterov, giving faster asymptotic running times for various algorithms that use standard coordinate descent as a black box. In addition to providing a proof of convergence for this new general method, we show that it is numerically stable, efficiently implementable, and in certain regimes, asymptotically optimal. To highlight the computational power of this algorithm, we show how it can used to create faster linear system solvers in several regimes: - We show how this method achieves a faster asymptotic runtime than conjugate gradient for solving a broad class of symmetric positive definite systems of equations. - We improve the best known asymptotic convergence guarantees for Kaczmarz methods, a popular technique for image reconstruction and solving overdetermined systems of equations, by accelerating a randomized algorithm of Strohmer and Vershynin. - We achieve the best known running time for solving Symmetric Diagonally Dominant (SDD) system of equations in the unit-cost RAM model, obtaining an O(m log^{3/2} n (log log n)^{1/2} log (log n / eps)) asymptotic running time by accelerating a recent solver by Kelner et al. Beyond the independent interest of these solvers, we believe they highlight the versatility of the approach of this paper and we hope that they will open the door for further algorithmic improvements in the future.
On the universality of cognitive tests
Venue: arXiv cs.AI 2013
Year: 2013

The analysis of the adaptive behaviour of many different kinds of systems such as humans, animals and machines, requires more general ways of assessing their cognitive abilities. This need is strengthened by increasingly more tasks being analysed for and completed by a wider diversity of systems, including swarms and hybrids. The notion of universal test has recently emerged in the context of machine intelligence evaluation as a way to define and use the same cognitive test for a variety of systems, using some principled tasks and adapting the interface to each particular subject. However, how far can universal tests be taken? This paper analyses this question in terms of subjects, environments, space-time resolution, rewards and interfaces. This leads to a number of findings, insights and caveats, according to several levels where universal tests may be progressively more difficult to conceive, implement and administer. One of the most significant contributions is given by the realisation that more universal tests are defined as maximisations of less universal tests for a variety of configurations. This means that universal tests must be necessarily adaptive.
HTTP Mailbox - Asynchronous RESTful Communication
Venue: arXiv cs.SE 2013
Year: 2013

We describe HTTP Mailbox, a mechanism to enable RESTful HTTP communication in an asynchronous mode with a full range of HTTP methods otherwise unavailable to standard clients and servers. HTTP Mailbox allows for broadcast and multicast semantics via HTTP. We evaluate a reference implementation using ApacheBench (a server stress testing tool) demonstrating high throughput (on 1,000 concurrent requests) and a systemic error rate of 0.01%. Finally, we demonstrate our HTTP Mailbox implementation in a human assisted web preservation application called "Preserve Me".
Expressing Algorithms As Concise As Possible via Computability Logic
Venue: arXiv cs.LO 2013
Year: 2013

This paper proposes a new approach to defining and expressing algorithms: the notion of {\it task logical} algorithms. This notion allows the user to define an algorithm for a task $T$ as a set of agents who can collectively perform $T$. This notion considerably simplifies the algorithm development process and can be seen as an integration of the sequential pseudocode and logical algorithms. This observation requires some changes to algorithm development process. We propose a two-step approach: the first step is to define an algorithm for a task $T$ via a set of agents that can collectively perform $T$. The second step is to translate these agents into (higher-order) computability logic.
An Epistemic Perspective on Consistency of Concurrent Computations
Venue: arXiv cs.LO 2013
Year: 2013

Consistency properties of concurrent computations, e.g., sequential consistency, linearizability, or eventual consistency, are essential for devising correct concurrent algorithms. In this paper, we present a logical formalization of such consistency properties that is based on a standard logic of knowledge. Our formalization provides a declarative perspective on what is imposed by consistency requirements and provides some interesting unifying insight on differently looking properties.
Cryptography and Algorithmic Randomness
Venue: arXiv cs.CR 2013
Year: 2013

The secure instantiation of the random oracle is one of the major open problems in modern cryptography. We investigate this problem using concepts and methods of algorithmic randomness. In modern cryptography, the random oracle model is widely used as an imaginary framework in which the security of a cryptographic scheme is discussed. In the random oracle model, the cryptographic hash function used in a cryptographic scheme is formulated as a random variable uniformly distributed over all possibility of the function, called the random oracle. The main result of this paper is to show that, for any secure signature scheme in the random oracle model, there exists a specific computable function which can instantiate the random oracle while keeping the security originally proved in the random oracle model. In modern cryptography the generic group model is used also for a similar purpose to the random oracle model. We show that the same results hold for the generic group model. In the process of proving the results, we introduce the notion of effective security, demonstrating the importance of this notion in modern cryptography.
The Case for Explicit Coupling Constraints
Venue: arXiv cs.SE 2013
Year: 2013

A software element defined in one place is typically used in many places. When it is changed, all its occurrences may need to be changed too, which can severely hinder software evolution. This has led to the support of encapsulation in modern programming languages. Unfortunately, as is shown in this paper, this is not enough to express all the constraints that are needed to decouple programming elements that evolve at different paces. In this paper we show that: a language can be defined to easily express very general coupling constraints; violations to these constraints can be detected automatically. We then demonstrate several places where the need for coupling constraints arose in open-source Java projects. These constraints were expressed in comments when explicit constraints would have enabled automatic treatment.
Exponentiated Gradient LINUCB for Contextual Multi-Armed Bandits
Venue: arXiv cs.AI 2013
Year: 2013

We present Exponentiated Gradient LINUCB, an algorithm for con-textual multi-armed bandits. This algorithm uses Exponentiated Gradient to find the optimal exploration of the LINUCB. Within a deliberately designed offline simulation framework we conduct evaluations with real online event log data. The experimental results demonstrate that our algorithm outperforms surveyed algorithms.
Preventing Phishing Attacks using One Time Password and User Machine Identification
Venue: arXiv cs.CR 2013
Year: 2013

Phishing is a type of attack in which cyber criminals tricks the victims to steal their personal and financial data. It has become an organized criminal activity. Spoofed emails claiming to be from legitimate source are crafted in a way to lead victims to reveal their personal, financial data by misdirecting them to the counterfeit website. This research paper presents a novel approach to combat the Phishing attacks. An approach is proposed where user will retrieve the one time password by SMS or by alternate email address. After receiving the one time password the web server will create an encrypted token for the users computer or device for authentication. The encrypted token will be used for identification, any time user wishes to access the website he or she must request the new password. The one time password as name implies will expire after single use. The one time password and encrypted token is a smart way to tackle this problem.
Generalized Neutrosophic Soft Set
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we present a new concept called generalized neutrosophic soft set. This concept incorporates the beneficial properties of both generalized neutrosophic set introduced by A.A. Salama [7]and soft set techniques proposed by Molodtsov [4]. We also study some properties of this concept. Some definitions and operations have been introduced on generalized neutrosophic soft set. Finally we present an application of generalized neuutrosophic soft set in decision making problem.
An efficient algorithm for learning with semi-bandit feedback
Venue: arXiv cs.LG 2013
Year: 2013

We consider the problem of online combinatorial optimization under semi-bandit feedback. The goal of the learner is to sequentially select its actions from a combinatorial decision set so as to minimize its cumulative loss. We propose a learning algorithm for this problem based on combining the Follow-the-Perturbed-Leader (FPL) prediction method with a novel loss estimation procedure called Geometric Resampling (GR). Contrary to previous solutions, the resulting algorithm can be efficiently implemented for any decision set where efficient offline combinatorial optimization is possible at all. Assuming that the elements of the decision set can be described with d-dimensional binary vectors with at most m non-zero entries, we show that the expected regret of our algorithm after T rounds is O(m sqrt(dT log d)). As a side result, we also improve the best known regret bounds for FPL in the full information setting to O(m^(3/2) sqrt(T log d)), gaining a factor of sqrt(d/m) over previous bounds for this algorithm.
Stochastic Differential Games and Energy-Efficient Power Control
Venue: arXiv cs.NI 2013
Year: 2013

One of the contributions of this work is to formulate the problem of energy-efficient power control in multiple access channels (namely, channels which comprise several transmitters and one receiver) as a stochastic differential game. The players are the transmitters who adapt their power level to the quality of their time-varying link with the receiver, their battery level, and the strategy updates of the others. The proposed model not only allows one to take into account long-term strategic interactions but also long-term energy constraints. A simple sufficient condition for the existence of a Nash equilibrium in this game is provided and shown to be verified in a typical scenario. As the uniqueness and determination of equilibria are difficult issues in general, especially when the number of players goes large, we move to two special cases: the single player case which gives us some useful insights of practical interest and allows one to make connections with the case of large number of players. The latter case is treated with a mean-field game approach for which reasonable sufficient conditions for convergence and uniqueness are provided. Remarkably, this recent approach for large system analysis shows how scalability can be dealt with in large games and only relies on the individual state information assumption.
Predicting a User's Next Cell With Supervised Learning Based on Channel States
Venue: arXiv cs.NI 2013
Year: 2013

Knowing a user's next cell allows more efficient resource allocation and enables new location-aware services. To anticipate the cell a user will hand-over to, we introduce a new machine learning based prediction system. Therein, we formulate the prediction as a classification problem based on information that is readily available in cellular networks. Using only Channel State Information (CSI) and handover history, we perform classification by embedding Support Vector Machines (SVMs) into an efficient pre-processing structure. Simulation results from a Manhattan Grid scenario and from a realistic radio map of downtown Frankfurt show that our system provides timely prediction at high accuracy.
An Algorithm to Improve Performance over Multihop Wireless Mesh Network
Venue: arXiv cs.NI 2013
Year: 2013

Transmission Control Protocol (TCP) is the dominant reliable transport protocol utilized in the Internet. Improving the performance of TCP associated with the presence of multi-hop is one of the research challenges in wireless mesh networks. Wireless mesh networks have large round trip time variations and these variations are dependent on the number of hops. In wireless mesh network, when congestion loss and wireless loss are co-existed the number of packets dropped increases and will have adverse effects on TCP and its congestion control mechanism which leads to low throughput. Here we have designed a new TCP scheme for multi-hop wireless mesh networks, by modifying the sender side congestion control functionality of TCP NewReno, which is tuned towards improving the performance of TCP. The simulation results show that TCP SAC has higher performance than TCP NewReno, Reno, Sack and Vegas in multi-hop wireless mesh networks.
TCloud: A Dynamic Framework and Policies for Access Control across Multiple Domains in Cloud Computing
Venue: arXiv cs.DC 2013
Year: 2013

In a cloud computing environment, access control policy is an effective means of fortification cloud users and cloud resources services against security infringements. Based on analysis of current cloud computing security characteristics, the preamble of the concept of trust, role-based access control policy, combined with the characteristics of the cloud computing environment, there are multiple security management domains, so a new cross domain framework is for access control is proposed which is based on trust. It will establish and calculate the degree of trust in the single as well as multiple domains. Role Based Access Control is used for the implementation of the access control policies in a single domain environment with the introduction of the trust concept. In multiple domains the access control will be based on the conversion of roles. On the basis of trust, and role based access control model, a new novel framework of flexible cross domain access control framework is presented. The role assignment and conversion will take place dynamically.
Unsupervised ensemble of experts (EoE) framework for automatic binarization of document images
Venue: arXiv cs.CV 2013
Year: 2013

In recent years, a large number of binarization methods have been developed, with varying performance generalization and strength against different benchmarks. In this work, to leverage on these methods, an ensemble of experts (EoE) framework is introduced, to efficiently combine the outputs of various methods. The proposed framework offers a new selection process of the binarization methods, which are actually the experts in the ensemble, by introducing three concepts: confidentness, endorsement and schools of experts. The framework, which is highly objective, is built based on two general principles: (i) consolidation of saturated opinions and (ii) identification of schools of experts. After building the endorsement graph of the ensemble for an input document image based on the confidentness of the experts, the saturated opinions are consolidated, and then the schools of experts are identified by thresholding the consolidated endorsement graph. A variation of the framework, in which no selection is made, is also introduced that combines the outputs of all experts using endorsement-dependent weights. The EoE framework is evaluated on the set of participating methods in the H-DIBCO'12 contest and also on an ensemble generated from various instances of grid-based Sauvola method with promising performance.
Automatic Speech Recognition Using Template Model for Man-Machine Interface
Venue: arXiv cs.SD 2013
Year: 2013

Speech is a natural form of communication for human beings, and computers with the ability to understand speech and speak with a human voice are expected to contribute to the development of more natural man-machine interfaces. Computers with this kind of ability are gradually becoming a reality, through the evolution of speech recognition technologies. Speech is being an important mode of interaction with computers. In this paper Feature extraction is implemented using well-known Mel-Frequency Cepstral Coefficients (MFCC).Pattern matching is done using Dynamic time warping (DTW) algorithm.
Blind Adaptive Reduced-Rank Detectors for DS-UWB Systems Based on Joint Iterative Optimization and the Constrained Constant Modulus Criterion
Venue: arXiv cs.IT 2013
Year: 2013

A novel linear blind adaptive receiver based on joint iterative optimization (JIO) and the constrained constant modulus (CCM) design criterion is proposed for interference suppression in direct-sequence ultra-wideband (DS-UWB) systems. The proposed blind receiver consists of two parts, a transformation matrix that performs dimensionality reduction and a reduced-rank filter that produces the output. In the proposed receiver, the transformation matrix and the reduced-rank filter are updated jointly and iteratively to minimize the constant modulus (CM) cost function subject to a constraint. Adaptive implementations for the JIO receiver are developed by using the normalized stochastic gradient (NSG) and recursive least-squares (RLS) algorithms. In order to obtain a low-complexity scheme, the columns of the transformation matrix with the RLS algorithm are updated individually. Blind channel estimation algorithms for both versions (NSG and RLS) are implemented. Assuming the perfect timing, the JIO receiver only requires the spreading code of the desired user and the received data. Simulation results show that both versions of the proposed JIO receivers have excellent performance in suppressing the inter-symbol interference (ISI) and multiple access interference (MAI) with a low complexity.