OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized complexity results for 1-safe Petri nets
Venue: arXiv cs.LO 2011
Year: 2011

We associate a graph with a 1-safe Petri net and study the parameterized complexity of various problems with parameters derived from the graph. With treewidth as the parameter, we give W[1]-hardness results for many problems about 1-safe Petri nets. As a corollary, this proves a conjecture of Downey et. al. about the hardness of some graph pebbling problems. We consider the parameter benefit depth (that is known to be helpful in getting better algorithms for general Petri nets) and again give W[1]-hardness results for various problems on 1-safe Petri nets. We also consider the stronger parameter vertex cover number. Combining the well known automata-theoretic method and a powerful fixed parameter tractability (FPT) result about Integer Linear Programming, we give a FPT algorithm for model checking Monadic Second Order (MSO) formulas on 1-safe Petri nets, with parameters vertex cover number and the size of the formula.
A Tuned and Scalable Fast Multipole Method as a Preeminent Algorithm for Exascale Systems
Venue: arXiv cs.NA 2011
Year: 2011

Among the algorithms that are likely to play a major role in future exascale computing, the fast multipole method (FMM) appears as a rising star. Our previous recent work showed scaling of an FMM on GPU clusters, with problem sizes in the order of billions of unknowns. That work led to an extremely parallel FMM, scaling to thousands of GPUs or tens of thousands of CPUs. This paper reports on a a campaign of performance tuning and scalability studies using multi-core CPUs, on the Kraken supercomputer. All kernels in the FMM were parallelized using OpenMP, and a test using 10^7 particles randomly distributed in a cube showed 78% efficiency on 8 threads. Tuning of the particle-to-particle kernel using SIMD instructions resulted in 4x speed-up of the overall algorithm on single-core tests with 10^3 - 10^7 particles. Parallel scalability was studied in both strong and weak scaling. The strong scaling test used 10^8 particles and resulted in 93% parallel efficiency on 2048 processes for the non-SIMD code and 54% for the SIMD-optimized code (which was still 2x faster). The weak scaling test used 10^6 particles per process, and resulted in 72% efficiency on 32,768 processes, with the largest calculation taking about 40 seconds to evaluate more than 32 billion unknowns. This work builds up evidence for our view that FMM is poised to play a leading role in exascale computing, and we end the paper with a discussion of the features that make it a particularly favorable algorithm for the emerging heterogeneous and massively parallel architectural landscape.
Optimisation de la taille de la série: illustration par un cas industriel de sous-traitance mécanique
Venue: arXiv cs.OH 2011
Year: 2011

Reducing costs of manufactured products is one of the key issues of companies. Bar turning companies (mechanical subcontracting companies) are faced with the following dilemma: use a pull strategy or use a push strategy. Instinctively these companies produce more than demand required by customers. This strategy allows them to respond to requests forecasts and reduce their cost of changeover time. These companies make a bet on sales opportunities and think to realize an additional profit. We have tried to find in this study to provide elements to know the limits of this strategy. Our proposal focuses on developing a model to support the decision taking into account the mix of opportunities, economic constraints and mean constraints. This model features the particular importance of high rates of ownership and the risk of not selling. Réduire les coûts de revient des produits fabriqués est une des problématiques essentielles des entreprises d'aujourd'hui. Les entreprises de décolletage (entreprises de sous-traitance mécanique) sont confrontées au dilemme suivant : produire juste la demande client ou produire plus. Instinctivement ces entreprises, dont les temps de changement de série sont élevés, cherchent à produire plus que la demande exigée par le client. Cette stratégie leur permet de répondre à des demandes prévisionnelles et réduire ainsi le coût de revient des produits. Ces entreprises réalisent un pari sur les opportunités de vente et pensent réaliser un gain supplémentaire en réalisant des stocks. Nous avons cherché dans cette étude à fournir des éléments de décision pour connaître les limites de cette règle de gestion. Notre proposition porte sur le développement d'un modèle d'aide à la décision prenant en considération le mixte entre opportunités commerciales, contraintes économiques et contraintes de moyen. Ce modèle souligne l'importance particulière du taux de possession et du risque de non vente.
Unconstrained and Constrained Fault-Tolerant Resource Allocation
Venue: arXiv cs.DS 2011
Year: 2011

