OpenRaiser/Intern-Atlas huggingface dataset:
Some remarks on relations between the $μ$-parameters of regular graphs
Venue: arXiv cs.DM 2013
Year: 2013

For an undirected, simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges, respectively. A function $φ:E(G)\rightarrow \{1,...,t\}$ is called a proper edge $t$-coloring of a graph $G$, if adjacent edges are colored differently and each of $t$ colors is used. The least value of $t$ for which there exists a proper edge $t$-coloring of a graph $G$ is denoted by $χ'(G)$. For any graph $G$, and for any integer $t$ satisfying the inequality $χ'(G)\leq t\leq |E(G)|$, we denote by $α(G,t)$ the set of all proper edge $t$-colorings of $G$. Let us also define a set $α(G)$ of all proper edge colorings of a graph $G$: $$ α(G)\equiv\bigcup_{t=χ'(G)}^{|E(G)|}α(G,t). $$ An arbitrary nonempty finite subset of consecutive integers is called an interval. If $φ\inα(G)$ and $x\in V(G)$, then the set of colors of edges of $G$ which are incident with $x$ is denoted by $S_G(x,φ)$ and is called a spectrum of the vertex $x$ of the graph $G$ at the proper edge coloring $φ$. If $G$ is a graph and $φ\inα(G)$, then define $f_G(φ)\equiv|\{x\in V(G)/S_G(x,φ) \textrm{is an interval}\}|$. For a graph $G$ and any integer $t$, satisfying the inequality $χ'(G)\leq t\leq |E(G)|$, we define: $$ μ_1(G,t)\equiv\min_{φ\inα(G,t)}f_G(φ),\qquad μ_2(G,t)\equiv\max_{φ\inα(G,t)}f_G(φ). $$ For any graph $G$, we set: $$ μ_{11}(G)\equiv\min_{χ'(G)\leq t\leq|E(G)|}μ_1(G,t),\qquad μ_{12}(G)\equiv\max_{χ'(G)\leq t\leq|E(G)|}μ_1(G,t), $$ $$ μ_{21}(G)\equiv\min_{χ'(G)\leq t\leq|E(G)|}μ_2(G,t),\qquad μ_{22}(G)\equiv\max_{χ'(G)\leq t\leq|E(G)|}μ_2(G,t). $$ For regular graphs, some relations between the $μ$-parameters are obtained.
Consistency Analysis of Sensor Data Distribution
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we analyze the probability of consistency of sensor data distribution systems (SDDS), and determine suitable evaluation models. This problem is typically difficult, since a reliable model taking into account all parameters and processes which affect the system consistency is unavoidably very complex. The simplest candidate approach consists of modeling the state sojourn time, or holding time, as memoryless, and resorting to the well known solutions of Markovian processes. Nevertheless, it may happen that this approach does not fit with some working conditions. In particular, the correct modeling of the SDDS dynamics requires the introduction of a number of parameters, such as the packet transfer time or the packet loss probability, the value of which may determine the suitability of unsuitability of the Markovian model. Candidate alternative solutions include the Erlang phase-type approximation of nearly constant state holding time and a more refined model to account for overlapping events in semi-Markov processes.
Application Behavior Enforcement Based On Network Characteristics
Venue: arXiv cs.NI 2013
Year: 2013

Every device defines the behavior of various applications running on it with the help of user profiles or settings. What if a user wants different different applications to run in different different networks. Then he cannot do this because in todays existing operating systems the application profile, user specific tool settings and any such system usage settings do not consider the current network characteristics of the user or system and are therefore static in nature.Therefore there is a need for an intelligent system which will dynamically change or apply changes to the settings of various applications running on the system considering the current network characteristics based on user specifications. This paper presents an idea such that a user can set different different applications in different different networks.This paper presents how the user will get pop up messages when he visits to safe web sites. And according to the users current network status he will get a pop up message when he will go for download or stream audio or video files.
Privatizing user credential information of Web services in a shared user environment
Venue: arXiv cs.CR 2013
Year: 2013

User credentials security is one of the most important tasks in Web World. Most Web sites on the Internet that support user accounts store the users credentials in a database. Now a days, most of the web browsers offer auto login feature for the favorite web sites such as yahoo, google, gmail etc. using these credential information. This facilitates the misuse of user credentials. Privatizing user credential information of web services in a shared user environment provides a feature enhancement where the root user will be able to privatize his stored credentials by enforcing some masking techniques such that even a user logs on to the system with root user credentials, he will not be able to access privatized data. In case of web browsers auto login feature, a root user can disable the feature manually by deleting entries from web browsers' saved password list. But this involves spending a considerable amount of time and the biggest problem is that he has to insert those credentials once again when he next visits these websites. This application resumes auto login feature whenever root user disable the masked mode. The application includes two parts: Masked Application Mode and Disabling the Masked Application Mode. When the system goes for masked application mode, the other user will not be able to use the credentials of the root user.If the other user tries to access any of the web pages which have been masked, the other user will have to authenticate with his own credentials. Disabling the masked mode requires authentication from the root user. As long as this credential is not shared, masked mode can be disabled only by the root user.
A Construction of Quantum Codes via A Class of Classical Polynomial Codes
Venue: arXiv cs.IT 2013
Year: 2013

There have been various constructions of classical codes from polynomial valuations in literature \cite{ARC04, LNX01,LX04,XF04,XL00}. In this paper, we present a construction of classical codes based on polynomial construction again. One of the features of this construction is that not only the classical codes arisen from the construction have good parameters, but also quantum codes with reasonably good parameters can be produced from these classical codes. In particular, some new quantum codes are constructed (see Examples \ref{5.5} and \ref{5.6}).
Polynomial kernels collapse the W-hierarchy
Venue: arXiv cs.CC 2013
Year: 2013

We prove that, for many parameterized problems in the class FPT, the existence of polynomial kernels implies the collapse of the W-hierarchy (i.e., W[P] = FPT). The collapsing results are also extended to assumed exponential kernels for problems in the class FPT. In particular, we establish a close relationship between polynomial (and exponential) kernelizability and the existence of sub-exponential time algorithms for a spectrum of circuit satisfiability problems in FPT. To the best of our knowledge, this is the first work that connects hardness for polynomial kernelizability of FPT problems to parameterized intractability. Our work also offers some new insights into the class FPT.
On the State and Importance of Reproducible Experimental Research in Parallel Computing
Venue: arXiv cs.DC 2013
Year: 2013

Computer science is also an experimental science. This is particularly the case for parallel computing, which is in a total state of flux, and where experiments are necessary to substantiate, complement, and challenge theoretical modeling and analysis. Here, experimental work is as important as are advances in theory, that are indeed often driven by the experimental findings. In parallel computing, scientific contributions presented in research articles are therefore often based on experimental data, with a substantial part devoted to presenting and discussing the experimental findings. As in all of experimental science, experiments must be presented in a way that makes reproduction by other researchers possible, in principle. Despite appearance to the contrary, we contend that reproducibility plays a small role, and is typically not achieved. As can be found, articles often do not have a sufficiently detailed description of their experiments, and do not make available the software used to obtain the claimed results. As a consequence, parallel computational results are most often impossible to reproduce, often questionable, and therefore of little or no scientific value. We believe that the description of how to reproduce findings should play an important part in every serious, experiment-based parallel computing research article. We aim to initiate a discussion of the reproducibility issue in parallel computing, and elaborate on the importance of reproducible research for (1) better and sounder technical/scientific papers, (2) a sounder and more efficient review process and (3) more effective collective work. This paper expresses our current view on the subject and should be read as a position statement for discussion and future work. We do not consider the related (but no less important) issue of the quality of the experimental design.
Decision Theory with Resource-Bounded Agents
Venue: arXiv cs.GT 2013
Year: 2013

There have been two major lines of research aimed at capturing resource-bounded players in game theory. The first, initiated by Rubinstein, charges an agent for doing costly computation; the second, initiated by Neyman, does not charge for computation, but limits the computation that agents can do, typically by modeling agents as finite automata. We review recent work on applying both approaches in the context of decision theory. For the first approach, we take the objects of choice in a decision problem to be Turing machines, and charge players for the ``complexity'' of the Turing machine chosen (e.g., its running time). This approach can be used to explain well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on) and belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions) as the outcomes of quite rational decisions. For the second approach, we model people as finite automata, and provide a simple algorithm that, on a problem that captures a number of settings of interest, provably performs optimally as the number of states in the automaton increases.
Strict majority bootstrap percolation in the r-wheel
Venue: arXiv cs.SI 2013
Year: 2013

