OpenRaiser/Intern-Atlas huggingface dataset:
Fixed Parameter Inapproximability for Clique and SetCover in Time Super-exponential in OPT
Venue: arXiv cs.CC 2013
Year: 2013

In this paper, we consider proving inapproximability in terms of OPT and thus we base the foundations of fixed parameter inapproximability.
Low-cost photoplethysmograph solutions using the Raspberry Pi
Venue: arXiv cs.SY 2013
Year: 2013

Photoplethysmography is a prevalent, non-invasive heart monitoring method. In this paper an implementation of photoplethysmography on the Raspberry Pi is presented. Two modulation techniques are discussed, which make possible to measure these signals by the Raspberry Pi, using an external sound card as A/D converter. Furthermore, it is shown, how can digital signal processing improve signal quality. The presented methods can be used in low-cost cardiac function monitoring, in telemedicine applications and in education as well, since cheap and current hardware are used. Full documentation and open-source software for the measurement available: http://www.noise.inf.u-szeged.hu/Instruments/raspberryplet/
Waterfall: Primitives Generation on the Fly
Venue: arXiv cs.PL 2013
Year: 2013

Modern languages are typically supported by managed runtimes (Virtual Machines). Since VMs have to deal with many concepts such as memory management, abstract execution model and scheduling, they tend to be very complex. Additionally, VMs have to meet strong performance requirements. This demand of performance is one of the main reasons why many VMs are built statically. Thus, design decisions are frozen at compile time preventing changes at runtime. One clear example is the impossibility to dynamically adapt or change primitives of the VM once it has been compiled. In this work we present a toolchain that allows for altering and configuring components such as primitives and plug-ins at runtime. The main contribution is Waterfall, a dynamic and reflective translator from Slang, a restricted subset of Smalltalk, to native code. Waterfall generates primitives on demand and executes them on the fly. We validate our approach by implementing dynamic primitive modification and runtime customization of VM plug-ins.
IMSuite: A Benchmark Suite for Simulating Distributed Algorithms
Venue: arXiv cs.DC 2013
Year: 2013

Considering the diverse nature of real-world distributed applications that makes it hard to identify a representative subset of distributed benchmarks, we focus on their underlying distributed algorithms. We present and characterize a new kernel benchmark suite (named IMSuite) that simulates some of the classical distributed algorithms in task parallel languages. We present multiple variations of our kernels, broadly categorized under two heads: (a) varying synchronization primitives (with and without fine grain synchronization primitives); and (b) varying forms of parallelization (data parallel and recursive task parallel). Our characterization covers interesting aspects of distributed applications such as distribution of remote communication requests, number of synchronization, task creation, task termination and atomic operations. We study the behavior (execution time) of our kernels by varying the problem size, the number of compute threads, and the input configurations. We also present an involved set of input generators and output validators.
Virtual Location-Based Services: Merging the Physical and Virtual World
Venue: arXiv cs.CY 2013
Year: 2013

Location-based services gained much popularity through providing users with helpful information with respect to their current location. The search and recommendation of nearby locations or places, and the navigation to a specific location are some of the most prominent location-based services. As a recent trend, virtual location-based services consider webpages or sites associated with a location as 'virtual locations' that online users can visit in spite of not being physically present at the location. The presence of links between virtual locations and the corresponding physical locations (e.g., geo-location information of a restaurant linked to its website), allows for novel types of services and applications which constitute virtual location-based services (VLBS). The quality and potential benefits of such services largely depends on the existence of websites referring to physical locations. In this paper, we investigate the usefulness of linking virtual and physical locations. For this, we analyze the presence and distribution of virtual locations, i.e., websites referring to places, for two Irish cities. Using simulated tracks based on a user movement model, we investigate how mobile users move through the Web as virtual space. Our results show that virtual locations are omnipresent in urban areas, and that the situation that a user is close to even several such locations at any time is rather the normal case instead of the exception.
Limit Synchronization in Markov Decision Processes
Venue: arXiv cs.GT 2013
Year: 2013

