OpenRaiser/Intern-Atlas huggingface dataset:
On the Effect of Connectedness for Biobjective Multiple and Long Path Problems
Venue: arXiv cs.NE 2012
Year: 2012

Recently, the property of connectedness has been claimed to give a strong motivation on the design of local search techniques for multiobjective combinatorial optimization (MOCO). Indeed, when connectedness holds, a basic Pareto local search, initialized with at least one non-dominated solution, allows to identify the efficient set exhaustively. However, this becomes quickly infeasible in practice as the number of efficient solutions typically grows exponentially with the instance size. As a consequence, we generally have to deal with a limited-size approximation, where a good sample set has to be found. In this paper, we propose the biobjective multiple and long path problems to show experimentally that, on the first problems, even if the efficient set is connected, a local search may be outperformed by a simple evolutionary algorithm in the sampling of the efficient set. At the opposite, on the second problems, a local search algorithm may successfully approximate a disconnected efficient set. Then, we argue that connectedness is not the single property to study for the design of local search heuristics for MOCO. This work opens new discussions on a proper definition of the multiobjective fitness landscape.
On the Neutrality of Flowshop Scheduling Fitness Landscapes
Venue: arXiv cs.NE 2012
Year: 2012

Solving efficiently complex problems using metaheuristics, and in particular local searches, requires incorporating knowledge about the problem to solve. In this paper, the permutation flowshop problem is studied. It is well known that in such problems, several solutions may have the same fitness value. As this neutrality property is an important one, it should be taken into account during the design of optimization methods. Then in the context of the permutation flowshop, a deep landscape analysis focused on the neutrality property is driven and propositions on the way to use this neutrality to guide efficiently the search are given.
Clustering of Local Optima in Combinatorial Fitness Landscapes
Venue: arXiv cs.NE 2012
Year: 2012

Using the recently proposed model of combinatorial landscapes: local optima networks, we study the distribution of local optima in two classes of instances of the quadratic assignment problem. Our results indicate that the two problem instance classes give rise to very different configuration spaces. For the so-called real-like class, the optima networks possess a clear modular structure, while the networks belonging to the class of random uniform instances are less well partitionable into clusters. We briefly discuss the consequences of the findings for heuristically searching the corresponding problem spaces.
Nonblocker in H-minor free graphs: kernelization meets discharging
Venue: arXiv cs.DS 2012
Year: 2012

Perhaps the best known kernelization result is the kernel of size 335k for the Planar Dominating Set problem by Alber et al. [JACM 2004], later improved to 67k by Chen et al. [SICOMP 2007]. This result means roughly, that the problem of finding the smallest dominating set in a planar graph is easy when the optimal solution is small. On the other hand, it is known that Planar Dominating Set parameterized by k'=|V|-k (also known as Planar Nonblocker) has a kernel of size 2k'. This means that Planar Dominating Set is easy when the optimal solution is very large. We improve the kernel for Planar Nonblocker to 7/4k'. This also implies that Planar Dominating Set has no kernel of size at most (7/3-epsilon)k, for any epsilon>0, unless P=NP. This improves the previous lower bound of (2-epsilon)k of Chen et al. Both of these results immediately generalize to H-minor free graphs (without changing the constants). In our proof of the bound on the kernel size we use a variant of the discharging method (used e.g. in the proof of the four color theorem). We give some arguments that this method is natural in the context of kernelization and we hope it will be applied to get improved kernel size bounds for other problems as well. As a by-product we show a result which might be of independent interest: every n-vertex graph with no isolated vertices and such that every pair of degree 1 vertices is at distance at least 5 and every pair of degree 2 vertices is at distance at least 2 has a dominating set of size at most 3/7n.
An Adaptive Online Ad Auction Scoring Algorithm for Revenue Maximization
Venue: arXiv cs.GT 2012
Year: 2012

Sponsored search becomes an easy platform to match potential consumers' intent with merchants' advertising. Advertisers express their willingness to pay for each keyword in terms of bids to the search engine. When a user's query matches the keyword, the search engine evaluates the bids and allocates slots to the advertisers that are displayed along side the unpaid algorithmic search results. The advertiser only pays the search engine when its ad is clicked by the user and the price-per-click is determined by the bids of other competing advertisers.
Finite Alphabet Iterative Decoders, Part II: Improved Guaranteed Error Correction of LDPC Codes via Iterative Decoder Diversity
Venue: arXiv cs.IT 2012
Year: 2012

