OpenRaiser/Intern-Atlas huggingface dataset:
Mixture Gaussian Signal Estimation with L_infty Error Metric
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of estimating an input signal from noisy measurements in both parallel scalar Gaussian channels and linear mixing systems. The performance of the estimation process is quantified by the $\ell_\infty$ norm error metric. We first study the minimum mean $\ell_\infty$ error estimator in parallel scalar Gaussian channels, and verify that, when the input is independent and identically distributed (i.i.d.) mixture Gaussian, the Wiener filter is asymptotically optimal with probability 1. For linear mixing systems with i.i.d. sparse Gaussian or mixture Gaussian inputs, under the assumption that the relaxed belief propagation (BP) algorithm matches Tanaka's fixed point equation, applying the Wiener filter to the output of relaxed BP is also asymptotically optimal with probability 1. However, in order to solve the practical problem where the signal dimension is finite, we apply an estimation algorithm that has been proposed in our previous work, and illustrate that an $\ell_\infty$ error minimizer can be approximated by an $\ell_p$ error minimizer provided the value of $p$ is properly chosen.
Soft computing-based calibration of microplane M4 model parameters: Methodology and validation
Venue: arXiv cs.CE 2013
Year: 2013

Constitutive models for concrete based on the microplane concept have repeatedly proven their ability to well-reproduce its non-linear response on material as well as structural scales. The major obstacle to a routine application of this class of models is, however, the calibration of microplane-related constants from macroscopic data. The goal of this paper is two-fold: (i) to introduce the basic ingredients of a robust inverse procedure for the determination of dominant parameters of the M4 model proposed by Bazant and co-workers based on cascade Artificial Neural Networks trained by Evolutionary Algorithm and (ii) to validate the proposed methodology against a representative set of experimental data. The obtained results demonstrate that the soft computing-based method is capable of delivering the searched response with an accuracy comparable to the values obtained by expert users.
Manipulation in Clutter with Whole-Arm Tactile Sensing
Venue: arXiv cs.RO 2013
Year: 2013

We begin this paper by presenting our approach to robot manipulation, which emphasizes the benefits of making contact with the world across the entire manipulator. We assume that low contact forces are benign, and focus on the development of robots that can control their contact forces during goal-directed motion. Inspired by biology, we assume that the robot has low-stiffness actuation at its joints, and tactile sensing across the entire surface of its manipulator. We then describe a novel controller that exploits these assumptions. The controller only requires haptic sensing and does not need an explicit model of the environment prior to contact. It also handles multiple contacts across the surface of the manipulator. The controller uses model predictive control (MPC) with a time horizon of length one, and a linear quasi-static mechanical model that it constructs at each time step. We show that this controller enables both real and simulated robots to reach goal locations in high clutter with low contact forces. Our experiments include tests using a real robot with a novel tactile sensor array on its forearm reaching into simulated foliage and a cinder block. In our experiments, robots made contact across their entire arms while pushing aside movable objects, deforming compliant objects, and perceiving the world.
Linear Precoding for Broadcast Channels with Confidential Messages under Transmit-Side Channel Correlation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we analyze the performance of regularized channel inversion (RCI) precoding in multiple-input single-output (MISO) broadcast channels with confidential messages under transmit-side channel correlation. We derive a deterministic equivalent for the achievable per-user secrecy rate which is almost surely exact as the number of transmit antennas and the number of users grow to infinity in a fixed ratio, and we determine the optimal regularization parameter that maximizes the secrecy rate. Furthermore, we obtain deterministic equivalents for the secrecy rates achievable by: (i) zero forcing precoding and (ii) single user beamforming. The accuracy of our analysis is validated by simulations of finite-size systems.
A Security Protocol for the Identification and Data Encrypt Key Management of Secure Mobile Devices
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we proposed an identification and data encrypt key manage protocol that can be used in some security system based on such secure devices as secure USB memories or RFIDs, which are widely used for identifying persons or other objects recently. In general, the default functions of the security system using a mobile device are the authentication for the owner of the device and secure storage of data stored on the device. We proposed a security model that consists of the server and mobile devices in order to realize these security features. In this model we defined the secure communication protocol for the authentication and management of data encryption keys using a private key encryption algorithm with the public key between the server and mobile devices. In addition, we was performed the analysis for the attack to the communication protocol between the mobile device and server. Using the communication protocol, the system will attempt to authenticate the mobile device. The data decrypt key is transmitted only if the authentication process is successful. The data in the mobile device can be decrypted using the key. Our analysis proved that this Protocol ensures anonymity, prevents replay attacks and realizes the interactive identification between the security devices and the authentication server.
New Polynomial Cases of the Weighted Efficient Domination Problem
Venue: arXiv cs.DM 2013
Year: 2013