Markov decision processes (MDP) are finite-state systems with both strategic and probabilistic choices. After fixing a strategy, an MDP produces a sequence of probability distributions over states. The sequence is eventually synchronizing if the probability mass accumulates in a single state, possibly in the limit. Precisely, for 0 <= p <= 1 the sequence is p-synchronizing if a probability distribution in the sequence assigns probability at least p to some state, and we distinguish three synchronization modes: (i) sure winning if there exists a strategy that produces a 1-synchronizing sequence; (ii) almost-sure winning if there exists a strategy that produces a sequence that is, for all epsilon > 0, a (1-epsilon)-synchronizing sequence; (iii) limit-sure winning if for all epsilon > 0, there exists a strategy that produces a (1-epsilon)-synchronizing sequence. We consider the problem of deciding whether an MDP is sure, almost-sure, limit-sure winning, and we establish the decidability and optimal complexity for all modes, as well as the memory requirements for winning strategies. Our main contributions are as follows: (a) for each winning modes we present characterizations that give a PSPACE complexity for the decision problems, and we establish matching PSPACE lower bounds; (b) we show that for sure winning strategies, exponential memory is sufficient and may be necessary, and that in general infinite memory is necessary for almost-sure winning, and unbounded memory is necessary for limit-sure winning; (c) along with our results, we establish new complexity results for alternating finite automata over a one-letter alphabet.
SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine
Venue: arXiv cs.DC 2013
Year: 2013

Client-side logic and storage are increasingly used in web and mobile applications to improve response time and availability. Current approaches tend to be ad-hoc and poorly integrated with the server-side logic. We present a principled approach to integrate client- and server-side storage. We support mergeable and strongly consistent transactions that target either client or server replicas and provide access to causally-consistent snapshots efficiently. In the presence of infrastructure faults, a client-assisted failover solution allows client execution to resume immediately and seamlessly access consistent snapshots without waiting. We implement this approach in SwiftCloud, the first transactional system to bring geo-replication all the way to the client machine. Example applications show that our programming model is useful across a range of application areas. Our experimental evaluation shows that SwiftCloud provides better fault tolerance and at the same time can improve both latency and throughput by up to an order of magnitude, compared to classical geo-replication techniques.
Keyboards for inputting Japanese language -A study based on US patents
Venue: arXiv cs.HC 2013
Year: 2013

The most commonly used Japanese alphabets are Kanji, Hiragana and Katakana. The Kanji alphabet includes pictographs or ideographic characters that were adopted from the Chinese alphabet. Hiragana is used to spell words of Japanese origin, while Katakana is used to spell words of western or other foreign origin. Two methods are commonly used to input Japanese to the computer. One, the 'kana input method' that uses a keyboard having 46 Japanese iroha (or kana) letter keys. The other method is 'Roma-ji input method', where the Japanese letters are composed of English input from a standard QWERTY keyboard. Both the methods have their advantages and disadvantages. This article analyses two inventions on inputting Japanese language through a computer keyboard. One invention uses a standard English keyboard to input Japanese characters, the other invention uses a standard mobile phone key board to input the Japanese characters.
Valuation Compressions in VCG-Based Combinatorial Auctions
Venue: arXiv cs.GT 2013
Year: 2013

The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes.
10 Inventions on Key Guides and Keyboard Templates
Venue: arXiv cs.HC 2013
Year: 2013

A keyboard has many function keys and each function key can have multiple functions when used with control, shift and alt keys, it is difficult for a user to remember the functionality of the function keys. We need a mechanism to indicate the operations assigned to each function key for different software programs. A keyboard guide or template is used for this purpose. This article illustrates 10 inventions on keyboard key guide and function key templates selected from US patent database. Various mechanisms of keyboard templates have been proposed, including static, dynamic, manual, mechanical, onscreen display and others.
Measuring Software Diversity, with Applications to Security
Venue: arXiv cs.CR 2013
Year: 2013

In this work, we briefly introduce and discuss some of the diversity measures used in Ecology. After a succinct description and analysis of the most relevant ones, we single out the Shannon-Weiner index. We justify why it is the most informative and relevant one for measuring software diversity. Then, we show how it can be used for effectively assessing the diversity of various real software ecosystems. We discover in the process a frequently overlooked software monopoly, and its key security implications. We finally extract some conclusions from the results obtained, focusing mostly on their security implications.
A Preliminary Field Study of Game Programming on Mobile Devices
Venue: arXiv cs.SE 2013
Year: 2013

TouchDevelop is a new programming environment that allows users to create applications on mobile devices. Applications created with TouchDevelop have continued to grow in popularity since TouchDevelop was first released to public in 2011. This paper presents a field study of 31,699 applications, focusing on different characteristics between 539 game scripts and all other non-game applications, as well as what make some game applications more popular than others to users. The study provides a list of findings on characteristics of game scripts and also implications for improving end-user programming of game applications.
Multicriteria Evaluation and Sensitivity Analysis on Information Security
Venue: arXiv cs.CY 2013
Year: 2013