Recently, we introduced a new class of finite alphabet iterative decoders (FAIDs) for low-density parity-check (LDPC) codes. These decoders are capable of surpassing belief propagation in the error floor region on the Binary Symmetric channel with much lower complexity. In this paper, we introduce a a novel scheme to further increase the guaranteed error correction capability from what is achievable by a FAID on column-weight-three LDPC codes. The proposed scheme uses a plurality of FAIDs which collectively correct more error patterns than a single FAID on a given code. The collection of FAIDs utilized by the scheme is judiciously chosen to ensure that individual decoders have different decoding dynamics and correct different error patterns. Consequently, they can collectively correct a diverse set of error patterns, which is referred to as decoder diversity. We provide a systematic method to generate the set of FAIDs for decoder diversity on a given code based on the knowledge of the most harmful trapping sets present in the code. Using the well-known column-weight-three $(155,64)$ Tanner code with $d_{min}$ = 20 as an example, we describe the method in detail and show that the guaranteed error correction capability can be significantly increased with decoder diversity.
Intruder deducibility constraints with negation. Decidability and application to secured service compositions
Venue: arXiv cs.CR 2012
Year: 2012

The problem of finding a mediator to compose secured services has been reduced in our former work to the problem of solving deducibility constraints similar to those employed for cryptographic protocol analysis. We extend in this paper the mediator synthesis procedure by a construction for expressing that some data is not accessible to the mediator. Then we give a decision procedure for verifying that a mediator satisfying this non-disclosure policy can be effectively synthesized. This procedure has been implemented in CL-AtSe, our protocol analysis tool. The procedure extends constraint solving for cryptographic protocol analysis in a significative way as it is able to handle negative deducibility constraints without restriction. In particular it applies to all subterm convergent theories and therefore covers several interesting theories in formal security analysis including encryption, hashing, signature and pairing.
Motion Planning Of an Autonomous Mobile Robot Using Artificial Neural Network
Venue: arXiv cs.RO 2012
Year: 2012

The paper presents the electronic design and motion planning of a robot based on decision making regarding its straight motion and precise turn using Artificial Neural Network (ANN). The ANN helps in learning of robot so that it performs motion autonomously. The weights calculated are implemented in microcontroller. The performance has been tested to be excellent.
Service Oriented Architecture A Revolution For Comprehensive Web Based Project Management Software
Venue: arXiv cs.SE 2012
Year: 2012

Service Oriented Architecture A Revolution for Project Management Software has changed the way projects today are moving on the fly with the help of web services booming the industry. Service oriented architecture improves performance and the communication between the distributed and remote teams. Web Services to Provide Project Management software the visibility and control of the application development lifecycle-giving a better control over the entire development process, from the management stage through development. The goal of Service Oriented Architecture for Project Management Software is to produce a product that is delivered on time, within the allocated budget, and with the capabilities expected by the customer. Web Services in Project management Project management software is basically a properly managed project and has a clear, communicated, and managed set of goals and objectives, whose progress is quantifiable and controlled. Resources are used effectively and efficiently to produce the desired product. With the help of service oriented architecture we can move into the future without abandoning the past. A project usually has a communicated set of processes that cover the daily activities of the project, forming the project framework. As a result, every team member understands their roles, responsibilities and how they fit into the big picture thus promoting the efficient use of resources.
Mapping and Reducing the Brain on the Cloud
Venue: arXiv cs.DC 2012
Year: 2012

The emergence of cloud computing has enabled an incredible growth in available hardware resources at very low costs. These resources are being increasingly utilized by corporations for scalable analysis of "big data" problems. In this work, we explore the possibility of using commodity hardware such as Amazon EC2 for performing large scale scientific computation. In particular, we simulate interconnected cortical neurons using MapReduce. We build and model a network of 1000 spiking cortical neurons in Hadoop, an opensource implementation of MapReduce, and present results.
Control and Synthesis of Non-Interferent Timed Systems
Venue: arXiv cs.LO 2012
Year: 2012