In this paper we study the strict majority bootstrap percolation process on graphs. Vertices may be active or passive. Initially, active vertices are chosen independently with probability p. Each passive vertex becomes active if at least half of its neighbors are active (and thereafter never changes its state). If at the end of the process all vertices become active then we say that the initial set of active vertices percolates on the graph. We address the problem of finding graphs for which percolation is likely to occur for small values of p. Specifically, we study a graph that we call r-wheel: a ring of n vertices augmented with a universal vertex where each vertex in the ring is connected to its r closest neighbors to the left and to its r closest neighbors to the right. We prove that the critical probability is 1/4. In other words, if p>1/4 then for large values of r percolation occurs with probability arbitrarily close to 1 as n goes to infinity. On the other hand, if p<1/4 then the probability of percolation is bounded away from 1.
Measurement and Prediction of Centrical/Peripheral Network Properties based on Regression Analysis - A Parametric Foundation for Performance Self-Management in WSNs
Venue: arXiv cs.PF 2013
Year: 2013

Predicting performance-related behavior of the underlying network structure becomes more and more indispensable in terms of the aspired application outcome quality. However, the reliable forecast of QoS metrics like packet transfer delay in wireless network systems is still a challenging task. Even though existing approaches are technically capable of determining such network properties under certain assumptions, they mostly abstract away from primal aspects that inherently have an essential impact on temporal network performance dynamics. Also, they usually require auxiliary resources to be implemented and deployed along with the actual network components. In the course of developing a lightweight measurement-based alternative for the self-inspection and prediction of volatile performance characteristics in environments of any kind, we selectively investigate the duration of message delivery and packet loss rate against various parameters peculiar to common radio network technologies like Wireless Sensor Networks (WSNs). Our hands-on experiments reveal the relations between the oftentimes underestimated medium access delay and a variety of main influencing factors including packet size, backoff period, and number of neighbor nodes contending for the communication medium. A closed formulation of selected weighted drivers facilitates the average-case prediction of inter-node packet transfer delays for arbitrary configurations of given network parameters even on resource-scarce WSN devices. We validate our prediction method against basic multi-hop networking scenarios. Yield field test results proof the basic feasibility and high precision of our approach to network property estimation in virtue of self-governed local measurements and regression-based calculations paving the way for a prospective self-management of network properties based upon autonomous distributed coordination.
Efficiently Retrieving Function Dependencies in the Linux Kernel Using XSB
Venue: arXiv cs.PL 2013
Year: 2013

