Monocultures are hard to find in practice

The statement that computer networks executing essentially the same software (for example, a software's various versions and configurations; such as Linux or Windows) present a higher risk of cascading failures than more diversified networks when a serious vulnerability is discovered in that common software has two inherent problems. The first problem is with the concept of "essentially the same software", and the second is with the meaning of "cascading failures".     

Random low-degree polynomials are hard to approximate

We study the problem of how well a typical multivariate polynomial can be approximated by lower-degree polynomials over mathbb F{mathbb F} . We prove that almost all degree d polynomials have only an exponentially small correlation with all polynomials of degree at most d − 1, for all degrees d up to Θ(n). That is, a random degree d polynomial does not admit a good approximation of lower degree. In order to prove this, we prove far tail estimates on the distribution of the bias of a random low-degree polynomial. Recently, several results regarding the weight distribution of Reed–Muller codes were obtained. Our results can be interpreted as a new large deviation bound on the weight distribution of Reed–Muller codes.     

Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

Relocation problems are hard

We show that General Relocation is NP-Complete. However, specific Relocation subprobiems, such as relocation feasibility or Johnson's scheduling problem are shown to be of almost linear complexity.     

Easy problems are sometimes hard

We present a detailed experimental investigation of the easy-hard-easy phase transition for randomly generated instances of satisfiability problems. Problems in the hard part of the phase transition have been extensively used for benchmarking satisfiability algorithms. This study demonstrates that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classes and regions of the phase transition considered hard. These difficult problems are either hard unsatisfiable problems or are satisfiable problems which give a hard unsatisfiable subproblem following a wrong split. Whilst these hard unsatisfiable problems may have short proofs, these appear to be difficult to find, and other proofs are long and hard.     

Alternatives to SNA

The advantages of changing from a network configured with IBM's preSNA equipment (hosts, host software, communications processors, terminals) to one using SNA are reviewed. Two viable alternatives to SNA are considered. One relies on data comunications architectures as developed by two vendors (NCR-Comten, CCl) of plug-compatible replacements for IBM's 3704/3705 communications controllers. Packet-switched public data networks provide a second alternative. Host software remains unchanged in both instances.     

Better Alternatives to OSPF Routing

The current standard for intra-domain network routing, Open Shortest Path First (OSPF), suffers from a number of problems-the tunable parameters (the weights) are hard to optimize, the chosen paths are not robust under changes in traffic or network state, and some network links are over-used at the expense of others. We present prototypical scenarios that illustrate these problems. Then we propose several variants of a protocol to eliminate or alleviate them and demonstrate the improvements in performance under those scenarios. We also prove that these protocols never perform significantly worse than OSPF and show that for at least a limited class of network topologies, it is possible to find efficiently the optimal weight settings. Some of the problems with OSPF are well known; indeed, there are several routing protocols that perform better than OSPF in routing quality (i.e., in terms of congestion, delay, etc.). OSPF’s popularity persists in part because of its efficiency with respect to several resource bounds. In contrast, many competing protocols that provide routing superior to OSPF are computationally prohibitive. Motivated by this consideration, we designed our protocols not only to achieve better routing quality than OSPF, but also to use resources in amount comparable with OSPF with respect to offline broadcast communication, size of and time to compute routing tables, packet delivery latency, and packet header structure and size.     

Learning to recognize three-dimensional objects

A learning account for the problem of object recognition is developed within the probably approximately correct (PAC) model of learnability. The key assumption underlying this work is that objects can be recognized (or discriminated) using simple representations in terms of syntactically simple relations over the raw image. Although the potential number of these simple relations could be huge, only a few of them are actually present in each observed image, and a fairly small number of those observed are relevant to discriminating an object. We show that these properties can be exploited to yield an efficient learning approach in terms of sample and computational complexity within the PAC model. No assumptions are needed on the distribution of the observed objects, and the learning performance is quantified relative to its experience. Most important, the success of learning an object representation is naturally tied to the ability to represent it as a function of some intermediate representations extracted from the image. We evaluate this approach in a large-scale experimental study in which the SNoW learning architecture is used to learn representations for the 100 objects in the Columbia Object Image Library. Experimental results exhibit good generalization and robustness properties of the SNoW-based method relative to other approaches. SNoW's recognition rate degrades more gracefully when the training data contains fewer views, and it shows similar behavior in some preliminary experiments with partially occluded objects.     

Nested semantics over finite trees are equationally hard

This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based.     

Training multiple-layer perceptrons to recognize attractors

Determining the long-term behavior in dynamical systems is an area of intense research interest. In this paper, a multilayer perceptron is used to perform this task. The network is trained using an evolution strategy. A comparison against backpropagation-trained networks was performed, and the results indicate evolution strategies produce better performing networks     

On truthfulness and approximation for scheduling selfish tasks

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, 1999) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, 2004) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, 1969) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, 1995), we obtain a randomized 2r(1+ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ε)-algorithm for the off-line case with related machines.     

