OpenRaiser/Intern-Atlas huggingface dataset:
A Full Derandomization of Schoening's k-SAT Algorithm
Venue: arXiv cs.DS 2010
Year: 2010

Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O((a+epsilon)^n * poly(n)), where epsilon > 0 can be made arbitrarily small.
Hybrid tractability of soft constraint problems
Venue: arXiv cs.AI 2010
Year: 2010

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Soft constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of soft constraint problems; that is, properties which guarantee tractability of the given soft constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of soft constraints in the instance (such as submodularity). We present several novel hybrid classes of soft constraint problems, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary soft constraints. An important tool in our investigation will be the notion of forbidden substructures.
Three-Level Parallel J-Jacobi Algorithms for Hermitian Matrices
Venue: arXiv cs.NA 2010
Year: 2010

The paper describes several efficient parallel implementations of the one-sided hyperbolic Jacobi-type algorithm for computing eigenvalues and eigenvectors of Hermitian matrices. By appropriate blocking of the algorithms an almost ideal load balancing between all available processors/cores is obtained. A similar blocking technique can be used to exploit local cache memory of each processor to further speed up the process. Due to diversity of modern computer architectures, each of the algorithms described here may be the method of choice for a particular hardware and a given matrix size. All proposed block algorithms compute the eigenvalues with relative accuracy similar to the original non-blocked Jacobi algorithm.
Performance of Optimum and Suboptimum Combining Diversity Reception for Binary DPSK over Independent, Nonidentical Rayleigh Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

This paper is concerned with the error performance analysis of binary differential phase shift keying with differential detection over the nonselective, Rayleigh fading channel with combining diversity reception. Space antenna diversity reception is assumed. The diversity branches are independent, but have nonidentically distributed statistics. The fading process in each branch is assumed to have an arbitrary Doppler spectrum with arbitrary Doppler bandwidth. Both optimum diversity reception and suboptimum diversity reception are considered. Results available previously apply only to the case of first and second-order diversity. Our results are more general in that the order of diversity is arbitrary. Moreover, the bit error probability (BEP) result is obtained in an exact, closed-form expression which shows the behavior of the BEP as an explict function of the one-bit-interval fading correlation coefficient at the matched filter output, the mean signal-to-noise ratio per bit per branch and the order of diversity. A simple, more easily computable Chernoff bound to the BEP of the optimum diversity detector is also derived.
Cluster Editing: Kernelization based on Edge Cuts
Venue: arXiv cs.DS 2010
Year: 2010

Kernelization algorithms for the {\sc cluster editing} problem have been a popular topic in the recent research in parameterized computation. Thus far most kernelization algorithms for this problem are based on the concept of {\it critical cliques}. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the {\sc cluster editing} problem. Our techniques are based on the study of the relationship between {\sc cluster editing} and graph edge-cuts. As an application, we present an ${\cal O}(n^2)$-time algorithm that constructs a $2k$ kernel for the {\it weighted} version of the {\sc cluster editing} problem. Our result meets the best kernel size for the unweighted version for the {\sc cluster editing} problem, and significantly improves the previous best kernel of quadratic size for the weighted version of the problem.
An Influence Diagram-Based Approach for Estimating Staff Training in Software Industry
Venue: arXiv cs.SE 2010
Year: 2010

The successful completion of a software development process depends on the analytical capability and foresightedness of the project manager. For the project manager, the main intriguing task is to manage the risk factors as they adversely influence the completion deadline. One such key risk factor is staff training. The risk of this factor can be avoided by pre-judging the amount of training required by the staff. So, a procedure is required to help the project manager make this decision. This paper presents a system that uses influence diagrams to implement the risk model to aid decision making. The system also considers the cost of conducting the training, based on various risk factors such as, (i) Lack of experience with project software; (ii) Newly appointed staff; (iii) Staff not well versed with the required quality standards; and (iv) Lack of experience with project environment. The system provides estimated requirement details for staff training at the beginning of a software development project.
Evacuation of rectilinear polygons
Venue: arXiv cs.DS 2010
Year: 2010