In this paper we investigate XSB-Prolog as a static analysis engine for data represented by medium-sized graphs. We use XSB-Prolog to automatically identify function dependencies in the Linux Kernel---queries that are difficult to implement efficiently in a commodity database and that developers often have to identify manually. This project illustrates that Prolog systems are ideal for building tools for use in other disciplines that require sophisticated inferences, because Prolog is both declarative and can efficiently implement complex problem specifications through tabling and indexing.
Efficient Leverage of Symbolic ATG Tools to Advanced Coverage Criteria
Venue: arXiv cs.SE 2013
Year: 2013

Automatic test data generation (ATG) is a major topic in software engineering. In this paper, we seek to bridge the gap between the coverage criteria supported by symbolic ATG tools and the most advanced coverage criteria found in the literature. We define a new testing criterion, label coverage, and prove it to be both expressive and amenable to efficient automation. We propose several innovative techniques resulting in an effective black-box support for label coverage, while a direct approach induces an exponential blow-up of the search space. Initial experiments show that ATG for label coverage can be achieved at a reasonable cost and that our optimisations yield very significant savings.
Ultra-low Energy, High Performance and Programmable Magnetic Threshold Logic
Venue: arXiv cs.ET 2013
Year: 2013

We propose magnetic threshold-logic (MTL) design based on non-volatile spin-torque switches. A threshold logic gate (TLG) performs summation of multiple inputs multiplied by a fixed set of weights and compares the sum with a threshold. MTL employs resistive states of magnetic tunnel junctions as programmable input weights, while, a low-voltage domain-wall shift based spin-torque switch is used for thresholding operation. The resulting MTL gate acts as a low-power, configurable logic unit and can be used to build fully pipelined, high-performance programmable computing blocks. Multiple stages in such a MTL design can be connected using energy-efficient ultralow swing programmable interconnect networks based on resistive switches. Owing to memory-based compact logic and interconnect design and low-voltage, high-speed spintorque based threshold operation, MTL can achieve more than two orders of magnitude improvement in energy-delay product as compared to look-up table based CMOS FPGA.
Towards an Effective Decision Procedure for LTL formulas with Constraints
Venue: arXiv cs.LO 2013
Year: 2013

This paper presents an ongoing work that is part of a more wide-ranging project whose final scope is to define a method to validate LTL formulas w.r.t. a program written in the timed concurrent constraint language tccp, which is a logic concurrent constraint language based on the concurrent constraint paradigm of Saraswat. Some inherent notions to tccp processes are non-determinism, dealing with partial information in states and the monotonic evolution of the information. In order to check an LTL property for a process, our approach is based on the abstract diagnosis technique. The concluding step of this technique needs to check the validity of an LTL formula (with constraints) in an effective way. In this paper, we present a decision method for the validity of temporal logic formulas (with constraints) built by our abstract diagnosis technique.
On Optimal and Fair Service Allocation in Mobile Cloud Computing
Venue: arXiv cs.DC 2013
Year: 2013

