OpenRaiser/Intern-Atlas huggingface dataset:
Arithmetic Circuits and the Hadamard Product of Polynomials
Venue: arXiv cs.CC 2009
Year: 2009

Motivated by the Hadamard product of matrices we define the Hadamard product of multivariate polynomials and study its arithmetic circuit and branching program complexity. We also give applications and connections to polynomial identity testing. Our main results are the following. 1. We show that noncommutative polynomial identity testing for algebraic branching programs over rationals is complete for the logspace counting class $\ceql$, and over fields of characteristic $p$ the problem is in $\ModpL/\Poly$. 2.We show an exponential lower bound for expressing the Raz-Yehudayoff polynomial as the Hadamard product of two monotone multilinear polynomials. In contrast the Permanent can be expressed as the Hadamard product of two monotone multilinear formulas of quadratic size.
Cognitive MAC Protocols for General Primary Network Models
Venue: arXiv cs.NI 2009
Year: 2009

We consider the design of cognitive Medium Access Control (MAC) protocols enabling a secondary (unlicensed) transmitter-receiver pair to communicate over the idle periods of a set of primary (licensed) channels. More specifically, we propose cognitive MAC protocols optimized for both slotted and un-slotted primary networks. For the slotted structure, the objective is to maximize the secondary throughput while maintaining synchronization between the secondary pair and not causing interference to the primary network. Our investigations differentiate between two sensing scenarios. In the first, the secondary transmitter is capable of sensing all the primary channels, whereas it senses only a subset of the primary channels in the second scenario. In both cases, we propose blind MAC protocols that efficiently learn the statistics of the primary traffic on-line and asymptotically achieve the throughput obtained when prior knowledge of primary traffic statistics is available. For the un-slotted structure, the objective is to maximize the secondary throughput while satisfying an interference constraint on the primary network. Sensing-dependent periods are optimized for each primary channel yielding a MAC protocol which outperforms previously proposed techniques that rely on a single sensing period optimization.
Learning Object Location Predictors with Boosting and Grammar-Guided Feature Extraction
Venue: arXiv cs.CV 2009
Year: 2009

We present BEAMER: a new spatially exploitative approach to learning object detectors which shows excellent results when applied to the task of detecting objects in greyscale aerial imagery in the presence of ambiguous and noisy data. There are four main contributions used to produce these results. First, we introduce a grammar-guided feature extraction system, enabling the exploration of a richer feature space while constraining the features to a useful subset. This is specified with a rule-based generative grammar crafted by a human expert. Second, we learn a classifier on this data using a newly proposed variant of AdaBoost which takes into account the spatially correlated nature of the data. Third, we perform another round of training to optimize the method of converting the pixel classifications generated by boosting into a high quality set of (x, y) locations. Lastly, we carefully define three common problems in object detection and define two evaluation criteria that are tightly matched to these problems. Major strengths of this approach are: (1) a way of randomly searching a broad feature space, (2) its performance when evaluated on well-matched evaluation criteria, and (3) its use of the location prediction domain to learn object detectors as well as to generate detections that perform well on several tasks: object counting, tracking, and target detection. We demonstrate the efficacy of BEAMER with a comprehensive experimental evaluation on a challenging data set.
The Cost of Stability in Coalitional Games
Venue: arXiv cs.GT 2009
Year: 2009

A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the \emph{core}--the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the \emph{cost of stability (CoS)} as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures.
Evolution of Digital Logic Functionality via a Genetic Algorithm
Venue: arXiv cs.NE 2009
Year: 2009

Digital logic forms the functional basics of most modern electronic equipment and as such the creation of novel digital logic circuits is an active area of computer engineering research. This study demonstrates that genetic algorithms can be used to evolve functionally useful sets of logic gate interconnections to create useful digital logic circuits. The efficacy of this approach is illustrated via the evolution of AND, OR, XOR, NOR, and XNOR functionality from sets of NAND gates, thereby illustrating that evolutionary methods have the potential be applied to the design of digital electronics.
What type of distribution for packet delay in a global network should be used in the control theory?
Venue: arXiv cs.NI 2009
Year: 2009

