OpenRaiser/Intern-Atlas huggingface dataset:
Similarity Measuring Approuch for Engineering Materials Selection
Venue: arXiv cs.AI 2013
Year: 2013

Advanced engineering materials design involves the exploration of massive multidimensional feature spaces, the correlation of materials properties and the processing parameters derived from disparate sources. The search for alternative materials or processing property strategies, whether through analytical, experimental or simulation approaches, has been a slow and arduous task, punctuated by infrequent and often expected discoveries. A few systematic efforts have been made to analyze the trends in data as a basis for classifications and predictions. This is particularly due to the lack of large amounts of organized data and more importantly the challenging of shifting through them in a timely and efficient manner. The application of recent advances in Data Mining on materials informatics is the state of art of computational and experimental approaches for materials discovery. In this paper similarity based engineering materials selection model is proposed and implemented to select engineering materials based on the composite materials constraints. The result reviewed from this model is sustainable for effective decision making in advanced engineering materials design applications.
Spectrum Sharing-based Multi-hop Decode-and-Forward Relay Networks under Interference Constraints: Performance Analysis and Relay Position Optimization
Venue: arXiv cs.IT 2013
Year: 2013

The exact closed-form expressions for outage probability and bit error rate of spectrum sharing-based multi-hop decodeand- forward (DF) relay networks in non-identical Rayleigh fading channels are derived. We also provide the approximate closed-form expression for the system ergodic capacity. Utilizing these tractable analytical formulas, we can study the impact of key network parameters on the performance of cognitivemulti-hop relay networks under interference constraints. Using a linear network model, we derive an optimum relay position scheme by numerically solving an optimization problem of balancing average signal-to-noise ratio (SNR) of each hop. The numerical results show that the optimal scheme leads to SNR performance gains of more than 1 dB. All the analytical expressions are verified by Monte-Carlo simulations confirming the advantage ofmultihop DF relaying networks in cognitive environments.
Constacyclic Codes over $F_p+vF_p$
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study constacyclic codes over $F_p+vF_p$, where $p$ is an odd prime and $v^2=v$. The polynomial generators of all constacyclic codes over $F_p+vF_p$ are characterized and their dual codes are also determined.
Improved QFT algorithm for power-of-two FFT
Venue: arXiv cs.DS 2013
Year: 2013

This paper shows that it is possible to improve the computational cost, the memory requirements and the accuracy of Quick Fourier Transform (QFT) algorithm for power-of-two FFT (Fast Fourier Transform) just introducing a slight modification in this algorithm. The new algorithm requires the same number of additions and multiplications of split-radix 3add/3mul, one of the most appreciated FFT algorithms appeared in the literature, but employing only half of the trigonometric constants. These results can elevate the QFT approach to the level of most used FFT procedures. A new quite general way to describe FFT algorithms, based on signal types and on a particular notation, is also proposed and used, highligting its advantages.
An Efficient Algorithm for Clustering of Large-Scale Mass Spectrometry Data
Venue: arXiv cs.DS 2013
Year: 2013

High-throughput spectrometers are capable of producing data sets containing thousands of spectra for a single biological sample. These data sets contain a substantial amount of redundancy from peptides that may get selected multiple times in a LC-MS/MS experiment. In this paper, we present an efficient algorithm, CAMS (Clustering Algorithm for Mass Spectra) for clustering mass spectrometry data which increases both the sensitivity and confidence of spectral assignment. CAMS utilizes a novel metric, called F-set, that allows accurate identification of the spectra that are similar. A graph theoretic framework is defined that allows the use of F-set metric efficiently for accurate cluster identifications. The accuracy of the algorithm is tested on real HCD and CID data sets with varying amounts of peptides. Our experiments show that the proposed algorithm is able to cluster spectra with very high accuracy in a reasonable amount of time for large spectral data sets. Thus, the algorithm is able to decrease the computational time by compressing the data sets while increasing the throughput of the data by interpreting low S/N spectra.
Fast and RIP-optimal transforms
Venue: arXiv cs.NA 2013
Year: 2013

We study constructions of $k \times n$ matrices $A$ that both (1) satisfy the restricted isometry property (RIP) at sparsity $s$ with optimal parameters, and (2) are efficient in the sense that only $O(n\log n)$ operations are required to compute $Ax$ given a vector $x$. Our construction is based on repeated application of independent transformations of the form $DH$, where $H$ is a Hadamard or Fourier transform and $D$ is a diagonal matrix with random $\{+1,-1\}$ elements on the diagonal, followed by any $k \times n$ matrix of orthonormal rows (e.g.\ selection of $k$ coordinates). We provide guarantees (1) and (2) for a larger regime of parameters for which such constructions were previously unknown. Additionally, our construction does not suffer from the extra poly-logarithmic factor multiplying the number of observations $k$ as a function of the sparsity $s$, as present in the currently best known RIP estimates for partial random Fourier matrices and other classes of structured random matrices.
Popular Matchings -- structure and cheating strategies
Venue: arXiv cs.DS 2013
Year: 2013