This paper studies the optimal and fair service allocation for a variety of mobile applications (single or group and collaborative mobile applications) in mobile cloud computing. We exploit the observation that using tiered clouds, i.e. clouds at multiple levels (local and public) can increase the performance and scalability of mobile applications. We proposed a novel framework to model mobile applications as a location-time workflows (LTW) of tasks; here users mobility patterns are translated to mobile service usage patterns. We show that an optimal mapping of LTWs to tiered cloud resources considering multiple QoS goals such application delay, device power consumption and user cost/price is an NP-hard problem for both single and group-based applications. We propose an efficient heuristic algorithm called MuSIC that is able to perform well (73% of optimal, 30% better than simple strategies), and scale well to a large number of users while ensuring high mobile application QoS. We evaluate MuSIC and the 2-tier mobile cloud approach via implementation (on real world clouds) and extensive simulations using rich mobile applications like intensive signal processing, video streaming and multimedia file sharing applications. Our experimental and simulation results indicate that MuSIC supports scalable operation (100+ concurrent users executing complex workflows) while improving QoS. We observe about 25% lower delays and power (under fixed price constraints) and about 35% decrease in price (considering fixed delay) in comparison to only using the public cloud. Our studies also show that MuSIC performs quite well under different mobility patterns, e.g. random waypoint and Manhattan models.
Coded Acquisition of High Frame Rate Video
Venue: arXiv cs.MM 2013
Year: 2013

High frame video (HFV) is an important investigational tool in sciences, engineering and military. In ultra-high speed imaging, the obtainable temporal, spatial and spectral resolutions are limited by the sustainable throughput of in-camera mass memory, the lower bound of exposure time, and illumination conditions. In order to break these bottlenecks, we propose a new coded video acquisition framework that employs K > 2 conventional cameras, each of which makes random measurements of the 3D video signal in both temporal and spatial domains. For each of the K cameras, this multi-camera strategy greatly relaxes the stringent requirements in memory speed, shutter speed, and illumination strength. The recovery of HFV from these random measurements is posed and solved as a large scale l1 minimization problem by exploiting joint temporal and spatial sparsities of the 3D signal. Three coded video acquisition techniques of varied trade offs between performance and hardware complexity are developed: frame-wise coded acquisition, pixel-wise coded acquisition, and column-row-wise coded acquisition. The performances of these techniques are analyzed in relation to the sparsity of the underlying video signal. Simulations of these new HFV capture techniques are carried out and experimental results are reported.
External Memory Algorithms For Path Traversal in Graphs
Venue: arXiv cs.DS 2013
Year: 2013

This thesis presents a number of results related to path traversal in trees and graphs. In particular, we focus on data structures which allow such traversals to be performed efficiently in the external memory setting. In addition, for trees and planar graphs the data structures we present are succinct. Our tree structures permit efficient bottom-up path traversal in rooted trees of arbitrary degree and efficient top-down path traversal in binary trees. In the graph setting, we permit efficient traversal of an arbitrary path in bounded degree planar graphs. Our data structures for both trees and graphs match or slightly improve current best results for external memory path traversal in these settings while at the same time improving space bounds due to the succinct nature of our data structures. Employing our path traversal structure for bounded degree planar graphs, we describe a number of useful applications of this technique for triangular meshes in R^2. As an extension of the R^2 representation for triangular meshes we also present an efficient external memory representation for well-shaped tetrahedral meshes in R^3. The external memory representation we present is based on a partitioning scheme that matches the current best-known results for well-shaped tetrahedral meshes. We describe applications of path traversal in tetrahedral meshes which are made efficient in the external memory setting using our structure. Finally, we present a result on using jump-and-walk point location in well-shaped meshes in both R^2 and R^3. We demonstrate that, given an approximate nearest neighbour from among the vertices of a mesh, locating the simplex containing the query point involves a constant length walk (path traversal) in the mesh.
Codeword or noise? Exact random coding exponents for slotted asynchronism
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of slotted asynchronous coded communication, where in each time frame (slot), the transmitter is either silent or transmits a codeword from a given (randomly selected) codebook. The task of the decoder is to decide whether transmission has taken place, and if so, to decode the message. We derive the optimum detection/decoding rule in the sense of the best trade-off among the probabilities of decoding error, false alarm, and misdetection. For this detection/decoding rule, we then derive single-letter characterizations of the exact exponential rates of these three probabilities for the average code in the ensemble.