In this paper correspondence between experimental data for packet delay and two theoretical types of distribution is investigated. Calculations have shown that the exponential distribution describes the data on network delay better, than truncated normal distribution. Precision experimental data to within microseconds are gathered by means of the RIPE Test Box. In addition to exact measurements the data gathered by means of the utility {\em ping} has been parsed that has not changed the main result. As a result, the equation for an exponential distribution, in the best way describing process of packet delay in a TCP/IP based network is written. The search algorithm for key parameters as for normal, and an exponential distribution is resulted.
Clone Theory and Algebraic Logic
Venue: arXiv cs.LO 2009
Year: 2009

The concept of a clone is central to many branches of mathematics, such as universal algebra, algebraic logic, and lambda calculus. Abstractly a clone is a category with two objects such that one is a countably infinite power of the other. Left and right algebras over a clone are covariant and contravariant functors from the category to that of sets respectively. In this paper we show that first-order logic can be studied effectively using the notions of right and left algebras over a clone. It is easy to translate the classical treatment of logic into our setting and prove all the fundamental theorems of first-order theory algebraically.
The Nondeterministic Waiting Time Algorithm: A Review
Venue: arXiv cs.FL 2009
Year: 2009

We present briefly the Nondeterministic Waiting Time algorithm. Our technique for the simulation of biochemical reaction networks has the ability to mimic the Gillespie Algorithm for some networks and solutions to ordinary differential equations for other networks, depending on the rules of the system, the kinetic rates and numbers of molecules. We provide a full description of the algorithm as well as specifics on its implementation. Some results for two well-known models are reported. We have used the algorithm to explore Fas-mediated apoptosis models in cancerous and HIV-1 infected T cells.
The Open Cloud Testbed: A Wide Area Testbed for Cloud Computing Utilizing High Performance Network Services
Venue: arXiv cs.DC 2009
Year: 2009

Recently, a number of cloud platforms and services have been developed for data intensive computing, including Hadoop, Sector, CloudStore (formerly KFS), HBase, and Thrift. In order to benchmark the performance of these systems, to investigate their interoperability, and to experiment with new services based on flexible compute node and network provisioning capabilities, we have designed and implemented a large scale testbed called the Open Cloud Testbed (OCT). Currently the OCT has 120 nodes in four data centers: Baltimore, Chicago (two locations), and San Diego. In contrast to other cloud testbeds, which are in small geographic areas and which are based on commodity Internet services, the OCT is a wide area testbed and the four data centers are connected with a high performance 10Gb/s network, based on a foundation of dedicated lightpaths. This testbed can address the requirements of extremely large data streams that challenge other types of distributed infrastructure. We have also developed several utilities to support the development of cloud computing systems and services, including novel node and network provisioning services, a monitoring system, and a RPC system. In this paper, we describe the OCT architecture and monitoring system. We also describe some benchmarks that we developed and some interoperability studies we performed using these benchmarks.
The Distributions in Nature and Entropy Principle
Venue: arXiv cs.DM 2009
Year: 2009

The derivation of the maximum entropy distribution of particles in boxes yields two kinds of distributions: a "bell-like" distribution and a long-tail distribution. The first one is obtained when the ratio between particles and boxes is low, and the second one - when the ratio is high. The obtained long tail distribution yields correctly the empirical Zipf law, Pareto's 20:80 rule and Benford's law. Therefore, it is concluded that the long tail and the "bell-like" distributions are outcomes of the tendency of statistical systems to maximize entropy.
Growth Rate of the Weight Distribution of Doubly-Generalized LDPC Codes: General Case and Efficient Evaluation
Venue: arXiv cs.IT 2009
Year: 2009

The growth rate of the weight distribution of irregular doubly-generalized LDPC (D-GLDPC) codes is developed and in the process, a new efficient numerical technique for its evaluation is presented. The solution involves simultaneous solution of a 4 x 4 system of polynomial equations. This represents the first efficient numerical technique for exact evaluation of the growth rate, even for LDPC codes. The technique is applied to two example D-GLDPC code ensembles.
Automatic local Gabor Features extraction for face recognition
Venue: arXiv cs.CV 2009
Year: 2009

