OpenRaiser/Intern-Atlas huggingface dataset:
Rank and fooling set size
Venue: arXiv cs.CC 2013
Year: 2013

Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
Deconstructing Queue-Based Mutual Exclusion
Venue: arXiv cs.DC 2013
Year: 2013

We formulate a modular approach to the design and analysis of a particular class of mutual exclusion algorithms for shared memory multiprocessor systems. Specifically, we consider algorithms that organize waiting processes into a queue. Such algorithms can achieve O(1) remote memory reference (RMR) complexity, which minimizes (asymptotically) the amount of traffic through the processor-memory interconnect. We first describe a generic mutual exclusion algorithm that relies on a linearizable implementation of a particular queue-like data structure that we call MutexQueue. Next, we show two implementations of MutexQueue using O(1) RMRs per operation based on synchronization primitives commonly available in multiprocessors. These implementations follow closely the queuing code embedded in previously published mutual exclusion algorithms. We provide rigorous correctness proofs and RMR complexity analyses of the algorithms we present.
On Convergent Finite Difference Schemes for Variational - PDE Based Image Processing
Venue: arXiv cs.CV 2013
Year: 2013

We study an adaptive anisotropic Huber functional based image restoration scheme. By using a combination of L2-L1 regularization functions, an adaptive Huber functional based energy minimization model provides denoising with edge preservation in noisy digital images. We study a convergent finite difference scheme based on continuous piecewise linear functions and use a variable splitting scheme, namely the Split Bregman, to obtain the discrete minimizer. Experimental results are given in image denoising and comparison with additive operator splitting, dual fixed point, and projected gradient schemes illustrate that the best convergence rates are obtained for our algorithm.
OutFlank Routing: Increasing Throughput in Toroidal Interconnection Networks
Venue: arXiv cs.DC 2013
Year: 2013

We present a new, deadlock-free, routing scheme for toroidal interconnection networks, called OutFlank Routing (OFR). OFR is an adaptive strategy which exploits non-minimal links, both in the source and in the destination nodes. When minimal links are congested, OFR deroutes packets to carefully chosen intermediate destinations, in order to obtain travel paths which are only an additive constant longer than the shortest ones. Since routing performance is very sensitive to changes in the traffic model or in the router parameters, an accurate discrete-event simulator of the toroidal network has been developed to empirically validate OFR, by comparing it against other relevant routing strategies, over a range of typical real-world traffic patterns. On the 16x16x16 (4096 nodes) simulated network OFR exhibits improvements of the maximum sustained throughput between 14% and 114%, with respect to Adaptive Bubble Routing.
Optimal cooperative motion planning for vehicles at intersections
Venue: arXiv cs.SY 2013
Year: 2013

We consider the problem of cooperative intersection management. It arises in automated transportation systems for people or goods but also in multi-robots environment. Therefore many solutions have been proposed to avoid collisions. The main problem is to determine collision-free but also deadlock-free and optimal algorithms. Even with a simple definition of optimality, finding a global optimum is a problem of high complexity, especially for open systems involving a large and varying number of vehicles. This paper advocates the use of a mathematical framework based on a decomposition of the problem into a continuous optimization part and a scheduling problem. The paper emphasizes connections between the usual notion of vehicle priority and an abstract formulation of the scheduling problem in the coordination space. A constructive locally optimal algorithm is proposed. More generally, this work opens up for new computationally efficient cooperative motion planning algorithms.
Moving in temporal graphs with very sparse random availability of edges
Venue: arXiv cs.DS 2013
Year: 2013

In this work we consider temporal graphs, i.e. graphs, each edge of which is assigned a set of discrete time-labels drawn from a set of integers. The labels of an edge indicate the discrete moments in time at which the edge is available. We also consider temporal paths in a temporal graph, i.e. paths whose edges are assigned a strictly increasing sequence of labels. Furthermore, we assume the uniform case (UNI-CASE), in which every edge of a graph is assigned exactly one time label from a set of integers and the time labels assigned to the edges of the graph are chosen randomly and independently, with the selection following the uniform distribution. We call uniform random temporal graphs the graphs that satisfy the UNI-CASE. We begin by deriving the expected number of temporal paths of a given length in the uniform random temporal clique. We define the term temporal distance of two vertices, which is the arrival time, i.e. the time-label of the last edge, of the temporal path that connects those vertices, which has the smallest arrival time amongst all temporal paths that connect those vertices. We then propose and study two statistical properties of temporal graphs. One is the maximum expected temporal distance which is, as the term indicates, the maximum of all expected temporal distances in the graph. The other one is the temporal diameter which, loosely speaking, is the expectation of the maximum temporal distance in the graph. We derive the maximum expected temporal distance of a uniform random temporal star graph as well as an upper bound on both the maximum expected temporal distance and the temporal diameter of the normalized version of the uniform random temporal clique, in which the largest time-label available equals the number of vertices. Finally, we provide an algorithm that solves an optimization problem on a specific type of temporal (multi)graphs of two vertices.
Necessary and Sufficient Conditions for Novel Word Detection in Separable Topic Models
Venue: arXiv cs.LG 2013
Year: 2013