First, we study the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem (a.k.a. FTFA problem in \cite{shihongftfa}). In the problem, we are given a set of sites equipped with an unconstrained number of facilities as resources, and a set of clients with set $\mathcal{R}$ as corresponding connection requirements, where every facility belonging to the same site has an identical opening (operating) cost and every client-facility pair has a connection cost. The objective is to allocate facilities from sites to satisfy $\mathcal{R}$ at a minimum total cost. Next, we introduce the Constrained Fault-Tolerant Resource Allocation (CFTRA) problem. It differs from UFTRA in that the number of resources available at each site $i$ is limited by $R_{i}$. Both problems are practical extensions of the classical Fault-Tolerant Facility Location (FTFL) problem \cite{Jain00FTFL}. For instance, their solutions provide optimal resource allocation (w.r.t. enterprises) and leasing (w.r.t. clients) strategies for the contemporary cloud platforms. In this paper, we consider the metric version of the problems. For UFTRA with uniform $\mathcal{R}$, we present a star-greedy algorithm. The algorithm achieves the approximation ratio of 1.5186 after combining with the cost scaling and greedy augmentation techniques similar to \cite{Charikar051.7281.853,Mahdian021.52}, which significantly improves the result of \cite{shihongftfa} using a phase-greedy algorithm. We also study the capacitated extension of UFTRA and give a factor of 2.89. For CFTRA with uniform $\mathcal{R}$, we slightly modify the algorithm to achieve 1.5186-approximation. For a more general version of CFTRA, we show that it is reducible to FTFL using linear programming.
Evolutionary Biclustering of Clickstream Data
Venue: arXiv cs.NE 2011
Year: 2011

Biclustering is a two way clustering approach involving simultaneous clustering along two dimensions of the data matrix. Finding biclusters of web objects (i.e. web users and web pages) is an emerging topic in the context of web usage mining. It overcomes the problem associated with traditional clustering methods by allowing automatic discovery of browsing pattern based on a subset of attributes. A coherent bicluster of clickstream data is a local browsing pattern such that users in bicluster exhibit correlated browsing pattern through a subset of pages of a web site. This paper proposed a new application of biclustering to web data using a combination of heuristics and meta-heuristics such as K-means, Greedy Search Procedure and Genetic Algorithms to identify the coherent browsing pattern. Experiment is conducted on the benchmark clickstream msnbc dataset from UCI repository. Results demonstrate the efficiency and beneficial outcome of the proposed method by correlating the users and pages of a web site in high degree.This approach shows excellent performance at finding high degree of overlapped coherent biclusters from web data.
A framework for coupled deformation-diffusion analysis with application to degradation/healing
Venue: arXiv cs.NA 2011
Year: 2011

This paper deals with the formulation and numerical implementation of a fully coupled continuum model for deformation-diffusion in linearized elastic solids. The mathematical model takes into account the effect of the deformation on the diffusion process, and the affect of the transport of an inert chemical species on the deformation of the solid. We then present a robust computational framework for solving the proposed mathematical model, which consists of coupled non-linear partial differential equations. It should be noted that many popular numerical formulations may produce unphysical negative values for the concentration, particularly, when the diffusion process is anisotropic. The violation of the non-negative constraint by these numerical formulations is not mere numerical noise. In the proposed computational framework we employ a novel numerical formulation that will ensure that the concentration of the diffusant be always non-negative, which is one of the main contributions of this paper. Representative numerical examples are presented to show the robustness, convergence, and performance of the proposed computational framework. Another contribution of this paper is to systematically study the affect of transport of the diffusant on the deformation of the solid and vice-versa, and their implication in modeling degradation/healing of materials. We show that the coupled response is both qualitatively and quantitatively different from the uncoupled response.
Cognitive Binary Logic - The Natural Unified Formal Theory of Propositional Binary Logic
Venue: arXiv cs.LO 2011
Year: 2011