Aggregating value ranges: preference elicitation and truthfulness

We study the case where agents have preferences over ranges (intervals) of values, and we wish to elicit and aggregate these preferences. For example, consider a set of climatologist agents who are asked for their predictions for the increase in temperature between 2009 and 2100. Each climatologist submits a range, and from these ranges we must construct an aggregate range. What rule should we use for constructing the aggregate range? One issue in such settings is that an agent (climatologist) may misreport her range to make the aggregate range coincide more closely with her own (true) most-preferred range. We extend the theory of single-peaked preferences from points to ranges to obtain a rule (the median-of-ranges rule) that is strategy-proof under a condition on preferences. We then introduce and analyze a natural class of algorithms for approximately eliciting a median range from multiple agents. We also show sufficient conditions under which such an approximate elicitation algorithm still incentivizes agents to answer truthfully. Finally, we consider the possibility that ranges can be refined when the topic is more completely specified (for example, the increase in temperature on the North Pole given the failure of future climate pacts). We give a framework and algorithms for selectively specifying the topic further based on queries to agents.     

How to recognize database winners and losers

The author considers the benefits of reverse engineering a database. This recognizes what is good and bad in the design and understands how these characteristics affect the product and its use. He discusses implementation recovery, design recovery, identity conflicts and ambiguous assignments     

Alternatives to variable duration HMM in handwriting recognition

A successful handwritten word recognition (HWR) system using a variable duration hidden Markov model (VDHMM) and the path discriminant-HMM (PD-HMM) strategy is easy to implement. The central theme of the paper is to show that if the duration statistics are computed, it could be utilized to implement a model-discriminant-HMM (MD-HMM) approach for better experimental results. The paper also describes a PD-HMM based HWR system where the duration statistics are not explicitly computed, but results are still comparable to VDHMM based HWR scheme     

Learning to recognize patterns with a probabilistic teacher

A problem of learning with a probabilistic teacher is considered. Neither prior class probabilities nor class densities are assumed to be known and pattern recognition procedures are derived from nonparametric density and regression estimates. Weak and strong Bayes risk consistency of the procedures is shown. Examples of procedures using the kernel, the nearest neighbor and the orthogonal series estimates are given.     

Subwords-Only Alternatives to fastText for Morphologically Rich Languages

Programming and Computer Software - In this work, we present purely subword-based alternatives to fastText word embedding algorithm The alternatives are modifications of the original fastText...     

Fuzzy state machines to recognize totally unconstructed handwritten strokes

An automatic off-line character recognition system for totally unconstrained handwritten strokes is presented. A stroke representation is developed and described using five types of feature. Fuzzy state machines are defined to work as recognizers of strokes. An algorithm to obtain a deterministic fuzzy state machine from a stroke representation, that is capable of recognizing that stroke and its variants is presented. An algorithm is developed to merge two fuzzy state machines into one machine. The use of fuzzy machines to recognize strokes is clarified through a recognition algorithm. The learning algorithm is a complex of the previous algorithms. A set of 20 stroke classes was used in the learning and recognition stages. The system was trained on 5890 unnormalized strokes written by five writers. The learning stage produced a fuzzy state machine of 2705 states and 8640 arcs. A total of 6865 unnormalized strokes, written freely by five writers other than the writers of the learning stage, was used in testing. The recognition, rejection and error rates were 94.8%, 1.2% and 4.0%, respectively. The system can be more developed to deal with cursive handwriting.