Let G be a finite undirected graph. A vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete even for very restricted graph classes. In particular, the ED problem remains NP-complete for 2P3-free graphs and thus for P7-free graphs. We show that the weighted version of the problem (abbreviated WED) is solvable in polynomial time on various subclasses of 2P3-free and P7-free graphs, including (P2+P4)-free graphs, P5-free graphs and other classes. Furthermore, we show that a minimum weight e.d. consisting only of vertices of degree at most 2 (if one exists) can be found in polynomial time. This contrasts with our NP-completeness result for the ED problem on planar bipartite graphs with maximum degree 3.
Guarded Variable Automata over Infinite Alphabets
Venue: arXiv cs.FL 2013
Year: 2013

We define guarded variable automata (GVAs), a simple extension of finite automata over infinite alphabets. In this model the transitions are labelled by letters or variables ranging over an infinite alphabet and guarded by conjunction of equalities and disequalities. GVAs are well-suited for modeling component-based applications such as web services. They are closed under intersection, union, concatenation and Kleene operator, and their nonemptiness problem is PSPACE-complete. We show that the simulation preorder of GVAs is decidable. Our proof relies on the characterization of the simulation by means of games and strategies. This result can be applied to service composition synthesis.
On the Complexity of Verifying Regular Properties on Flat Counter Systems
Venue: arXiv cs.LO 2013
Year: 2013

Among the approximation methods for the verification of counter systems, one of them consists in model-checking their flat unfoldings. Unfortunately, the complexity characterization of model-checking problems for such operational models is not always well studied except for reachability queries or for Past LTL. In this paper, we characterize the complexity of model-checking problems on flat counter systems for the specification languages including first-order logic, linear mu-calculus, infinite automata, and related formalisms. Our results span different complexity classes (mainly from PTime to PSpace) and they apply to languages in which arithmetical constraints on counter values are systematically allowed. As far as the proof techniques are concerned, we provide a uniform approach that focuses on the main issues.
Adaptive Switched Lattice Reduction-Aided Linear Detection Techniques for MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

Lattice reduction (LR) aided multiple-input-multiple-out (MIMO) linear detection can achieve the maximum receive diversity of the maximum likelihood detection (MLD). By emloying the most commonly used Lenstra, Lenstra, and L. Lovasz (LLL) algorithm, an equivalent channel matrix which is shorter and nearly orthogonal is obtained. And thus the noise enhancement is greatly reduced by employing the LR-aided detection. One problem is that the LLL algorithm can not guarantee to find the optimal basis. The optimal lattice basis can be found by the Korkin and Zolotarev (KZ) reduction. However, the KZ reduction is infeasible in practice due to its high complexity. In this paper, a simple algorithm is proposed based on the complex LLL (CLLL) algorithm to approach the optimal performance while maintaining a reasonable complexity.
Transmission Sequence Design and Allocation for Wide Area Ad Hoc Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we examine the problem of designing and allocating transmission sequences to users in a mobile ad hoc network that has no spatial boundary. A basic tenet of the transmission sequence approach for addressing media access control is that under normal operating conditions, there is no feedback triggered re-transmission. This obviously is a major departure from the Slotted-ALOHA or CSMA type approaches. While these solutions enjoy excellent throughput performance, a fundamental drawback is that they are based on feedback information. For systems without naturally defined central controller that can play the role of a base station, the task of providing feedback information could easily become unmanageable. This highlights the advantage of the feedback-free approach. A second advantage is the ability to handle unlimited spatial coverage. We propose in this paper a concept for media access control that is akin to frequency reuse. However, instead of reusing frequency, the new approach allows transmission sequences be reused. A study of the transmission sequence approach against other approaches is conducted by comparing the minimal frame lengths that can guarantee the existence of conflict-free transmissions.
Software Design Principles of a DFS Tower A-CWP Prototype
Venue: arXiv cs.SE 2013
Year: 2013

SESAR is supposed to boost the development of new operational procedures together with the supporting systems in order to modernize the pan-European air traffic management (ATM). One consequence of this development is that more and more information is presented to - and has to be processed by - air traffic control officers (ATCOs). Thus, there is a strong need for a software design concept that fosters the development of an advanced (tower) controller working position (A-CWP) that comprehensively integrates the still counting amount of information while reducing the data management workload of ATCOs. We report on our first hands-on experiences obtained during the development of an A-CWP prototype that was used in two SESAR validation sessions.
Public key exchange using semidirect product of (semi)groups
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we describe a brand new key exchange protocol based on a semidirect product of (semi)groups (more specifically, on extension of a (semi)group by automorphisms), and then focus on practical instances of this general idea. Our protocol can be based on any group, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when our protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. Here we also suggest a particular non-commutative semigroup (of matrices) as the platform and show that security of the relevant protocol is based on a quite different assumption compared to that of the standard Diffie-Hellman protocol.
When Privacy meets Security: Leveraging personal information for password cracking
Venue: arXiv cs.CR 2013
Year: 2013