The simplicial condition and other stronger conditions that imply it have recently played a central role in developing polynomial time algorithms with provable asymptotic consistency and sample complexity guarantees for topic estimation in separable topic models. Of these algorithms, those that rely solely on the simplicial condition are impractical while the practical ones need stronger conditions. In this paper, we demonstrate, for the first time, that the simplicial condition is a fundamental, algorithm-independent, information-theoretic necessary condition for consistent separable topic estimation. Furthermore, under solely the simplicial condition, we present a practical quadratic-complexity algorithm based on random projections which consistently detects all novel words of all topics using only up to second-order empirical word moments. This algorithm is amenable to distributed implementation making it attractive for 'big-data' scenarios involving a network of large distributed databases.
Undecidable First-Order Theories of Affine Geometries
Venue: arXiv cs.LO 2013
Year: 2013

Tarski initiated a logic-based approach to formal geometry that studies first-order structures with a ternary betweenness relation β, and a quaternary equidistance relation \equiv. Tarski established, inter alia, that the first-order (FO) theory of (R^2,β,\equiv) is decidable. Aiello and van Benthem (2002) conjectured that the FO-theory of expansions of (R^2,β) with unary predicates is decidable. We refute this conjecture by showing that for all n>1, the FO-theory of the class of expansions of (R^2,β) with just one unary predicate is not even arithmetical. We also define a natural and comprehensive class C of geometric structures (T,β), and show that for each structure (T,β) in C, the FO-theory of the class of expansions of (T,β) with a single unary predicate is undecidable. We then consider classes of expansions of structures (T,β) with a restricted unary predicate, for example a finite predicate, and establish a variety of related undecidability results. In addition to decidability questions, we briefly study the expressivities of universal MSO and weak universal MSO over expansions of (R^n,β). While the logics are incomparable in general, over expansions of (R^n,β), formulae of weak universal MSO translate into equivalent formulae of universal MSO.
(Re)partitioning for stream-enabled computation
Venue: arXiv cs.DC 2013
Year: 2013

Partitioning an input graph over a set of workers is a complex operation. Objectives are twofold: split the work evenly, so that every worker gets an equal share, and minimize edge cut to achieve a good work locality (i.e. workers can work independently). Partitioning a graph accessible from memory is a notorious NP-complete problem. Motivated by the regain of interest for the stream processing paradigm (where nodes and edges arrive as a flow to the datacenter), we propose in this paper a stream-enabled graph partitioning system that constantly seeks an optimum between those two objectives. We first expose the hardness of partitioning using classic and static methods; we then exhibit the cut versus load balancing tradeoff, from an application point of view. With this tradeoff in mind, our approach translates the online partitioning problem into a standard optimization problem. A greedy algorithm handles the stream of incoming graph updates while optimizations are triggered on demand to improve upon the greedy decisions. Using simulations, we show that this approach is very efficient, turning a basic optimization strategy such as hill climbing into an online partitioning solution that compares favorably to literature's recent stream partitioning solutions.
Tree Nash Equilibria in the Network Creation Game
Venue: arXiv cs.GT 2013
Year: 2013

In the network creation game with n vertices, every vertex (a player) buys a set of adjacent edges, each at a fixed amount α > 0. It has been conjectured that for α >= n, every Nash equilibrium is a tree, and has been confirmed for every α >= 273n. We improve upon this bound and show that this is true for every α >= 65n. To show this, we provide new and improved results on the local structure of Nash equilibria. Technically, we show that if there is a cycle in a Nash equilibrium, then α < 65n. Proving this, we only consider relatively simple strategy changes of the players involved in the cycle. We further show that this simple approach cannot be used to show the desired upper bound α < n (for which a cycle may exist), but conjecture that a slightly worse bound α < 1.3n can be achieved with this approach. Towards this conjecture, we show that if a Nash equilibrium has a cycle of length at most 10, then indeed α < 1.3n. We further provide experimental evidence suggesting that when the girth of a Nash equilibrium is increasing, the upper bound on α obtained by the simple strategy changes is not increasing. To the end, we investigate the approach for a coalitional variant of Nash equilibrium, where coalitions of two players cannot collectively improve, and show that if α >= 41n, then every such Nash equilibrium is a tree.
Enabling Information Centric Networks through Opportunistic Search, Routing and Caching
Venue: arXiv cs.NI 2013
Year: 2013