Information security plays a significant role in recent information society. Increasing number and impact of cyber attacks on information assets have resulted the increasing awareness among managers that attack on information is actually attack on organization itself. Unfortunately, particular model for information security evaluation for management levels is still not well defined. In this study, decision analysis based on Ternary Analytic Hierarchy Process (T-AHP) is proposed as a novel model to aid managers who responsible in making strategic evaluation related to information security issues. In addition, sensitivity analysis is applied to extend our analysis by using several "what-if" scenarios in order to measure the consistency of the final evaluation. Finally, we conclude that the final evaluation made by managers has a significant consistency shown by sensitivity analysis results.
Joint Indoor Localization and Radio Map Construction with Limited Deployment Load
Venue: arXiv cs.NI 2013
Year: 2013

One major bottleneck in the practical implementation of received signal strength (RSS) based indoor localization systems is the extensive deployment efforts required to construct the radio maps through fingerprinting. In this paper, we aim to design an indoor localization scheme that can be directly employed without building a full fingerprinted radio map of the indoor environment. By accumulating the information of localized RSSs, this scheme can also simultaneously construct the radio map with limited calibration. To design this scheme, we employ a source data set that possesses the same spatial correlation of the RSSs in the indoor environment under study. The knowledge of this data set is then transferred to a limited number of calibration fingerprints and one or several RSS observations with unknown locations, in order to perform direct localization of these observations using manifold alignment. We test two different source data sets, namely a simulated radio propagation map and the environments plan coordinates. For moving users, we exploit the correlation of their observations to improve the localization accuracy. The online testing in two indoor environments shows that the plan coordinates achieve better results than the simulated radio maps, and a negligible degradation with 70-85% reduction in calibration load.
Optimal Energy Consumption Model for Smart Grid Households with Energy Storage
Venue: arXiv cs.OH 2013
Year: 2013

In this paper, we propose to model the energy consumption of smart grid households with energy storage systems as an intertemporal trading economy. Intertemporal trade refers to transaction of goods across time when an agent, at any time, is faced with the option of consuming or saving with the aim of using the savings in the future or spending the savings from the past. Smart homes define optimal consumption as either balancing/leveling consumption such that the utility company is presented with a uniform demand or as minimizing consumption costs by storing energy during off-peak time periods when prices are lower and use the stored energy during peak time periods when prices are higher. Due to the varying nature of energy requirements of household and market energy prices over different time periods in a day, households face a trade-off between consuming to meet their current energy requirements and/or storing energy for future consumption and/or spending energy stored in the past. These trade-offs or consumption preferences of the household are modeled as utility functions using consumer theory. We introduce two different utility functions, one for cost minimization and another for consumption balancing/leveling, that are maximized subject to respective budget, consumption, storage and savings constraints to solve for the optimum consumption profile. The optimization problem of a household with energy storage is formulated as a geometric program for consumption balancing/leveling, while cost minimization is formulated as a linear programming problem. Simulation results show that the proposed model achieves extremely low peak to average ratio in the consumption balancing/leveling scheme with about 8% reduction in consumption costs and the least possible amount for electricity bill with about 12% reduction in consumption costs in the cost minimization scheme.
Linear Extended Whitening Filters
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we present a class of linear whitening filters termed linear extended whitening filters (EWFs) which are whitening filters that have desirable secondary properties and can be used for simplifying algorithms, or achieving desired side-effects on given secondary matrices, random vectors or random processes. Further, we present an application of EWFs for simplification of QR decomposition based ML detection algorithm in Wireless Communication.
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation
Venue: arXiv cs.DS 2013
Year: 2013

We describe an asynchronous algorithm to solve secure multiparty computation (MPC) over n players, when strictly less than a 1/8 fraction of the players are controlled by a static adversary. For any function f over a field that can be computed by a circuit with m gates, our algorithm requires each player to send a number of field elements and perform an amount of computation that is O (m/n + \sqrt{n}). This significantly improves over traditional algorithms, which require each player to both send a number of messages and perform computation that is Ω(nm). Additionally, we define the threshold counting problem and present a distributed algorithm to solve it in the asynchronous communication model. Our algorithm is load balanced, with computation, communication and latency complexity of O(log n), and may be of independent interest to other applications with a load balancing goal in mind.
Can Twitter Predict Royal Baby's Name ?
Venue: arXiv cs.SI 2013
Year: 2013