Passwords are widely used for user authentication and, despite their weaknesses, will likely remain in use in the foreseeable future. Human-generated passwords typically have a rich structure, which makes them susceptible to guessing attacks. In this paper, we study the effectiveness of guessing attacks based on Markov models. Our contributions are two-fold. First, we propose a novel password cracker based on Markov models, which builds upon and extends ideas used by Narayanan and Shmatikov (CCS 2005). In extensive experiments we show that it can crack up to 69% of passwords at 10 billion guesses, more than all probabilistic password crackers we compared again t. Second, we systematically analyze the idea that additional personal information about a user helps in speeding up password guessing. We find that, on average and by carefully choosing parameters, we can guess up to 5% more passwords, especially when the number of attempts is low. Furthermore, we show that the gain can go up to 30% for passwords that are actually based on personal attributes. These passwords are clearly weaker and should be avoided. Our cracker could be used by an organization to detect and reject them. To the best of our knowledge, we are the first to systematically study the relationship between chosen passwords and users' personal information. We test and validate our results over a wide collection of leaked password databases.
EM-based Semi-blind Channel Estimation in AF Two-Way Relay Networks
Venue: arXiv cs.IT 2013
Year: 2013

We propose an expectation maximization (EM)-based algorithm for semi-blind channel estimation of reciprocal channels in amplify-and-forward (AF) two-way relay networks (TWRNs). By incorporating both data samples and pilots into the estimation, the proposed algorithm provides substantially higher accuracy than the conventional training-based approach. Furthermore, the proposed algorithm has a linear computational complexity per iteration and converges after a small number of iterations.
A new modeling approach to the safety evaluation of N-modular redundant computer systems in presence of imperfect maintenance
Venue: arXiv cs.SE 2013
Year: 2013

A large number of safety-critical control systems are based on N-modular redundant architectures, using majority voters on the outputs of independent computation units. In order to assess the compliance of these architectures with international safety standards, the frequency of hazardous failures must be analyzed by developing and solving proper formal models. Furthermore, the impact of maintenance faults has to be considered, since imperfect maintenance may degrade the safety integrity level of the system. In this paper we present both a failure model for voting architectures based on Bayesian Networks and a maintenance model based on Continuous Time Markov Chains, and we propose to combine them according to a compositional multiformalism modeling approach in order to analyze the impact of imperfect maintenance on the system safety. We also show how the proposed approach promotes the reuse and the interchange of models as well the interchange of solving tools.
Hardware Implementation of Algorithm for Cryptanalysis
Venue: arXiv cs.CR 2013
Year: 2013

Cryptanalysis of block ciphers involves massive computations which are independent of each other and can be instantiated simultaneously so that the solution space is explored at a faster rate. With the advent of low cost Field Programmable Gate Arrays, building special purpose hardware for computationally intensive applications has now become possible. For this the Data Encryption Standard is used as a proof of concept. This paper presents the design for Hardware implementation of DES cryptanalysis on FPGA using exhaustive key search. Two architectures viz. Rolled and Unrolled DES architecture are compared and based on experimental result the Rolled architecture is implemented on FPGA. The aim of this work is to make cryptanalysis faster and better.
Counting approximately-shortest paths in directed acyclic graphs
Venue: arXiv cs.DS 2013
Year: 2013

Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most L. We extend the algorithm for the case of two (or more) instances of the same problem. That is, given two graphs that have the same vertices and edges and differ only in edge-weights, and given two threshold-weights L_1 and L_2, we show how to approximately count the s-t paths that have length at most L_1 in the first graph and length at most L_2 in the second graph. We believe that our algorithms should find application in counting approximate solutions of related optimization problems, where finding an (optimum) solution can be reduced to the computation of a shortest path in a purpose-built auxiliary graph.
A New Trusted and E-Commerce Architecture for Cloud Computing
Venue: arXiv cs.DC 2013
Year: 2013