Content dissemination networks are pervasive in todays Internet. Examples of content dissemination networks include peer-to-peer networks (P2P), content distribution networks (CDN) and information centric networks (ICN). In this paper, we propose a new system design for information centric networks which leverages opportunistic searching, routing and caching. Our system design is based on an hierarchical tiered structure. Random walks are used to find content inside each tier, and gateways across tiers are used to direct requests towards servers placed in the top tier, which are accessed in case content replicas are not found in lower tiers. Then, we propose a model to analyze the system in consideration. The model yields metrics such as mean time to find a content and the load experienced by custodians as a function of the network topology. Using the model, we identify trade-offs between these two metrics, and numerically show how to find the optimal time to live of the random walks.
Power of Nondetreministic JAGs on Cayley graphs
Venue: arXiv cs.CC 2013
Year: 2013

The Immerman-Szelepcsenyi Theorem uses an algorithm for co-st- connectivity based on inductive counting to prove that NLOGSPACE is closed un- der complementation. We want to investigate whether counting is necessary for this theorem to hold. Concretely, we show that Nondeterministic Jumping Graph Autmata (ND-JAGs) (pebble automata on graphs), on several families of Cayley graphs, are equal in power to nondeterministic logspace Turing machines that are given such graphs as a linear encoding. In particular, it follows that ND-JAGs can solve co-st-connectivity on those graphs. This came as a surprise since Cook and Rackoff showed that deterministic JAGs cannot solve st-connectivity on many Cayley graphs due to their high self-similarity (every neighbourhood looks the same). Thus, our results show that on these graphs, nondeterminism provably adds computational power. The families of Cayley graphs we consider include Cayley graphs of abelian groups and of all finite simple groups irrespective of how they are presented and graphs corresponding to groups generated by various product constructions, in- cluding iterated ones. We remark that assessing the precise power of nondeterministic JAGs and in par- ticular whether they can solve co-st-connectivity on arbitrary graphs is left as an open problem by Edmonds, Poon and Achlioptas. Our results suggest a positive answer to this question and in particular considerably limit the search space for a potential counterexample.
Safe and Efficient Screening For Sparse Support Vector Machine
Venue: arXiv cs.LG 2013
Year: 2013

Screening is an effective technique for speeding up the training process of a sparse learning model by removing the features that are guaranteed to be inactive the process. In this paper, we present a efficient screening technique for sparse support vector machine based on variational inequality. The technique is both efficient and safe.
Cloud computing security using encryption technique
Venue: arXiv cs.DC 2013
Year: 2013

Cloud Computing has been envisioned as the next generation architecture of IT Enterprise. The Cloud computing concept offers dynamically scalable resources provisioned as a service over the Internet. Economic benefits are the main driver for the Cloud, since it promises the reduction of capital expenditure and operational expenditure. In order for this to become reality, however, there are still some challenges to be solved. Most important among these are security and trust issues,since the users data has to be released to the Cloud and thus leaves the protection sphere of the data owner.In contrast to traditional solutions, where the IT services are under proper physical,logical and personnel controls, Cloud Computing moves the application software and databases to the large data centers, where the management of the data and services may not be fully trustworthy. This unique attribute, however, poses many new security challenges which have not been well understood. Security is to save data from danger and vulnerability. There are so many dangers and vulnerabilities to be handled. Various security issues and some of their solution are explained and are concentrating mainly on public cloud security issues and their solutions. Data should always be encrypted when stored(using separate symmetric encryption keys)and transmitted. If this is implemented appropriately, even if another tenant can access the data, all that will appear is gibberish. So a method is proposed such that we are encrypting the whole data along with the cryptographic key.
On the Combination of Silent Error Detection and Checkpointing
Venue: arXiv cs.DC 2013
Year: 2013

In this paper, we revisit traditional checkpointing and rollback recovery strategies, with a focus on silent data corruption errors. Contrarily to fail-stop failures, such latent errors cannot be detected immediately, and a mechanism to detect them must be provided. We consider two models: (i) errors are detected after some delays following a probability distribution (typically, an Exponential distribution); (ii) errors are detected through some verification mechanism. In both cases, we compute the optimal period in order to minimize the waste, i.e., the fraction of time where nodes do not perform useful computations. In practice, only a fixed number of checkpoints can be kept in memory, and the first model may lead to an irrecoverable failure. In this case, we compute the minimum period required for an acceptable risk. For the second model, there is no risk of irrecoverable failure, owing to the verification mechanism, but the corresponding overhead is included in the waste. Finally, both models are instantiated using realistic scenarios and application/architecture parameters.
Instant messaging an effective way of communication in workplace
Venue: arXiv cs.CY 2013
Year: 2013