This paper presents a formal theory which describes propositional binary logic as a semantically closed formal language, and allows for syntactically and semantically well-formed formulae, formal proofs (demonstrability in Hilbertian acception), deduction (Gentzen's view of demonstrability), CNF-ization, and deconstruction to be expressed and tested in the same (computational) formal language, using the same data structure. It is also shown here that Cognitive Binary Logic is a self-described theory in which the Liar Paradox is deconstructed.
Some Results on the Information Loss in Dynamical Systems
Venue: arXiv cs.IT 2011
Year: 2011

In this work we investigate the information loss in (nonlinear) dynamical input-output systems and provide some general results. In particular, we present an upper bound on the information loss rate, defined as the (non-negative) difference between the entropy rates of the jointly stationary stochastic processes at the input and output of the system. We further introduce a family of systems with vanishing information loss rate. It is shown that not only linear filters belong to that family, but - under certain circumstances - also finite-precision implementations of the latter, which typically consist of nonlinear elements.
Resolving Author Name Homonymy to Improve Resolution of Structures in Co-author Networks
Venue: arXiv cs.DL 2011
Year: 2011

We investigate how author name homonymy distorts clustered large-scale co-author networks, and present a simple, effective, scalable and generalizable algorithm to ameliorate such distortions. We evaluate the performance of the algorithm to improve the resolution of mesoscopic network structures. To this end, we establish the ground truth for a sample of author names that is statistically representative of different types of nodes in the co-author network, distinguished by their role for the connectivity of the network. We finally observe that this distinction of node roles based on the mesoscopic structure of the network, in combination with a quantification of author name commonality, suggests a new approach to assess network distortion by homonymy and to analyze the reduction of distortion in the network after disambiguation, without requiring ground truth sampling.
On the Nash Equilibria in Decentralized Parallel Interference Channels
Venue: arXiv cs.GT 2011
Year: 2011

In this paper, the 2-dimensional decentralized parallel interference channel (IC) with 2 transmitter-receiver pairs is modelled as a non-cooperative static game. Each transmitter is assumed to be a fully rational entity with complete information on the game, aiming to maximize its own individual spectral efficiency by tuning its own power allocation (PA) vector. Two scenarios are analysed. First, we consider that transmitters can split their transmit power between both dimensions (PA game). Second, we consider that each transmitter is limited to use only one dimension (channel selection CS game). In the first scenario, the game might have either one or three NE in pure strategies (PS). However, two or infinitely many NE in PS might also be observed with zero probability. In the second scenario, there always exists either one or two NE in PS. We show that in both games there always exists a non-zero probability of observing more than one NE. More interestingly, using Monte-Carlo simulations, we show that the highest and lowest network spectral efficiency at any of the NE in the CS game are always higher than the ones in the PA.
Actual causation and the art of modeling
Venue: arXiv cs.AI 2011
Year: 2011

We look more carefully at the modeling of causality using structural equations. It is clear that the structural equations can have a major impact on the conclusions we draw about causality. In particular, the choice of variables and their values can also have a significant impact on causality. These choices are, to some extent, subjective. We consider what counts as an appropriate choice. More generally, we consider what makes a model an appropriate model, especially if we want to take defaults into account, as was argued is necessary in recent work.
I Don't Want to Think About it Now:Decision Theory With Costly Computation
Venue: arXiv cs.GT 2011
Year: 2011

Computation plays a major role in decision making. Even if an agent is willing to ascribe a probability to all states and a utility to all outcomes, and maximize expected utility, doing so might present serious computational problems. Moreover, computing the outcome of a given act might be difficult. In a companion paper we develop a framework for game theory with costly computation, where the objects of choice are Turing machines. Here we apply that framework to decision theory. We show how well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on), belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions), and the status quo bias (people are much more likely to stick with what they already have) can be easily captured in that framework. Finally, we use the framework to define some new notions: value of computational information (a computational variant of value of information) and and computational value of conversation.
Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence
Venue: arXiv cs.DM 2011
Year: 2011

Sand pile models are dynamical systems describing the evolution from $N$ stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. The main interest of sand piles relies in their {\em Self Organized Criticality} (SOC), the property that a small perturbation | adding some sand grains | on a fixed configuration has uncontrolled consequences on the system, involving an arbitrary number of grain fall. Physicists L. Kadanoff {\em et al} inspire KSPM, a model presenting a sharp SOC behavior, extending the well known {\em Sand Pile Model}. In KSPM($D$), we start from a pile of $N$ stacked grains and apply the rule: $D-1$ grains can fall from column $i$ onto the $D-1$ adjacent columns to the right if the difference of height between columns $i$ and $i+1$ is greater or equal to $D$. This paper develops a formal background for the study of KSPM fixed points. This background, resumed in a finite state word transducer, is used to provide a plain formula for fixed points of KSPM(3).
No justified complaints: On fair sharing of multiple resources
Venue: arXiv cs.DC 2011
Year: 2011