We present in this paper a biometric system of face detection and recognition in color images. The face detection technique is based on skin color information and fuzzy classification. A new algorithm is proposed in order to detect automatically face features (eyes, mouth and nose) and extract their correspondent geometrical points. These fiducial points are described by sets of wavelet components which are used for recognition. To achieve the face recognition, we use neural networks and we study its performances for different inputs. We compare the two types of features used for recognition: geometric distances and Gabor coefficients which can be used either independently or jointly. This comparison shows that Gabor coefficients are more powerful than geometric distances. We show with experimental results how the importance recognition ratio makes our system an effective tool for automatic face detection and recognition.
Restart Strategy Selection using Machine Learning Techniques
Venue: arXiv cs.AI 2009
Year: 2009

Restart strategies are an important factor in the performance of conflict-driven Davis Putnam style SAT solvers. Selecting a good restart strategy for a problem instance can enhance the performance of a solver. Inspired by recent success applying machine learning techniques to predict the runtime of SAT solvers, we present a method which uses machine learning to boost solver performance through a smart selection of the restart strategy. Based on easy to compute features, we train both a satisfiability classifier and runtime models. We use these models to choose between restart strategies. We present experimental results comparing this technique with the most commonly used restart strategies. Our results demonstrate that machine learning is effective in improving solver performance.
Serializing the Parallelism in Parallel Communicating Pushdown Automata Systems
Venue: arXiv cs.FL 2009
Year: 2009

We consider parallel communicating pushdown automata systems (PCPA) and define a property called known communication for it. We use this property to prove that the power of a variant of PCPA, called returning centralized parallel communicating pushdown automata (RCPCPA), is equivalent to that of multi-head pushdown automata. The above result presents a new sub-class of returning parallel communicating pushdown automata systems (RPCPA) called simple-RPCPA and we show that it can be written as a finite intersection of multi-head pushdown automata systems.
Rewrite based Verification of XML Updates
Venue: arXiv cs.LO 2009
Year: 2009

We consider problems of access control for update of XML documents. In the context of XML programming, types can be viewed as hedge automata, and static type checking amounts to verify that a program always converts valid source documents into also valid output documents. Given a set of update operations we are particularly interested by checking safety properties such as preservation of document types along any sequence of updates. We are also interested by the related policy consistency problem, that is detecting whether a sequence of authorized operations can simulate a forbidden one. We reduce these questions to type checking problems, solved by computing variants of hedge automata characterizing the set of ancestors and descendants of the initial document type for the closure of parameterized rewrite rules.
Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections
Venue: arXiv cs.FL 2009
Year: 2009

In this paper, we present some results regarding the size complexity of Accepting Networks of Evolutionary Processors with Filtered Connections (ANEPFCs). We show that there are universal ANEPFCs of size 10, by devising a method for simulating 2-Tag Systems. This result significantly improves the known upper bound for the size of universal ANEPFCs which is 18. We also propose a new, computationally and descriptionally efficient simulation of nondeterministic Turing machines by ANEPFCs. More precisely, we describe (informally, due to space limitations) how ANEPFCs with 16 nodes can simulate in O(f(n)) time any nondeterministic Turing machine of time complexity f(n). Thus the known upper bound for the number of nodes in a network simulating an arbitrary Turing machine is decreased from 26 to 16.
Programming with Quantum Communication
Venue: arXiv cs.PL 2009
Year: 2009

This work develops a formal framework for specifying, implementing, and analysing quantum communication protocols. We provide tools for developing simple proofs and analysing programs which involve communication, both via quantum channels and exhibiting the LOCC (local operations, classical communication) paradigm.
Analysis of Internet Measurement Systems for Optimized Anomaly Detection System Design
Venue: arXiv cs.NI 2009
Year: 2009

Although there exist very accurate hardware systems for measuring traffic on the internet, their widespread use for analysis tasks is limited by their high cost. On the other hand, less expensive, software-based systems exist that are widely available and can be used to perform a number of simple analysis tasks. The caveat with using such software systems is that application of standard analysis methods cannot proceed blindly because inherent distortions exist in the measurements obtained from software systems. The goal of this paper is to analyze common Internet measurement systems to discover the effect of these distortions on common analysis tasks. Then by selecting one specific task, periodic signal detection, a more in-depth analysis is conducted which derives a signal representation to capture the salient features of the measurement and develops a periodic detection mechanism designed for the measurement system which outperforms an existing detection method not optimized for the measurement system. Finally, through experiments the importance of understanding the relationship between the input traffic, measurement system configuration and detection method performance is emphasized.
Fast Detour Computation for Ride Sharing
Venue: arXiv cs.DS 2009
Year: 2009