In this paper, we focus on the synthesis of secure timed systems which are modelled as timed automata. The security property that the system must satisfy is a non-interference property. Intuitively, non-interference ensures the absence of any causal dependency from a high-level domain to a lower-level domain. Various notions of non-interference have been defined in the literature, and in this paper we focus on Strong Non-deterministic Non-Interference (SNNI) and two (bi)simulation based variants thereof (CSNNI and BSNNI). We consider timed non-interference properties for timed systems specified by timed automata and we study the two following problems: (1) check whether it is possible to find a sub-system so that it is non-interferent; if yes (2) compute a (largest) sub-system which is non-interferent.
Secrecy Sum-Rates for Multi-User MIMO Regularized Channel Inversion Precoding
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose a linear precoder for the downlink of a multi-user MIMO system with multiple users that potentially act as eavesdroppers. The proposed precoder is based on regularized channel inversion (RCI) with a regularization parameter $α$ and power allocation vector chosen in such a way that the achievable secrecy sum-rate is maximized. We consider the worst-case scenario for the multi-user MIMO system, where the transmitter assumes users cooperate to eavesdrop on other users. We derive the achievable secrecy sum-rate and obtain the closed-form expression for the optimal regularization parameter $α_{\mathrm{LS}}$ of the precoder using large-system analysis. We show that the RCI precoder with $α_{\mathrm{LS}}$ outperforms several other linear precoding schemes, and it achieves a secrecy sum-rate that has same scaling factor as the sum-rate achieved by the optimum RCI precoder without secrecy requirements. We propose a power allocation algorithm to maximize the secrecy sum-rate for fixed $α$. We then extend our algorithm to maximize the secrecy sum-rate by jointly optimizing $α$ and the power allocation vector. The jointly optimized precoder outperforms RCI with $α_{\mathrm{LS}}$ and equal power allocation by up to 20 percent at practical values of the signal-to-noise ratio and for 4 users and 4 transmit antennas.
On the Hardness of Network Design for Bottleneck Routing Games
Venue: arXiv cs.GT 2012
Year: 2012

In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We first show that bottleneck routing games do not suffer from Braess's paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as Ω(n^{0.121}) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^{0.121-\eps}), for any constant \eps > 0. On the positive side, we show how to compute an almost optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all used edges. The running time is determined by the total number of paths, and is quasipolynomial when the number of paths is quasipolynomial.
Efficient Identity-Based and Authenticated Key Agreement Protocol
Venue: arXiv cs.CR 2012
Year: 2012

Several identity based and implicitly authenticated key agreement protocols have been proposed in recent years and none of them has achieved all required security properties. In this paper, we propose an efficient identity-based and authenticated key agreement protocol IDAK using Weil/Tate pairing. The security of IDAK is proved in Bellare-Rogaway model. Several required properties for key agreement protocols are not implied by the Bellare-Rogaway model. We proved these properties for IDAK separately.
Survey and comparison for Open and closed sources in cloud computing
Venue: arXiv cs.DC 2012
Year: 2012

Cloud computing is a new technology widely studied in recent years. Now there are many cloud platforms both in industry and in academic circle. How to understand and use these platforms is a big issue. A detailed comparison has been presented in this paper focused on the aspects such as the architecture, characteristics, application and so on. To know the differences between open source and close source in cloud environment we mention some examples for Software-as-a-Service, Platform-as-a-Service, and Infrastructure-as-a-Service. We made comparison between them. Before conclusion we demonstrate some convergences and differences between open and closed platform, but we realized open source should be the best option.
Password Protected Smart Card and Memory Stick Authentication Against Off-line Dictionary Attacks
Venue: arXiv cs.CR 2012
Year: 2012

In this paper, we study the security requirements for remote authentication with password protected smart card. In recent years, several protocols for password-based authenticated key exchange have been proposed. These protocols are used for the protection of password based authentication between a client and a remote server. In this paper, we will focus on the password based authentication between a smart card owner and smart card via an untrusted card reader. In a typical scenario, a smart card owner inserts the smart card into an untrusted card reader and input the password via the card reader in order for the smart card to carry out the process of authentication with a remote server. In this case, we want to guarantee that the card reader will not be able to impersonate the card owner in future without the smart card itself. Furthermore, the smart card could be stolen. If this happens, we want the assurance that an adversary could not use the smart card to impersonate the card owner even though the sample space of passwords may be small enough to be enumerated by an off-line adversary. At the end of this paper, we further extend our results to credential storage on portable non-tamper resistant storage devices such as USB memory sticks.
On the Conjecture on APN Functions
Venue: arXiv cs.IT 2012
Year: 2012

An almost perfect nonlinear (APN) function (necessarily a polynomial function) on a finite field $\mathbb{F}$ is called exceptional APN, if it is also APN on infinitely many extensions of $\mathbb{F}$. In this article we consider the most studied case of $\mathbb{F}=\mathbb{F}_{2^n}$. A conjecture of Janwa-Wilson and McGuire-Janwa-Wilson (1993/1996), settled in 2011, was that the only exceptional monomial APN functions are the monomials $x^n$, where $n=2^i+1$ or $n={2^{2i}-2^i+1}$ (the Gold or the Kasami exponents respectively). A subsequent conjecture states that any exceptional APN function is one of the monomials just described. One of our result is that all functions of the form $f(x)=x^{2^k+1}+h(x)$ (for any odd degree $h(x)$, with a mild condition in few cases), are not exceptional APN, extending substantially several recent results towards the resolution of the stated conjecture.
LT Codes For Efficient and Reliable Distributed Storage Systems Revisited
Venue: arXiv cs.IT 2012
Year: 2012