We investigate the problem of creating fast evacuation plans for buildings that are modeled as grid polygons, possibly containing exponentially many cells. We study this problem in two contexts: the ``confluent'' context in which the routes to exits remain fixed over time, and the ``non-confluent'' context in which routes may change. Confluent evacuation plans are simpler to carry out, as they allocate contiguous regions to exits; non-confluent allocation can possibly create faster evacuation plans. We give results on the hardness of creating the evacuation plans and strongly polynomial algorithms for finding confluent evacuation plans when the building has two exits. We also give a pseudo-polynomial time algorithm for non-confluent evacuation plans. Finally, we show that the worst-case bound between confluent and non-confluent plans is 2-2/(k+1).
Switching between Hidden Markov Models using Fixed Share
Venue: arXiv cs.LG 2010
Year: 2010

In prediction with expert advice the goal is to design online prediction algorithms that achieve small regret (additional loss on the whole data) compared to a reference scheme. In the simplest such scheme one compares to the loss of the best expert in hindsight. A more ambitious goal is to split the data into segments and compare to the best expert on each segment. This is appropriate if the nature of the data changes between segments. The standard fixed-share algorithm is fast and achieves small regret compared to this scheme. Fixed share treats the experts as black boxes: there are no assumptions about how they generate their predictions. But if the experts are learning, the following question arises: should the experts learn from all data or only from data in their own segment? The original algorithm naturally addresses the first case. Here we consider the second option, which is more appropriate exactly when the nature of the data changes between segments. In general extending fixed share to this second case will slow it down by a factor of T on T outcomes. We show, however, that no such slowdown is necessary if the experts are hidden Markov models.
On the Transmission-Computation-Energy Tradeoff in Wireless and Fixed Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, a framework for the analysis of the transmission-computation-energy tradeoff in wireless and fixed networks is introduced. The analysis of this tradeoff considers both the transmission energy as well as the energy consumed at the receiver to process the received signal. While previous work considers linear decoder complexity, which is only achieved by uncoded transmission, this paper claims that the average processing (or computation) energy per symbol depends exponentially on the information rate of the source message. The introduced framework is parametrized in a way that it reflects properties of fixed and wireless networks alike. The analysis of this paper shows that exponential complexity and therefore stronger codes are preferable at low data rates while linear complexity and therefore uncoded transmission becomes preferable at high data rates. The more the computation energy is emphasized (such as in fixed networks), the less hops are optimal and the lower is the benefit of multi-hopping. On the other hand, the higher the information rate of the single-hop network, the higher the benefits of multi-hopping. Both conclusions are underlined by analytical results.
BSSSN: Bit String Swapping Sorting Network for Reversible Logic Synthesis
Venue: arXiv cs.AR 2010
Year: 2010

In this paper, we have introduced the notion of UselessGate and ReverseOperation. We have also given an algorithm to implement a sorting network for reversible logic synthesis based on swapping bit strings. The network is constructed in terms of n*n Toffoli Gates read from left to right and it has shown that there will be no more gates than the number of swappings the algorithm requires. The gate complexity of the network is O(n2). The number of gates in the network can be further reduced by template reduction technique and removing UselessGate from the network.
An Architecture of Active Learning SVMs with Relevance Feedback for Classifying E-mail
Venue: arXiv cs.IR 2010
Year: 2010

In this paper, we have proposed an architecture of active learning SVMs with relevance feedback (RF)for classifying e-mail. This architecture combines both active learning strategies where instead of using a randomly selected training set, the learner has access to a pool of unlabeled instances and can request the labels of some number of them and relevance feedback where if any mail misclassified then the next set of support vectors will be different from the present set otherwise the next set will not change. Our proposed architecture will ensure that a legitimate e-mail will not be dropped in the event of overflowing mailbox. The proposed architecture also exhibits dynamic updating characteristics making life as difficult for the spammer as possible.
Entanglement-assisted quantum low-density parity-check codes
Venue: arXiv cs.IT 2010
Year: 2010

This paper develops a general method for constructing entanglement-assisted quantum low-density parity-check (LDPC) codes, which is based on combinatorial design theory. Explicit constructions are given for entanglement-assisted quantum error-correcting codes (EAQECCs) with many desirable properties. These properties include the requirement of only one initial entanglement bit, high error correction performance, high rates, and low decoding complexity. The proposed method produces infinitely many new codes with a wide variety of parameters and entanglement requirements. Our framework encompasses various codes including the previously known entanglement-assisted quantum LDPC codes having the best error correction performance and many new codes with better block error rates in simulations over the depolarizing channel. We also determine important parameters of several well-known classes of quantum and classical LDPC codes for previously unsettled cases.
Spiking Neurons with ASNN Based-Methods for the Neural Block Cipher
Venue: arXiv cs.CR 2010
Year: 2010