The modern workplace is inherently collaborative, and this collaboration relies on effective communication among coworkers. Instant messaging is the multitasking tools of choice most people chatting over IM do other things at the same time.The use of IM in workplace is less intrusive than the use of phone, more immediate than email and has added advantage due to the ability to detect presence.In order for institution to maximize increased business productivity using instant messaging its imperative that organizations define and publish ICT policies, guidelines and regulations.Overall IM boosts business performance by making operations faster, more agile, and more efficient with very little additional cost thus Organizations that deploy IM would reap significant Return on Investment.Institutions should adopt IM meetings which are be more efficient and less prone to straying off topic, because of the relative effort of typing versus talking.
Dynamic web cache publishing for IaaS clouds using Shoal
Venue: arXiv cs.DC 2013
Year: 2013

We have developed a highly scalable application, called Shoal, for tracking and utilizing a distributed set of HTTP web caches. Squid servers advertise their existence to the Shoal server via AMQP messaging by running Shoal Agent. The Shoal server provides a simple REST interface that allows clients to determine their closest Squid cache. Our goal is to dynamically instantiate Squid caches on IaaS clouds in response to client demand. Shoal provides the VMs on IaaS clouds with the location of the nearest dynamically instantiated Squid Cache. In this paper, we describe the design and performance of Shoal.
Reconstruction of Complex-Valued Fractional Brownian Motion Fields Based on Compressive Sampling and Its Application to PSF Interpolation in Weak Lensing Survey
Venue: arXiv cs.CV 2013
Year: 2013

A new reconstruction method of complex-valued fractional Brownian motion (CV-fBm) field based on Compressive Sampling (CS) is proposed. The decay property of Fourier coefficients magnitude of the fBm signals/ fields indicates that fBms are compressible. Therefore, a few numbers of samples will be sufficient for a CS based method to reconstruct the full field. The effectiveness of the proposed method is showed by simulating, random sampling, and reconstructing CV-fBm fields. Performance evaluation shows advantages of the proposed method over boxcar filtering and thin plate methods. It is also found that the reconstruction performance depends on both of the fBm's Hurst parameter and the number of samples, which in fact is consistent with the CS reconstruction theory. In contrast to other fBm or fractal interpolation methods, the proposed CS based method does not require the knowledge of fractal parameters in the reconstruction process; the inherent sparsity is just sufficient for the CS to do the reconstruction. Potential applicability of the proposed method in weak gravitational lensing survey, particularly for interpolating non-smooth PSF (Point Spread Function) distribution representing distortion by a turbulent field is also discussed.
Improving Software Developer's Competence: Is the Personal Software Process Working?
Venue: arXiv cs.SE 2013
Year: 2013

Emerging agile software development methods are people oriented development approaches to be used by the software industry. The personal software process (PSP) is an accepted method for improving the capabilities of a single software engineer. Five original hypotheses regarding the impact of the PSP to individual performance are tested. Data is obtained from 58 computer science students in three university courses on the master level, which were held in two different educational institutions in Finland and Denmark. Statistical data treatment shows that the use of PSP did not improve size and time estimation skills but that the productivity did not decrease and the resulting product quality was improved. The implications of these findings are briefly addressed.
An axiomatic characterization of generalized entropies under analyticity condition
Venue: arXiv cs.IT 2013
Year: 2013

We present the characterization of the Nath, Rényi and Havrda-Charvát-Tsallis entropies under the assumption that they are analytic function with respect to the distribution dimension, unlike the the previous characterizations, which supposes that they are expandable maximized for uniform distribution.
De-Virtualizing Social Events: Understanding the Gap between Online and Offline Participation for Event Invitations
Venue: arXiv cs.HC 2013
Year: 2013

One growing use of computer-based communication media is for gathering people to initiate or sustain social events. Although the use of computer-mediated communication and social network sites such as Facebook for event promotion is becoming popular, online participation in an event does not always translate to offline attendance. In this paper, we report on an interview study of 31 participants that examines how people handle online event invitations and what influences their online and offline participation. The results show that people's event participation is shaped by their social perceptions of the event's nature (e.g., public or private), their relationships to others (e.g., the strength of their connections to other invitees), and the medium used to communicate event information (e.g., targeted invitation via email or spam communication via Facebook event page). By exploring how people decide whether to participate online or offline, the results illuminate the sophisticated nature of the mechanisms that affect participation and have design implications that can bridge virtual and real attendance.