LT codes and digital fountain techniques have received significant attention from both academics and industry in the past few years. There have also been extensive interests in applying LT code techniques to distributed storage systems such as cloud data storage in recent years. However, Plank and Thomason's experimental results show that LDPC code performs well only asymptotically when the number of data fragments increases and it has the worst performance for small number of data fragments (e.g., less than 100). In their INFOCOM 2012 paper, Cao, Yu, Yang, Lou, and Hou proposed to use exhaustive search approach to find a deterministic LT code that could be used to decode the original data content correctly in distributed storage systems. However, by Plank and Thomason's experimental results, it is not clear whether the exhaustive search approach will work efficiently or even correctly. This paper carries out the theoretical analysis on the feasibility and performance issues for applying LT codes to distributed storage systems. By employing the underlying ideas of efficient Belief Propagation (BP) decoding process in LT codes, this paper introduces two classes of codes called flat BP-XOR codes and array BP-XOR codes (which can be considered as a deterministic version of LT codes). We will show the equivalence between the edge-colored graph model and degree-one-and-two encoding symbols based array BP-XOR codes. Using this equivalence result, we are able to design general array BP-XOR codes using graph based results. Similarly, based on this equivalence result, we are able to get new results for edge-colored graph models using results from array BP-XOR codes.
Bellman Error Based Feature Generation using Random Projections on Sparse Spaces
Venue: arXiv cs.LG 2012
Year: 2012

We address the problem of automatic generation of features for value function approximation. Bellman Error Basis Functions (BEBFs) have been shown to improve the error of policy evaluation with function approximation, with a convergence rate similar to that of value iteration. We propose a simple, fast and robust algorithm based on random projections to generate BEBFs for sparse feature spaces. We provide a finite sample analysis of the proposed method, and prove that projections logarithmic in the dimension of the original space are enough to guarantee contraction in the error. Empirical results demonstrate the strength of this method.
Linear Dependent Types in a Call-by-Value Scenario (Long Version)
Venue: arXiv cs.LO 2012
Year: 2012

Linear dependent types allow to precisely capture both the extensional behaviour and the time complexity of lambda terms, when the latter are evaluated by Krivine's abstract machine. In this work, we show that the same paradigm can be applied to call-by-value evaluation. A system of linear dependent types for Plotkin's PCF is introduced, called dlPCFV, whose types reflect the complexity of evaluating terms in the so-called CEK machine. dlPCFV is proved to be sound, but also relatively complete: every true statement about the extensional and intentional behaviour of terms can be derived, provided all true index term inequalities can be used as assumptions.
Complexity of testing morphic primitivity
Venue: arXiv cs.FL 2012
Year: 2012

We analyze the algorithm in [Holub, 2009], which decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in O(mn), where n is the length of the word and m the size of the alphabet.
Haptic BCI Paradigm based on Somatosensory Evoked Potential
Venue: arXiv cs.HC 2012
Year: 2012

A new concept and an online prototype of haptic BCI paradigm are presented. Our main goal is to develop a new, alternative and low cost paradigm, with open-source hardware and software components. We also report results obtained with the novel dry EEG electrodes based signal acquisition system by g.tec, which further improves experimental comfort. We address the following points: a novel application of the BCI; a new methodological approach used compared to earlier projects; a new benefit for potential users of a BCI; the approach working online/in real-time; development of a novel stimuli delivery hardware and software. The results with five healthy subjects and discussion of future developments conclude this submission.
Semantic Information Retrieval Using Ontology In University Domain
Venue: arXiv cs.IR 2012
Year: 2012

Today's conventional search engines hardly do provide the essential content relevant to the user's search query. This is because the context and semantics of the request made by the user is not analyzed to the full extent. So here the need for a semantic web search arises. SWS is upcoming in the area of web search which combines Natural Language Processing and Artificial Intelligence. The objective of the work done here is to design, develop and implement a semantic search engine- SIEU(Semantic Information Extraction in University Domain) confined to the university domain. SIEU uses ontology as a knowledge base for the information retrieval process. It is not just a mere keyword search. It is one layer above what Google or any other search engines retrieve by analyzing just the keywords. Here the query is analyzed both syntactically and semantically. The developed system retrieves the web results more relevant to the user query through keyword expansion. The results obtained here will be accurate enough to satisfy the request made by the user. The level of accuracy will be enhanced since the query is analyzed semantically. The system will be of great use to the developers and researchers who work on web. The Google results are re-ranked and optimized for providing the relevant links. For ranking an algorithm has been applied which fetches more apt results for the user query.