Fair allocation has been studied intensively in both economics and computer science, and fair sharing of resources has aroused renewed interest with the advent of virtualization and cloud computing. Prior work has typically focused on mechanisms for fair sharing of a single resource. We provide a new definition for the simultaneous fair allocation of multiple continuously-divisible resources. Roughly speaking, we define fairness as the situation where every user either gets all the resources he wishes for, or else gets at least his entitlement on some bottleneck resource, and therefore cannot complain about not getting more. This definition has the same desirable properties as the recently suggested dominant resource fairness, and also handles the case of multiple bottlenecks. We then prove that a fair allocation according to this definition is guaranteed to exist for any combination of user requests and entitlements (where a user's relative use of the different resources is fixed). The proof, which uses tools from the theory of ordinary differential equations, is constructive and provides a method to compute the allocations numerically.
On the Eavesdropper's Correct Decision in Gaussian and Fading Wiretap Channels Using Lattice Codes
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, the probability of Eve the Eavesdropper's correct decision is considered both in the Gaussian and Rayleigh fading wiretap channels when using lattice codes for the transmission. First, it is proved that the secrecy function determining Eve's performance attains its maximum at y=1 on all known extremal even unimodular lattices. This is a special case of a conjecture by Belfiore and Solé. Further, a very simple method to verify or disprove the conjecture on any given unimodular lattice is given. Second, preliminary analysis on the behavior of Eve's probability of correct decision in the fast fading wiretap channel is provided. More specifically, we compute the truncated inverse norm power sum factors in Eve's probability expression. The analysis reveals a performance-secrecy-complexity tradeoff: relaxing on the legitimate user's performance can significantly increase the security of transmission. The confusion experienced by the eavesdropper may be further increased by using skewed lattices, but at the cost of increased complexity.
Supporting Parallelism in Server-based Multiprocessor Systems
Venue: arXiv cs.DC 2011
Year: 2011

Developing an efficient server-based real-time scheduling solution that supports dynamic task-level parallelism is now relevant to even the desktop and embedded domains and no longer only to the high performance computing market niche. This paper proposes a novel approach that combines the constant bandwidth server abstraction with a work-stealing load balancing scheme which, while ensuring isolation among tasks, enables a task to be executed on more than one processor at a given time instant.
Injectivity of 2D Toric Bézier Patches
Venue: arXiv cs.GR 2011
Year: 2011

Rational Bézier functions are widely used as mapping functions in surface reparameterization, finite element analysis, image warping and morphing. The injectivity (one-to-one property) of a mapping function is typically necessary for these applications. Toric Bézier patches are generalizations of classical patches (triangular, tensor product) which are defined on the convex hull of a set of integer lattice points. We give a geometric condition on the control points that we show is equivalent to the injectivity of every 2D toric Bézier patch with those control points for all possible choices of weights. This condition refines that of Craciun, et al., which only implied injectivity on the interior of a patch.
Widely Linear vs. Conventional Subspace-Based Estimation of SIMO Flat-Fading Channels: Mean-Squared Error Analysis
Venue: arXiv cs.IT 2011
Year: 2011

We analyze the mean-squared error (MSE) performance of widely linear (WL) and conventional subspace-based channel estimation for single-input multiple-output (SIMO) flat-fading channels employing binary phase-shift-keying (BPSK) modulation when the covariance matrix is estimated using a finite number of samples. The conventional estimator suffers from a phase ambiguity that reduces to a sign ambiguity for the WL estimator. We derive closed-form expressions for the MSE of the two estimators under four different ambiguity resolution scenarios. The first scenario is optimal resolution, which minimizes the Euclidean distance between the channel estimate and the actual channel. The second scenario assumes that a randomly chosen coefficient of the actual channel is known and the third assumes that the one with the largest magnitude is known. The fourth scenario is the more realistic case where pilot symbols are used to resolve the ambiguities. Our work demonstrates that there is a strong relationship between the accuracy of ambiguity resolution and the relative performance of WL and conventional subspace-based estimators, and shows that the less information available about the actual channel for ambiguity resolution, or the lower the accuracy of this information, the higher the performance gap in favor of the WL estimator.
Chameleons in imagined conversations: A new approach to understanding coordination of linguistic style in dialogs
Venue: arXiv cs.CL 2011
Year: 2011

Conversational participants tend to immediately and unconsciously adapt to each other's language styles: a speaker will even adjust the number of articles and other function words in their next utterance in response to the number in their partner's immediately preceding utterance. This striking level of coordination is thought to have arisen as a way to achieve social goals, such as gaining approval or emphasizing difference in status. But has the adaptation mechanism become so deeply embedded in the language-generation process as to become a reflex? We argue that fictional dialogs offer a way to study this question, since authors create the conversations but don't receive the social benefits (rather, the imagined characters do). Indeed, we find significant coordination across many families of function words in our large movie-script corpus. We also report suggestive preliminary findings on the effects of gender and other features; e.g., surprisingly, for articles, on average, characters adapt more to females than to males.