In this paper, we analyze the existence of possible correlation between public opinion of twitter users and the decision-making of persons who are influential in the society. We carry out this analysis on the example of the discussion of probable name of the British crown baby, born in July, 2013. In our study, we use the methods of quantitative processing of natural language, the theory of frequent sets, the algorithms of visual displaying of users' communities. We also analyzed the time dynamics of keyword frequencies. The analysis showed that the main predictable name was dominating in the spectrum of names before the official announcement. Using the theories of frequent sets, we showed that the full name consisting of three component names was the part of top 5 by the value of support. It was revealed that the structure of dynamically formed users' communities participating in the discussion is determined by only a few leaders who influence significantly the viewpoints of other users.
Lowest Density MDS Array Codes for Reliable Smart Meter Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we introduce a lowest density MDS array code which is applied to a Smart Meter network to introduce reliability. By treating the network as distributed storage with multiple sources, information can be exchanged between the nodes in the network allowing each node to store parity symbols relating to data from other nodes. A lowest density MDS array code is then applied to make the network robust against outages, ensuring low overhead and data transfers. We show the minimum amount of overhead required to be able to recover from r node erasures in an n node network and explicitly design an optimal array code with lowest density. In contrast to existing codes, this one has no restrictions on the number of nodes or erasures it can correct. Furthermore we consider incomplete networks where all nodes are not connected to each other. This limits the exchange of data for purposes of redundancy and we derive conditions on the minimum node degree that allow lowest density MDS codes to exist. We also present an explicit code design for incomplete networks that is capable of correcting two node failures.
Computing the Kullback-Leibler Divergence between two Weibull Distributions
Venue: arXiv cs.IT 2013
Year: 2013

We derive a closed form solution for the Kullback-Leibler divergence between two Weibull distributions. These notes are meant as reference material and intended to provide a guided tour towards a result that is often mentioned but seldom made explicit in the literature.
Security policies for distributed systems
Venue: arXiv cs.CR 2013
Year: 2013

A security policy specifies a security property as the maximal information flow. A distributed system composed of interacting processes implicitly defines an intransitive security policy by repudiating direct information flow between processes that do not exchange messages directly. We show that implicitly defined security policies in distributed systems are enforced, provided that processes run in separation, and possible process communication on a technical platform is restricted to specified message paths of the system. Furthermore, we propose to further restrict the allowable information flow by adding filter functions for controlling which messages may be transmitted between processes, and we prove that locally checking filter functions is sufficient for ensuring global security policies. Altogether, global intransitive security policies are established by means of local verification conditions for the (trusted) processes of the distributed system. Moreover, security policies may be implemented securely on distributed integration platforms which ensure partitioning. We illustrate our results with a smart grid case study, where we use CTL model checking for discharging local verification conditions for each process under consideration.
Spatially Coupled Sparse Codes on Graphs - Theory and Practice
Venue: arXiv cs.IT 2013
Year: 2013

Since the discovery of turbo codes 20 years ago and the subsequent re-discovery of low-density parity-check codes a few years later, the field of channel coding has experienced a number of major advances. Up until that time, code designers were usually happy with performance that came within a few decibels of the Shannon Limit, primarily due to implementation complexity constraints, whereas the new coding techniques now allow performance within a small fraction of a decibel of capacity with modest encoding and decoding complexity. Due to these significant improvements, coding standards in applications as varied as wireless mobile transmission, satellite TV, and deep space communication are being updated to incorporate the new techniques. In this paper, we review a particularly exciting new class of low-density parity-check codes, called spatially-coupled codes, which promise excellent performance over a broad range of channel conditions and decoded error rate requirements.
Efficient Modular Arithmetic for SIMD Devices
Venue: arXiv cs.CR 2013
Year: 2013

This paper describes several new improvements of modular arithmetic and how to exploit them in order to gain more efficient implementations of commonly used algorithms, especially in cryptographic applications. We further present a new record for modular multiplications per second on a single desktop computer as well as a new record for the ECM factoring algorithm. This new results allow building personal computers which can handle more than 3 billion modular multiplications per second for a 192 bit module at moderate costs using modern graphic cards.