OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized Complexity of Synchronization and Road Coloring
Venue: arXiv cs.FL 2014
Year: 2014

First, we close the multivariate analysis of a canonical problem concerning short reset words (SYN), as it was started by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multivariate analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum word length.
An Inter-Component Pixels Permutation Based Color Image Encryption Using Hyper-chaos
Venue: arXiv cs.CR 2014
Year: 2014

In this paper, a simple and robust color image encryption algorithm based on high-dimensional chaotic maps is proposed. The algorithm employs a 3D Arnold transform to perform inter-component shuffling of plain-image, while a 2D hyper-chaotic map is used to confuse the relationship between the encrypted image and plain-image. The control parameters of Arnold transform are extracted from pending plain-image, thereby establishing a dependency to the plain-image. The confusion process is carried out in cipher-block chaining mode to make it dependent to the encrypted image. This makes the algorithm able to resist the cryptographic attacks. The performance of the proposed algorithm is analyzed through computer simulations. The experimental analyses show that the proposed algorithm has desirable properties of high security, robustness to cryptographic attacks and practicability to protect multimedia color images.
Two Puzzles About Computation
Venue: arXiv cs.LO 2014
Year: 2014

The purpose of this note is to raise two different questions, which are rarely if ever considered, and to which, it seems, we lack convincing, systematic answers. These questions can be posed as: - Why do we compute? - What do we compute? The point is not so much that we have no answers to these puzzles, as that we have no established body of theory which gives satisfying, systematic answers, as part of a broader understanding. By raising these questions, we hope to stimulate some thinking in this direction.
State-space solution to a minimum-entropy $\mathcal{H}_\infty$-optimal control problem with a nested information constraint
Venue: arXiv cs.SY 2014
Year: 2014

State-space formulas are derived for the minimum-entropy $\mathcal{H}_\infty$ controller when the plant and controller are constrained to be block-lower-triangular. Such a controller exists if and only if: the corresponding unstructured problem has a solution, a certain pair of coupled algebraic Riccati equations admits a mutually stabilizing fixed point, and a pair of spectral radius conditions is met. The controller's observer-based structure is also discussed, and a simple numerical approach for solving the coupled Riccati equations is presented.
Unconfused Ultraconservative Multiclass Algorithms
Venue: arXiv cs.LG 2014
Year: 2014

We tackle the problem of learning linear classifiers from noisy datasets in a multiclass setting. The two-class version of this problem was studied a few years ago by, e.g. Bylander (1994) and Blum et al. (1996): in these contributions, the proposed approaches to fight the noise revolve around a Perceptron learning scheme fed with peculiar examples computed through a weighted average of points from the noisy training set. We propose to build upon these approaches and we introduce a new algorithm called UMA (for Unconfused Multiclass additive Algorithm) which may be seen as a generalization to the multiclass setting of the previous approaches. In order to characterize the noise we use the confusion matrix as a multiclass extension of the classification noise studied in the aforementioned literature. Theoretically well-founded, UMA furthermore displays very good empirical noise robustness, as evidenced by numerical simulations conducted on both synthetic and real data. Keywords: Multiclass classification, Perceptron, Noisy labels, Confusion Matrix
General Centrality in a hypergraph
Venue: arXiv cs.SI 2014
Year: 2014

The goal of this paper is to present a centrality measurement for the nodes of a hypergraph, by using existing literature which extends eigenvector centrality from a graph to a hypergraph, and literature which give a general centrality measurement for a graph. We will use this measurement to say more about the number of communications in a hypergraph, to implement a learning mechanism, and to construct certain networks.
Defuzzify firstly or finally: Dose it matter in fuzzy DEMATEL under uncertain environment?
Venue: arXiv cs.AI 2014
Year: 2014

Decision-Making Trial and Evaluation Laboratory (DEMATEL) method is widely used in many real applications. With the desirable property of efficient handling with the uncertain information in decision making, the fuzzy DEMATEL is heavily studied. Recently, Dytczak and Ginda suggested to defuzzify the fuzzy numbers firstly and then use the classical DEMATEL to obtain the final result. In this short paper, we show that it is not reasonable in some situations. The results of defuzzification at the first step are not coincide with the results of defuzzification at the final step.It seems that the alternative is to defuzzification in the final step in fuzzy DEMATEL.
A Survey on Cloud Security Issues and Techniques
Venue: arXiv cs.DC 2014
Year: 2014