Problem statement: This paper examines Artificial Spiking Neural Network (ASNN) which inter-connects group of artificial neurons that uses a mathematical model with the aid of block cipher. The aim of undertaken this research is to come up with a block cipher where by the keys are randomly generated by ASNN which can then have any variable block length. This will show the private key is kept and do not have to be exchange to the other side of the communication channel so it present a more secure procedure of key scheduling. The process enables for a faster change in encryption keys and a network level encryption to be implemented at a high speed without the headache of factorization. Approach: The block cipher is converted in public cryptosystem and had a low level of vulnerability to attack from brute, and moreover can able to defend against linear attacks since the Artificial Neural Networks (ANN) architecture convey non-linearity to the encryption/decryption procedures. Result: In this paper is present to use the Spiking Neural Networks (SNNs) with spiking neurons as its basic unit. The timing for the SNNs is considered and the output is encoded in 1's and 0's depending on the occurrence or not occurrence of spikes as well as the spiking neural networks use a sign function as activation function, and present the weights and the filter coefficients to be adjust, having more degrees of freedom than the classical neural networks. Conclusion: In conclusion therefore, encryption algorithm can be deployed in communication and security applications where data transfers are most crucial. So this paper, the neural block cipher proposed where the keys are generated by the SNN and the seed is considered the public key which generates the both keys on both sides In future therefore a new research will be conducted on the Spiking Neural Network (SNN) impacts on communication.
Spatio-Temporal Modeling of Wireless Users Internet Access Patterns Using Self-Organizing Maps
Venue: arXiv cs.NI 2010
Year: 2010

User online behavior and interests will play a central role in future mobile networks. We introduce a systematic method for large-scale multi-dimensional analysis of online activity for thousands of mobile users across 79 buildings over a variety of web domains. We propose a modeling approach based on self-organizing maps (SOM) for discovering, organizing and visualizing different mobile users' trends from billions of WLAN records. We find surprisingly that users' trends based on domains and locations can be accurately modeled using a self-organizing map with clearly distinct characteristics. We also find many non-trivial correlations between different types of web domains and locations. Based on our analysis, we introduce a mixture model as an initial step towards realistic simulation of wireless network usage.
Structural properties of 1-planar graphs and an application to acyclic edge coloring
Venue: arXiv cs.DM 2010
Year: 2010

A graph is called 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we establish a local property of 1-planar graphs which describes the structure in the neighborhood of small vertices (i.e. vertices of degree no more than seven). Meanwhile, some new classes of light graphs in 1-planar graphs with the bounded degree are found. Therefore, two open problems presented by Fabrici and Madaras [The structure of 1-planar graphs, Discrete Mathematics, 307, (2007), 854-865] are solved. Furthermore, we prove that each 1-planar graph $G$ with maximum degree $Δ(G)$ is acyclically edge $L$-choosable where $L=\max\{2Δ(G)-2,Δ(G)+83\}$.
Approximate Top-k Retrieval from Hidden Relations
Venue: arXiv cs.DB 2010
Year: 2010

We consider the evaluation of approximate top-k queries from relations with a-priori unknown values. Such relations can arise for example in the context of expensive predicates, or cloud-based data sources. The task is to find an approximate top-k set that is close to the exact one while keeping the total processing cost low. The cost of a query is the sum of the costs of the entries that are read from the hidden relation. A novel aspect of this work is that we consider prior information about the values in the hidden matrix. We propose an algorithm that uses regression models at query time to assess whether a row of the matrix can enter the top-k set given that only a subset of its values are known. The regression models are trained with existing data that follows the same distribution as the relation subjected to the query. To evaluate the algorithm and to compare it with a method proposed previously in literature, we conduct experiments using data from a context sensitive Wikipedia search engine. The results indicate that the proposed method outperforms the baseline algorithms in terms of the cost while maintaining a high accuracy of the returned results.
Prediction by Compression
Venue: arXiv cs.IT 2010
Year: 2010

It is well known that text compression can be achieved by predicting the next symbol in the stream of text data based on the history seen up to the current symbol. The better the prediction the more skewed the conditional probability distribution of the next symbol and the shorter the codeword that needs to be assigned to represent this next symbol. What about the opposite direction ? suppose we have a black box that can compress text stream. Can it be used to predict the next symbol in the stream ? We introduce a criterion based on the length of the compressed data and use it to predict the next symbol. We examine empirically the prediction error rate and its dependency on some compression parameters.
Fixed-point and coordinate descent algorithms for regularized kernel methods
Venue: arXiv cs.LG 2010
Year: 2010