We consider the cheating strategies for the popular matchings problem. The popular matchings problem can be defined as follows: Let G = (A U P, E) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and the edges in E are ranked. Each agent ranks a subset of posts in an order of preference, possibly involving ties. A matching M is popular if there exists no matching M' such that the number of agents that prefer M' to M exceeds the number of agents that prefer M to M'. Consider a centralized market where agents submit their preferences and a central authority matches agents to posts according to the notion of popularity. Since a popular matching need not be unique, we assume that the central authority chooses an arbitrary popular matching. Let a1 be the sole manipulative agent who is aware of the true preference lists of all other agents. The goal of a1 is to falsify her preference list to get better always, that is, to improve the set of posts that she gets matched to as opposed to what she got when she was truthful. We show that the optimal cheating strategy for a single agent to get better always can be computed in O(\sqrt{n}m) time when preference lists are allowed to contain ties and in O(m+n) time when preference lists are all strict. Here n = |A| + |P| and m = |E|. To compute the cheating strategies, we develop a switching graph characterization of the popular matchings problem involving ties. The switching graph characterization was studied for the case of strict lists by McDermid and Irving (J. Comb. Optim. 2011) and it was open for the case of ties. The switching graph characterization for the case of ties is of independent interest and answers a part of the open questions posed by McDermid and Irving.
Improving VANET Protocols via Network Science
Venue: arXiv cs.NI 2013
Year: 2013

Developing routing protocols for Vehicular Ad Hoc Networks (VANETs) is a significant challenge in these large, self- organized and distributed networks. We address this challenge by studying VANETs from a network science perspective to develop solutions that act locally but influence the network performance globally. More specifically, we look at snapshots from highway and urban VANETs of different sizes and vehicle densities, and study parameters such as the node degree distribution, the clustering coefficient and the average shortest path length, in order to better understand the networks' structure and compare it to structures commonly found in large real world networks such as small-world and scale-free networks. We then show how to use this information to improve existing VANET protocols. As an illustrative example, it is shown that, by adding new mechanisms that make use of this information, the overhead of the urban vehicular broadcasting (UV-CAST) protocol can be reduced substantially with no significant performance degradation.
Tropical cryptography
Venue: arXiv cs.CR 2013
Year: 2013

We employ tropical algebras as platforms for several cryptographic schemes that would be vulnerable to linear algebra attacks were they based on "usual" algebras as platforms.
Utilizing ASP for Generating and Visualizing Argumentation Frameworks
Venue: arXiv cs.AI 2013
Year: 2013

Within the area of computational models of argumentation, the instantiation-based approach is gaining more and more attention, not at least because meaningful input for Dung's abstract frameworks is provided in that way. In a nutshell, the aim of instantiation-based argumentation is to form, from a given knowledge base, a set of arguments and to identify the conflicts between them. The resulting network is then evaluated by means of extension-based semantics on an abstract level, i.e. on the resulting graph. While several systems are nowadays available for the latter step, the automation of the instantiation process itself has received less attention. In this work, we provide a novel approach to construct and visualize an argumentation framework from a given knowledge base. The system we propose relies on Answer-Set Programming and follows a two-step approach. A first program yields the logic-based arguments as its answer-sets; a second program is then used to specify the relations between arguments based on the answer-sets of the first program. As it turns out, this approach not only allows for a flexible and extensible tool for instantiation-based argumentation, but also provides a new method for answer-set visualization in general.
Planning and Scheduling in Hybrid Domains Using Answer Set Programming
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we present an Action Language-Answer Set Programming based approach to solving planning and scheduling problems in hybrid domains - domains that exhibit both discrete and continuous behavior. We use action language H to represent the domain and then translate the resulting theory into an A-Prolog program. In this way, we reduce the problem of finding solutions to planning and scheduling problems to computing answer sets of A-Prolog programs. We cite a planning and scheduling example from the literature and show how to model it in H. We show how to translate the resulting H theory into an equivalent A-Prolog program. We compute the answer sets of the resulting program using a hybrid solver called EZCSP which loosely integrates a constraint solver with an answer set solver. The solver allows us reason about constraints over reals and compute solutions to complex planning and scheduling problems. Results have shown that our approach can be applied to any planning and scheduling problem in hybrid domains.
On Complex LLL Algorithm for Integer Forcing Linear Receivers
Venue: arXiv cs.IT 2013
Year: 2013