Today, cloud computing is an emerging way of computing in computer science. Cloud computing is a set of resources and services that are offered by the network or internet. Cloud computing extends various computing techniques like grid computing, distributed computing. Today cloud computing is used in both industrial field and academic field. Cloud facilitates its users by providing virtual resources via internet. As the field of cloud computing is spreading the new techniques are developing. This increase in cloud computing environment also increases security challenges for cloud developers. Users of cloud save their data in the cloud hence the lack of security in cloud can lose the users trust. In this paper we will discuss some of the cloud security issues in various aspects like multi-tenancy, elasticity, availability etc. The paper also discuss existing security techniques and approaches for a secure cloud. This paper will enable researchers and professionals to know about different security threats and models and tools proposed.
Control over adversarial packet-dropping communication networks revisited
Venue: arXiv cs.SY 2014
Year: 2014

We revisit a one-step control problem over an adversarial packet-dropping link. The link is modeled as a set of binary channels controlled by a strategic jammer whose intention is to wage a `denial of service' attack on the plant by choosing a most damaging channel-switching strategy. The paper introduces a class of zero-sum games between the jammer and controller as a scenario for such attack, and derives necessary and sufficient conditions for these games to have a nontrivial saddle-point equilibrium. At this equilibrium, the jammer's optimal policy is to randomize in a region of the plant's state space, thus requiring the controller to undertake a nontrivial response which is different from what one would expect in a standard stochastic control problem over a packet dropping channel.
Partial Order Infinitary Term Rewriting
Venue: arXiv cs.LO 2014
Year: 2014

We study an alternative model of infinitary term rewriting. Instead of a metric on terms, a partial order on partial terms is employed to formalise convergence of reductions. We consider both a weak and a strong notion of convergence and show that the metric model of convergence coincides with the partial order model restricted to total terms. Hence, partial order convergence constitutes a conservative extension of metric convergence, which additionally offers a fine-grained distinction between different levels of divergence. In the second part, we focus our investigation on strong convergence of orthogonal systems. The main result is that the gap between the metric model and the partial order model can be bridged by extending the term rewriting system by additional rules. These extensions are the well-known Böhm extensions. Based on this result, we are able to establish that -- contrary to the metric setting -- orthogonal systems are both infinitarily confluent and infinitarily normalising in the partial order setting. The unique infinitary normal forms that the partial order model admits are Böhm trees.
A Polynomial-time Algorithm for Outerplanar Diameter Improvement
Venue: arXiv cs.DS 2014
Year: 2014

The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.
D-CFPR: D numbers extended consistent fuzzy preference relations
Venue: arXiv cs.AI 2014
Year: 2014

How to express an expert's or a decision maker's preference for alternatives is an open issue. Consistent fuzzy preference relation (CFPR) is with big advantages to handle this problem due to it can be construed via a smaller number of pairwise comparisons and satisfies additive transitivity property. However, the CFPR is incapable of dealing with the cases involving uncertain and incomplete information. In this paper, a D numbers extended consistent fuzzy preference relation (D-CFPR) is proposed to overcome the weakness. The D-CFPR extends the classical CFPR by using a new model of expressing uncertain information called D numbers. The D-CFPR inherits the merits of classical CFPR and can be totally reduced to the classical CFPR. This study can be integrated into our previous study about D-AHP (D numbers extended AHP) model to provide a systematic solution for multi-criteria decision making (MCDM).
Sample-Optimal Fourier Sampling in Any Constant Dimension -- Part I
Venue: arXiv cs.DS 2014
Year: 2014

We give an algorithm for $\ell_2/\ell_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of \cite{DIPW} for non-adaptive algorithms up to constant factors for any $k\leq N^{1-δ}$. The algorithm runs in $\tilde O(N)$ time. Our algorithm extends to higher dimensions, leading to sample complexity of $O_d(k\log N)$, which is optimal up to constant factors for any $d=O(1)$. These are the first sample optimal algorithms for these problems. A preliminary experimental evaluation indicates that our algorithm has empirical sampling complexity comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality.
A Survey on Network Tomography with Network Coding
Venue: arXiv cs.NI 2014
Year: 2014

The overhead of internal network monitoring motivates techniques of network tomography. Network coding (NC) presents a new opportunity for network tomography as NC introduces topology-dependent correlation that can be further exploited in topology estimation. Compared with traditional methods, network tomography with NC has many advantages such as the improvement of tomography accuracy and the reduction of complexity in choosing monitoring paths. In this paper we first introduce the problem of tomography with NC and then propose the taxonomy criteria to classify various methods. We also present existing solutions and future trend. We expect that our comprehensive review on network tomography with NC can serve as a good reference for researchers and practitioners working in the area.
Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard
Venue: arXiv cs.CC 2014
Year: 2014

The twentieth century has seen the rise of a new type of video games targeted at a mass audience of "casual" gamers. Many of these games require the player to swap items in order to form matches of three and are collectively known as \emph{tile-matching match-three games}. Among these, the most influential one is arguably \emph{Bejeweled} in which the matched items (gems) pop and the above gems fall in their place. Bejeweled has been ported to many different platforms and influenced an incredible number of similar games. Very recently one of them, named \emph{Candy Crush Saga} enjoyed a huge popularity and quickly went viral on social networks. We generalize this kind of games by only parameterizing the size of the board, while all the other elements (such as the rules or the number of gems) remain unchanged. Then, we prove that answering many natural questions regarding such games is actually \NP-Hard. These questions include determining if the player can reach a certain score, play for a certain number of turns, and others. We also \href{http://candycrush.isnphard.com}{provide} a playable web-based implementation of our reduction.
Utility Max-Min Fair Link Adaptation in IEEE 802.11ac Downlink Multi-User
Venue: arXiv cs.NI 2014
Year: 2014

In this letter, we propose a novel model and corresponding algorithms to address the optimal utility max-min fair link adaptation in Downlink Multi-User (DL-MU) feature of the emerging IEEE 802.11ac WLAN standard. Herein, we first propose a simple yet accurate model to formulate the max-min fair link adaptation problem. Furthermore, this model guarantees the minimum utility gain of each receiver according to its requirements. In the second step, we show that the optimal solution of the proposed model can be obtained in polynomial time, and then the solution algorithms are proposed and analyzed. The simulation results demonstrate the significant achievement of the proposed utility-aware link adaptation approach in terms of max-min fairness and utility gain compared to utility-oblivious schemes.
Mapping parcel-level urban areas for a large geographical area
Venue: arXiv cs.OH 2014
Year: 2014

As a vital indicator for measuring urban development, urban areas are expected to be identified explicitly and conveniently with widely available dataset thereby benefiting the planning decisions and relevant urban studies. Existing approaches to identify urban areas normally based on mid-resolution sensing dataset, socioeconomic information (e.g. population density) generally associate with low-resolution in space, e.g. cells with several square kilometers or even larger towns/wards. Yet, few of them pay attention to defining urban areas with micro data in a fine-scaled manner with large extend scale by incorporating the morphological and functional characteristics. This paper investigates an automated framework to delineate urban areas in the parcel level, using increasingly available ordnance surveys for generating all parcels (or geo-units) and ubiquitous points of interest (POIs) for inferring density of each parcel. A vector cellular automata model was adopted for identifying urban parcels from all generated parcels, taking into account density, neighborhood condition, and other spatial variables of each parcel. We applied this approach for mapping urban areas of all 654 Chinese cities and compared them with those interpreted from mid-resolution remote sensing images and inferred by population density and road intersections. Our proposed framework is proved to be more straight-forward, time-saving and fine-scaled, compared with other existing ones, and reclaim the need for consistency, efficiency and availability in defining urban areas with well-consideration of omnipresent spatial and functional factors across cities.
Revisiting Size-Based Scheduling with Estimated Job Sizes
Venue: arXiv cs.DS 2014
Year: 2014

We study size-based schedulers, and focus on the impact of inaccurate job size information on response time and fairness. Our intent is to revisit previous results, which allude to performance degradation for even small errors on job size estimates, thus limiting the applicability of size-based schedulers. We show that scheduling performance is tightly connected to workload characteristics: in the absence of large skew in the job size distribution, even extremely imprecise estimates suffice to outperform size-oblivious disciplines. Instead, when job sizes are heavily skewed, known size-based disciplines suffer. In this context, we show -- for the first time -- the dichotomy of over-estimation versus under-estimation. The former is, in general, less problematic than the latter, as its effects are localized to individual jobs. Instead, under-estimation leads to severe problems that may affect a large number of jobs. We present an approach to mitigate these problems: our technique requires no complex modifications to original scheduling policies and performs very well. To support our claim, we proceed with a simulation-based evaluation that covers an unprecedented large parameter space, which takes into account a variety of synthetic and real workloads. As a consequence, we show that size-based scheduling is practical and outperforms alternatives in a wide array of use-cases, even in presence of inaccurate size information.
Intensional RDB for Big Data Interoperability
Venue: arXiv cs.DB 2014
Year: 2014

A new family of Intensional RDBs (IRDBs), introduced in [1], extends the traditional RDBs with the Big Data and flexible and 'Open schema' features, able to preserve the user-defined relational database schemas and all preexisting user's applications containing the SQL statements for a deployment of such a relational data. The standard RDB data is parsed into an internal vector key/value relation, so that we obtain a column representation of data used in Big Data applications, covering the key/value and column-based Big Data applications as well, into a unifying RDB framework. Such an IRDB architecture is adequate for the massive migrations from the existing slow RDBMSs into this new family of fast IRDBMSs by offering a Big Data and new flexible schema features as well. Here we present the interoperability features of the IRDBs by permitting the queries also over the internal vector relations created by parsing of each federated database in a given Multidatabase system. We show that the SchemaLog with the second-order syntax and ad hoc Logic Programming and its querying fragment can be embedded into the standard SQL IRDBMSs, so that we obtain a full interoperabilty features of IRDBs by using only the standard relational SQL for querying both data and meta-data.
Development and evaluation of a 3D model observer with nonlinear spatiotemporal contrast sensitivity
Venue: arXiv cs.CV 2014
Year: 2014

We investigate improvements to our 3D model observer with the goal of better matching human observer performance as a function of viewing distance, effective contrast, maximum luminance, and browsing speed. Two nonlinear methods of applying the human contrast sensitivity function (CSF) to a 3D model observer are proposed, namely the Probability Map (PM) and Monte Carlo (MC) methods. In the PM method, the visibility probability for each frequency component of the image stack, p, is calculated taking into account Barten's spatiotemporal CSF, the component modulation, and the human psychometric function. The probability p is considered to be equal to the perceived amplitude of the frequency component and thus can be used by a traditional model observer (e.g., LG-msCHO) in the space-time domain. In the MC method, each component is randomly kept with probability p or discarded with 1-p. The amplitude of the retained components is normalized to unity. The methods were tested using DBT stacks of an anthropomorphic breast phantom processed in a comprehensive simulation pipeline. Our experiments indicate that both the PM and MC methods yield results that match human observer performance better than the linear filtering method as a function of viewing distance, effective contrast, maximum luminance, and browsing speed.
Quantum Synchronizable Codes From Quadratic Residue Codes and Their Supercodes
Venue: arXiv cs.IT 2014
Year: 2014

Quantum synchronizable codes are quantum error-correcting codes designed to correct the effects of both quantum noise and block synchronization errors. While it is known that quantum synchronizable codes can be constructed from cyclic codes that satisfy special properties, only a few classes of cyclic codes have been proved to give promising quantum synchronizable codes. In this paper, using quadratic residue codes and their supercodes, we give a simple construction for quantum synchronizable codes whose synchronization capabilities attain the upper bound. The method is applicable to cyclic codes of prime length.
CNN Features off-the-shelf: an Astounding Baseline for Recognition
Venue: arXiv cs.CV 2014
Year: 2014

Recent results indicate that the generic descriptors extracted from the convolutional neural networks are very powerful. This paper adds to the mounting evidence that this is indeed the case. We report on a series of experiments conducted for different recognition tasks using the publicly available code and model of the \overfeat network which was trained to perform object classification on ILSVRC13. We use features extracted from the \overfeat network as a generic image representation to tackle the diverse range of recognition tasks of object image classification, scene recognition, fine grained recognition, attribute detection and image retrieval applied to a diverse set of datasets. We selected these tasks and datasets as they gradually move further away from the original task and data the \overfeat network was trained to solve. Astonishingly, we report consistent superior results compared to the highly tuned state-of-the-art systems in all the visual classification tasks on various datasets. For instance retrieval it consistently outperforms low memory footprint methods except for sculptures dataset. The results are achieved using a linear SVM classifier (or $L2$ distance in case of retrieval) applied to a feature representation of size 4096 extracted from a layer in the net. The representations are further modified using simple augmentation techniques e.g. jittering. The results strongly suggest that features obtained from deep learning with convolutional nets should be the primary candidate in most visual recognition tasks.
Knightian Robustness of Single-Parameter Domains
Venue: arXiv cs.GT 2014
Year: 2014

We consider players that have very limited knowledge about their own valuations. Specifically, the only information that a Knightian player $i$ has about the profile of true valuations, $θ^*$, consists of a set of distributions, from one of which $θ_i^*$ has been drawn. We prove a ``robustness'' theorem for Knightian players in single-parameter domains: every mechanism that is weakly dominant-strategy truthful for classical players continues to be well-behaved for Knightian players that choose undominated strategies.