In this paper, we study two general classes of optimization algorithms for kernel methods with convex loss function and quadratic norm regularization, and analyze their convergence. The first approach, based on fixed-point iterations, is simple to implement and analyze, and can be easily parallelized. The second, based on coordinate descent, exploits the structure of additively separable loss functions to compute solutions of line searches in closed form. Instances of these general classes of algorithms are already incorporated into state of the art machine learning software for large scale problems. We start from a solution characterization of the regularized problem, obtained using sub-differential calculus and resolvents of monotone operators, that holds for general convex loss functions regardless of differentiability. The two methodologies described in the paper can be regarded as instances of non-linear Jacobi and Gauss-Seidel algorithms, and are both well-suited to solve large scale problems.
Improving the Performance of maxRPC
Venue: arXiv cs.AI 2010
Year: 2010

Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that can achieve considerably stronger pruning than arc consistency. However, existing maxRRC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose techniques that can boost the performance of maxRPC algorithms. These include the combined use of two data structures to avoid many redundant constraint checks, and heuristics for the efficient ordering and execution of certain operations. Based on these, we propose two closely related algorithms. The first one which is a maxRPC algorithm with optimal O(end^3) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one approximates maxRPC and has O(en^2d^4) time complexity, but a restricted version with O(end^4) complexity can be very efficient when used during search. Both algorithms have O(ed) space complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a more than viable alternative to arc consistency on many problems.
A secret sharing scheme using groups
Venue: arXiv cs.CR 2010
Year: 2010

In this paper a secret sharing scheme based on the word problem in groups is introduced. The security of the scheme and possible variations are discussed in section 2. The article concludes with the suggestion of two categories of platform groups for the implementation of the scheme.
A Competitive Analysis for Balanced Transactional Memory Workloads
Venue: arXiv cs.DC 2010
Year: 2010

We consider transactional memory contention management in the context of balanced workloads, where if a transaction is writing, the number of write operations it performs is a constant fraction of its total reads and writes. We explore the theoretical performance boundaries of contention management in balanced workloads from the worst-case perspective by presenting and analyzing two new contention management algorithms. The first algorithm Clairvoyant is O(\surd s)-competitive, where s is the number of shared resources. This algorithm depends on explicitly knowing the conflict graph. The second algorithm Non-Clairvoyant is O(\surd s \cdot log n)-competitive, with high probability, which is only a O(log n) factor worse, but does not require knowledge of the conflict graph, where n is the number of transactions. Both of these algorithms are greedy. We also prove that the performance of Clairvoyant is tight since there is no contention management algorithm that is better than O((\surd s)^(1-ε))-competitive for any constant ε> 0, unless NP\subseteq ZPP. To our knowledge, these results are significant improvements over the best previously known O(s) competitive ratio bound.
Not only a lack of right definitions: Arguments for a shift in information-processing paradigm
Venue: arXiv cs.AI 2010
Year: 2010

Machine Consciousness and Machine Intelligence are not simply new buzzwords that occupy our imagination. Over the last decades, we witness an unprecedented rise in attempts to create machines with human-like features and capabilities. However, despite widespread sympathy and abundant funding, progress in these enterprises is far from being satisfactory. The reasons for this are twofold: First, the notions of cognition and intelligence (usually borrowed from human behavior studies) are notoriously blurred and ill-defined, and second, the basic concepts underpinning the whole discourse are by themselves either undefined or defined very vaguely. That leads to improper and inadequate research goals determination, which I will illustrate with some examples drawn from recent documents issued by DARPA and the European Commission. On the other hand, I would like to propose some remedies that, I hope, would improve the current state-of-the-art disgrace.
Three Controlled Experiments in Software Engineering with the Two-Tier Programming Toolkit: Final Report
Venue: arXiv cs.SE 2010
Year: 2010

Three controlled experiments testing the benefits that Java programmers gain from using the Two-Tier Programming Toolkit have recently been concluded. The first experiment offers statistically significant evidence (p-value: 0.02) that programmers who undertook only minimal (1-hour) training in using the current prototype exhibit 76% productivity gains in key tasks in software development and maintenance. The second experiment shows that the use of the TTP Toolkit is likely (p-value: 0.10) to almost triple the accuracy of programmers performing tasks associated with software quality. The third experiment shows that the TTP Toolkit does not offer significant productivity gains in performing very short (under 10 min.) tasks.