Integer-forcing (IF) linear receiver has been recently introduced for multiple-input multiple-output (MIMO) fading channels. The receiver has to compute an integer linear combination of the symbols as a part of the decoding process. In particular, the integer coefficients have to be chosen based on the channel realizations, and the choice of such coefficients is known to determine the receiver performance. The original known solution of finding these integers was based on exhaustive search. A practical algorithm based on Hermite-Korkine-Zolotareff (HKZ) and Minkowski lattice reduction algorithms was also proposed recently. In this paper, we propose a low-complexity method based on complex LLL algorithm to obtain the integer coefficients for the IF receiver. For the 2 X 2 MIMO channel, we study the effectiveness of the proposed method in terms of the ergodic rate. We also compare the bit error rate (BER) of our approach with that of other linear receivers, and show that the suggested algorithm outperforms the minimum mean square estimator (MMSE) and zero-forcing (ZF) linear receivers, but trades-off error performance for complexity in comparison with the IF receiver based on exhaustive search or on HKZ and Minkowski lattice reduction algorithms.
Pebbling, Entropy and Branching Program Size Lower Bounds
Venue: arXiv cs.CC 2013
Year: 2013

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et. al. (2012). Proving a super-polynomial lower bound for the size of nondeterministic thrifty branching programs (NTBP) would separate $NL$ from $P$ for thrifty models solving the tree evaluation problem. First, we show that {\em Read-Once NTBPs} are equivalent to whole black-white pebbling algorithms thus showing a tight lower bound (ignoring polynomial factors) for this model. We then introduce a weaker restriction of NTBPs called {\em Bitwise Independence}. The best known NTBPs (of size $O(k^{h/2+1})$) for the tree evaluation problem given by Cook et. al. (2012) are Bitwise Independent. As our main result, we show that any Bitwise Independent NTBP solving $TEP_{2}^{h}(k)$ must have at least $\frac{1}{2}k^{h/2}$ states. Prior to this work, lower bounds were known for NTBPs only for fixed heights $h=2,3,4$ (See Cook et. al. (2012)). We prove our results by associating a fractional black-white pebbling strategy with any bitwise independent NTBP solving the Tree Evaluation Problem. Such a connection was not known previously even for fixed heights. Our main technique is the entropy method introduced by Jukna and Z{á}k (2001) originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds given by Cook et. al. (2012) for deterministic branching programs for Tree Evaluation Problem can be obtained using this approach. Using this method, we also show tight lower bounds for any $k$-way deterministic branching program solving Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes.
Object-oriented Bayesian networks for a decision support system for antitrust enforcement
Venue: arXiv cs.AI 2013
Year: 2013

We study an economic decision problem where the actors are two firms and the Antitrust Authority whose main task is to monitor and prevent firms' potential anti-competitive behaviour and its effect on the market. The Antitrust Authority's decision process is modelled using a Bayesian network where both the relational structure and the parameters of the model are estimated from a data set provided by the Authority itself. A number of economic variables that influence this decision process are also included in the model. We analyse how monitoring by the Antitrust Authority affects firms' strategies about cooperation. Firms' strategies are modelled as a repeated prisoner's dilemma using object-oriented Bayesian networks. We show how the integration of firms' decision process and external market information can be modelled in this way. Various decision scenarios and strategies are illustrated.
Secrecy Capacity of Two-Hop Relay Assisted Wiretap Channels
Venue: arXiv cs.IT 2013
Year: 2013

Incorporating the physical layer characteristics to secure communications has received considerable attention in recent years. Moreover, cooperation with some nodes of network can give benefits of multiple-antenna systems, increasing the secrecy capacity of such channels. In this paper, we consider cooperative wiretap channel with the help of an Amplify and Forward (AF) relay to transmit confidential messages from source to legitimate receiver in the presence of an eavesdropper. In this regard, the secrecy capacity of AF relying is derived, assuming the relay is subject to a peak power constraint. To this end, an achievable secrecy rate for Gaussian input is evaluated through solving a non-convex optimization problem. Then, it is proved that any rates greater than this secrecy rate is not achievable. To do this, the capacity of a genie-aided channel as an upper bound for the secrecy capacity of the underlying channel is derived, showing this upper bound is equal to the computed achievable secrecy rate with Gaussian input. Accordingly, the corresponding secrecy capacity is compared to the Decode and Forward (DF) strategy which is served as the benchmark in the current work.
Parallel Computing of Discrete Element Method on GPU
Venue: arXiv cs.CE 2013
Year: 2013

We investigate applicability of GPU to DEM. NVIDIA's code obtained superior performance than CPU in computational time. A model of contact forces in NVIDIA's code is too simple for practical use. We modify this model by replacing it with the practical model. The simulation shows that the practical model obtains the computing speed 6 times faster than the practical one on CPU while 7 times slower than the simple one on GPU. The result are analyzed.
Linear Bandits in High Dimension and Recommendation Systems
Venue: arXiv cs.LG 2013
Year: 2013