Cloud computing platform gives people the opportunity for sharing resources, services and information among the people of the whole world. In private cloud system, information is shared among the persons who are in that cloud. Presently, different types of internet based systems are running in Cloud Computing environment. E-commerce is one of them. Present models are not secured enough for executing e-transactions easily, especially in cloud platform. Again, most of the time, clients fail to distinguish between the good online business companies and the bad one, which discourages clients and companies to migrate in cloud. In this paper, we have proposed a newer e-commerce architecture depends on encryption based secured and fuzzy logic based certain trust model which will be helpful to solve present e-commerce problems. We had discussed about the whole working procedure of the model in this paper. Finally, at the end of this paper, we have discussed some experimental results about our proposed model which will help to show the validity of our model.
Automated Synthesis of Controllers for Search and Rescue from Temporal Logic Specifications
Venue: arXiv cs.SY 2013
Year: 2013

In this thesis, the synthesis of correct-by-construction controllers for robots assisting in Search and Rescue (SAR) is considered. In recent years, the development of robots assisting in disaster mitigation in urban environments has been actively encouraged, since robots can be deployed in dangerous and hazardous areas where human SAR operations would not be possible. In order to meet the reliability requirements in SAR, the specifications of the robots are stated in Linear Temporal Logic and synthesized into finite state machines that can be executed as controllers. The resulting controllers are purely discrete and maintain an ongoing interaction with their environment by changing their internal state according to the inputs they receive from sensors or other robots. Since SAR robots have to cooperate in order to complete the required tasks, the synthesis of controllers that together achieve a common goal is considered. This distributed synthesis problem is provably undecidable, hence it cannot be solved in full generality, but a set of design principles is introduced in order to develop specialized synthesizable specifications. In particular, communication and cooperation are resolved by introducing a verified standardized communication protocol and preempting negotiations between robots. The robots move on a graph on which we consider the search for stationary and moving targets. Searching for moving targets is cast into a game of cops and robbers, and specifications implementing a winning strategy are developed so that the number of robots required is minimized. The viability of the methods is demonstrated by synthesizing controllers for robots performing search and rescue for stationary targets and searching for moving targets. It is shown that the controllers are guaranteed to achieve the common goal of finding and rescuing the targets.
Controlling the Depth, Size, and Number of Subtrees for Two-variable Logic on Trees
Venue: arXiv cs.LO 2013
Year: 2013

Verification of properties of first order logic with two variables FO2 has been investigated in a number of contexts. Over arbitrary structures it is known to be decidable with NEXPTIME complexity, with finitely satisfiable formulas having exponential-sized models. Over word structures, where FO2 is known to have the same expressiveness as unary temporal logic, the same properties hold. Over finite labelled ordered trees FO2 is also of interest: it is known to have the same expressiveness as navigational XPath, a common query language for XML documents. Prior work on XPath and FO2 gives a 2EXPTIME bound for satisfiability of FO2. In this work we give the first in-depth look at the complexity of FO2 on trees, and on the size and depth of models. We show that the doubly-exponential bound is not tight, and neither do the NEXPTIME-completeness results from the word case carry over: the exact complexity varies depending on the vocabulary used, the presence or absence of a schema, and the encoding used for labels. Our results depend on an analysis of subformula types in models of FO2 formulas, including techniques for controlling the number of distinct subtrees, the depth, and the size of a witness to finite satisfiability for FO2 sentences over trees.
Efficiency Guarantees in Auctions with Budgets
Venue: arXiv cs.GT 2013
Year: 2013

In settings where players have a limited access to liquidity, represented in the form of budget constraints, efficiency maximization has proven to be a challenging goal. In particular, the social welfare cannot be approximated by a better factor then the number of players. Therefore, the literature has mainly resorted to Pareto-efficiency as a way to achieve efficiency in such settings. While successful in some important scenarios, in many settings it is known that either exactly one incentive-compatible auction that always outputs a Pareto-efficient solution, or that no truthful mechanism can always guarantee a Pareto-efficient outcome. Traditionally, impossibility results can be avoided by considering approximations. However, Pareto-efficiency is a binary property (is either satisfied or not), which does not allow for approximations. In this paper we propose a new notion of efficiency, called \emph{liquid welfare}. This is the maximum amount of revenue an omniscient seller would be able to extract from a certain instance. We explain the intuition behind this objective function and show that it can be 2-approximated by two different auctions. Moreover, we show that no truthful algorithm can guarantee an approximation factor better than 4/3 with respect to the liquid welfare, and provide a truthful auction that attains this bound in a special case. Importantly, the liquid welfare benchmark also overcomes impossibilities for some settings. While it is impossible to design Pareto-efficient auctions for multi-unit auctions where players have decreasing marginal values, we give a deterministic $O(\log n)$-approximation for the liquid welfare in this setting.