Todays ride sharing services still mimic a better billboard. They list the offers and allow to search for the source and target city, sometimes enriched with radial search. So finding a connection between big cities is quite easy. These places are on a list of designated origin and distination points. But when you want to go from a small town to another small town, even when they are next to a freeway, you run into problems. You can't find offers that would or could pass by the town easily with little or no detour. We solve this interesting problem by presenting a fast algorithm that computes the offers with the smallest detours w.r.t. a request. Our experiments show that the problem is efficiently solvable in times suitable for a web service implementation. For realistic database size we achieve lookup times of about 5ms and a matching rate of 90% instead of just 70% for the simple matching algorithms used today.
Multiple pattern classification by sparse subspace decomposition
Venue: arXiv cs.CV 2009
Year: 2009

A robust classification method is developed on the basis of sparse subspace decomposition. This method tries to decompose a mixture of subspaces of unlabeled data (queries) into class subspaces as few as possible. Each query is classified into the class whose subspace significantly contributes to the decomposed subspace. Multiple queries from different classes can be simultaneously classified into their respective classes. A practical greedy algorithm of the sparse subspace decomposition is designed for the classification. The present method achieves high recognition rate and robust performance exploiting joint sparsity.
Efficient Web Log Mining using Doubly Linked Tree
Venue: arXiv cs.IR 2009
Year: 2009

World Wide Web is a huge data repository and is growing with the explosive rate of about 1 million pages a day. As the information available on World Wide Web is growing the usage of the web sites is also growing. Web log records each access of the web page and number of entries in the web logs is increasing rapidly. These web logs, when mined properly can provide useful information for decision-making. The designer of the web site, analyst and management executives are interested in extracting this hidden information from web logs for decision making. Web access pattern, which is the frequently used sequence of accesses, is one of the important information that can be mined from the web logs. This information can be used to gather business intelligence to improve sales and advertisement, personalization for a user, to analyze system performance and to improve the web site organization. There exist many techniques to mine access patterns from the web logs. This paper describes the powerful algorithm that mines the web logs efficiently. Proposed algorithm firstly converts the web access data available in a special doubly linked tree. Each access is called an event. This tree keeps the critical mining related information in very compressed form based on the frequent event count. Proposed recursive algorithm uses this tree to efficiently find all access patterns that satisfy user specified criteria. To prove that our algorithm is efficient from the other GSP (Generalized Sequential Pattern) algorithms we have done experimental studies on sample data.
Convergence of Expected Utility for Universal AI
Venue: arXiv cs.AI 2009
Year: 2009

We consider a sequence of repeated interactions between an agent and an environment. Uncertainty about the environment is captured by a probability distribution over a space of hypotheses, which includes all computable functions. Given a utility function, we can evaluate the expected utility of any computational policy for interaction with the environment. After making some plausible assumptions (and maybe one not-so-plausible assumption), we show that if the utility function is unbounded, then the expected utility of any policy is undefined.
Randomized Online Algorithms for the Buyback Problem
Venue: arXiv cs.GT 2009
Year: 2009

In the matroid buyback problem, an algorithm observes a sequence of bids and must decide whether to accept each bid at the moment it arrives, subject to a matroid constraint on the set of accepted bids. Decisions to reject bids are irrevocable, whereas decisions to accept bids may be canceled at a cost which is a fixed fraction of the bid value. We present a new randomized algorithm for this problem, and we prove matching upper and lower bounds to establish that the competitive ratio of this algorithm, against an oblivious adversary, is the best possible. We also observe that when the adversary is adaptive, no randomized algorithm can improve the competitive ratio of the optimal deterministic algorithm. Thus, our work completely resolves the question of what competitive ratios can be achieved by randomized algorithms for the matroid buyback problem.
Outage analysis of Block-Fading Gaussian Interference Channels
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers the asymptotic behavior of two-source block-fading single-antenna Gaussian interference channels in the high-SNR regime by means of the diversity-multiplexing tradeoff. We consider a general setting where the users and the average channel gains are not restricted to be symmetric. Our results are not just extensions of previous results for symmetric networks, as our setting covers scenarios that are not possible under the symmetric assumption, such as the case of "mixed" interference, i.e., when difference sources have different distances from their intended receivers. We derive upper and lower bounds on the diversity. We show that for a fairly large set of channel parameters the two bounds coincides.