A large number of online services provide automated recommendations to help users to navigate through a large collection of items. New items (products, videos, songs, advertisements) are suggested on the basis of the user's past history and --when available-- her demographic profile. Recommendations have to satisfy the dual goal of helping the user to explore the space of available items, while allowing the system to probe the user's preferences. We model this trade-off using linearly parametrized multi-armed bandits, propose a policy and prove upper and lower bounds on the cumulative "reward" that coincide up to constants in the data poor (high-dimensional) regime. Prior work on linear bandits has focused on the data rich (low-dimensional) regime and used cumulative "risk" as the figure of merit. For this data rich regime, we provide a simple modification for our policy that achieves near-optimal risk performance under more restrictive assumptions on the geometry of the problem. We test (a variation of) the scheme used for establishing achievability on the Netflix and MovieLens datasets and obtain good agreement with the qualitative predictions of the theory we develop.
Challenges for regional innovation policies in CEE countries: Spatial concentration and foreign control of US patenting
Venue: arXiv cs.CY 2013
Year: 2013

Using techniques of data collection and mapping as overlays to Google Maps--on the basis of patent information available online at the U.S. Patent and Trademark Office (USPTO)--we point at two major and interconnected challenges that policy-makers face in Central and Eastern Europe (CEE) when combating the lagging innovation performance. First, we address the spatial concentration by using a distribution analysis at the city level. The results suggest that patenting is concentrated in post-socialist territories more than in western nations and regions. However, there is not a single outstanding hub in CEE when one compares USPTO patents normalized for the respective population sizes. Secondly, we argue that dominance of foreign control over USPTO patents is mostly embodied in international co-operations at the individual level, and only rarely spilled-over to MNE subsidiaries. In our opinion, catching-up of CEE in terms of patenting is unlikely, unless innovation policy measures focus on growing hubs and target both domestic inventors and international relations of companies.
Carrier phase and amplitude estimation for phase shift keying using pilots and data
Venue: arXiv cs.IT 2013
Year: 2013

We consider least squares estimators of carrier phase and amplitude from a noisy communications signal that contains both pilot signals, known to the receiver, and data signals, unknown to the receiver. We focus on signaling constellations that have symbols evenly distributed on the complex unit circle, i.e., M-ary phase shift keying. We show, under reasonably mild conditions on the distribution of the noise, that the least squares estimator of carrier phase is strongly consistent and asymptotically normally distributed. However, the amplitude estimator is not consistent, but converges to a positive real number that is a function of the true carrier amplitude, the noise distribution and the size of the constellation. Our theoretical results can also be applied to the case where no pilot symbols exist, i.e., noncoherent detection. The results of Monte Carlo simulations are provided and these agree with the theoretical results.
Authentication Schemes Using Polynomials Over Non-Commutative Rings
Venue: arXiv cs.CR 2013
Year: 2013

Authentication is a process by which an entity,which could be a person or intended computer,establishes its identity to another entity.In private and public computer networks including the Internet,authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic.Internet business and many other transactions require a more stringent authentication process. The aim of this paper is to propose two authentication schemes based on general non-commutative rings. The key idea of the schemes is that for a given non-commutative ring; one can build polynomials on additive structure and takes them as underlying work structure. By doing so, one can implement authentication schemes, one of them being zero-knowledge interactive proofs of knowledge, on multiplicative structure of the ring. The security of the schemes is based on the intractability of the polynomial symmetrical decomposition problem over the given non-commutative ring.
On the Degrees of Freedom of the K-User Time Correlated Broadcast Channel with Delayed CSIT
Venue: arXiv cs.IT 2013
Year: 2013

The Degrees of Freedom (DoF) of a K-User MISO Broadcast Channel (BC) is studied when the Transmitter (TX) has access to a delayed channel estimate in addition to an imperfect estimate of the current channel. The current estimate could be for example obtained from prediction applied on past estimates, in the case where feedback delay is within the coherence time. Building on previous recent works on this setting with two users, the estimation error of the current channel is characterized by its scaling as P at the exponent α, where α=1 (resp. α=0) corresponds to an estimate being essentially perfect (resp. useless) in terms of DoF. In this work, we contribute to the characterization of the DoF region in such a setting by deriving an outerbound for the DoF region and by providing an achievable DoF region. The achievable DoF is obtained by developing a new alignment scheme, called the Kα-MAT scheme, which builds upon both the principle of the MAT alignment scheme from Maddah-Ali and Tse and Zero-Forcing to achieve a larger DoF when the delayed CSIT received is correlated with the instantaneous channel state.
Equivalence of Deterministic One-Counter Automata is NL-complete
Venue: arXiv cs.FL 2013
Year: 2013

We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson in 1975. Our main contribution is to prove that two deterministic one-counter automata are inequivalent if and only if they can be distinguished by a word of length polynomial in the size of the two input automata.