OpenRaiser/Intern-Atlas huggingface dataset:
Social Networks and the Choices People Make
Venue: arXiv cs.SI 2014
Year: 2014

Social marketing is becoming increasingly important in contemporary business. Central to social marketing is quantifying how consumers choose between alternatives and how they influence each other. This work considers a new but simple multinomial choice model for multiple agents connected in a recommendation network based on the explicit modeling of choice adoption behavior. Efficiently computable closed-form solutions, absent from analyses of threshold/cascade models, are obtained together with insights on how the network affects aggregate decision making. A stylized "brand ambassador" selection problem is posed to model targeting in social marketing. Therein, it is shown that a greedy selection strategy leads to solutions achieving at least $1-1/e$ of the optimal value. In an extended example of imposing exogenous controls, a pricing problem is considered wherein it is shown that the single player profit optimization problem is concave, implying the existence of pure strategy equilibria for the associated pricing game.
Voltage and Level-Shifter Assignment Driven Floorplanning
Venue: arXiv cs.AR 2014
Year: 2014

Low Power Design has become a significant requirement when the CMOS technology entered the nanometer era. Multiple-Supply Voltage (MSV) is a popular and effective method for both dynamic and static power reduction while maintaining performance. Level shifters may cause area and Interconnect Length Overhead (ILO), and should be considered at both floorplanning and post-floorplanning stages. In this paper, we propose a two phases algorithm framework, called VLSAF, to solve voltage and level shifter assignment problem. At floorplanning phase, we use a convex cost network flow algorithm to assign voltage and a minimum cost flow algorithm to handle level-shifter assignment. At post-floorplanning phase, a heuristic method is adopted to redistribute white spaces and calculate the positions and shapes of level shifters. The experimental results show VLSAF is effective.
Lithography Hotspot Detection and Mitigation in Nanometer VLSI
Venue: arXiv cs.AR 2014
Year: 2014

With continued feature size scaling, even state of the art semiconductor manufacturing processes will often run into layouts with poor printability and yield. Identifying lithography hotspots is important at both physical verification and early physical design stages. While detailed lithography simulations can be very accurate, they may be too computationally expensive for full-chip scale and physical design inner loops. Meanwhile, pattern matching and machine learning based hotspot detection methods can provide acceptable quality and yet fast turn-around-time for full-chip scale physical verification and design. In this paper, we discuss some key issues and recent results on lithography hotspot detection and mitigation in nanometer VLSI.
Homogenization of coupled heat and moisture transport in masonry structures including interfaces
Venue: arXiv cs.CE 2014
Year: 2014

Homogenization of a simultaneous heat and moisture flow in a masonry wall is presented in this paper. The principle objective is to examine an impact of the assumed imperfect hydraulic contact on the resulting homogenized properties. Such a contact is characterized by a certain mismatching resistance allowing us to represent a discontinuous evolution of temperature and moisture fields across the interface, which is in general attributed to discontinuous capillary pressures caused by different pore size distributions of the adjacent porous materials. In achieving this, two particular laboratory experiments were performed to provide distributions of temperature and relative humidity in a sample of the masonry wall, which in turn served to extract the corresponding jumps and subsequently to obtain the required interface transition parameters by matching numerical predictions and experimental results. The results suggest a low importance of accounting for imperfect hydraulic contact for the derivation of macroscopic homogenized properties. On the other hand, they strongly support the need for a fully coupled multi-scale analysis due to significant dependence of the homogenized properties on actual moisture gradients and corresponding values of both macroscopic temperature and relative humidity.
Learning-Based Optimization of Cache Content in a Small Cell Base Station
Venue: arXiv cs.IT 2014
Year: 2014

Optimal cache content placement in a wireless small cell base station (sBS) with limited backhaul capacity is studied. The sBS has a large cache memory and provides content-level selective offloading by delivering high data rate contents to users in its coverage area. The goal of the sBS content controller (CC) is to store the most popular contents in the sBS cache memory such that the maximum amount of data can be fetched directly form the sBS, not relying on the limited backhaul resources during peak traffic periods. If the popularity profile is known in advance, the problem reduces to a knapsack problem. However, it is assumed in this work that, the popularity profile of the files is not known by the CC, and it can only observe the instantaneous demand for the cached content. Hence, the cache content placement is optimised based on the demand history. By refreshing the cache content at regular time intervals, the CC tries to learn the popularity profile, while exploiting the limited cache capacity in the best way possible. Three algorithms are studied for this cache content placement problem, leading to different exploitation-exploration trade-offs. We provide extensive numerical simulations in order to study the time-evolution of these algorithms, and the impact of the system parameters, such as the number of files, the number of users, the cache size, and the skewness of the popularity profile, on the performance. It is shown that the proposed algorithms quickly learn the popularity profile for a wide range of system parameters.
Differential Privacy: An Economic Method for Choosing Epsilon
Venue: arXiv cs.DB 2014
Year: 2014

Differential privacy is becoming a gold standard for privacy research; it offers a guaranteed bound on loss of privacy due to release of query results, even under worst-case assumptions. The theory of differential privacy is an active research area, and there are now differentially private algorithms for a wide range of interesting problems. However, the question of when differential privacy works in practice has received relatively little attention. In particular, there is still no rigorous method for choosing the key parameter $ε$, which controls the crucial tradeoff between the strength of the privacy guarantee and the accuracy of the published results. In this paper, we examine the role that these parameters play in concrete applications, identifying the key questions that must be addressed when choosing specific values. This choice requires balancing the interests of two different parties: the data analyst and the prospective participant, who must decide whether to allow their data to be included in the analysis. We propose a simple model that expresses this balance as formulas over a handful of parameters, and we use our model to choose $ε$ on a series of simple statistical studies. We also explore a surprising insight: in some circumstances, a differentially private study can be more accurate than a non-private study for the same cost, under our model. Finally, we discuss the simplifying assumptions in our model and outline a research agenda for possible refinements.
EDOCR: Energy Density On-demand Cluster Routing in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Energy management is one of the critical parameters in Wireless Sensor Networks. In this paper we attempt for a solution to balance the energy usage for maximizing the network lifetime, increase the packet delivery ratio and throughput. Our proposed algorithm is based on Energy Density of the clusters in Wireless Sensor Networks. The cluster head is selected using two step method and on-demand routing approach to calculate the balanced energy shortest path from source to sink. This unique approach maintains the balanced energy utilization among all nodes by selecting the different cluster heads dynamically. Our simulation results have compared with one of the plain routing scheme (EBRP) and cluster based routing (TSCHS), which shows the significant improvements in minimizing the delay and energy utilization and maximizing the network lifetime and throughput with respect to these works.
A Minimax Distortion View of Differentially Private Query Release
Venue: arXiv cs.CR 2014
Year: 2014

We consider the problem of differentially private query release through a synthetic database approach. Departing from the existing approaches that require the query set to be specified in advance, we advocate to devise query-set independent mechanisms, with an ambitious goal of providing accurate answers, while meeting the privacy constraints, for all queries in a general query class. Specifically, a differentially private mechanism is constructed to "encode" rich stochastic structure into the synthetic database, and "customized" companion estimators are then derived to provide accurate answers by making use of all available information, including the mechanism (which is public information) and the query functions. Accordingly, the distortion under the best of this kind of mechanisms at the worst-case query in a general query class, so called the minimax distortion, provides a fundamental characterization of differentially private query release. For the general class of statistical queries, we prove that with the squared-error distortion measure, the minimax distortion is $O(1/n)$ by deriving asymptotically tight upper and lower bounds in the regime that the database size $n$ goes to infinity. The upper bound is achievable by a mechanism $\mathcal{E}$ and its corresponding companion estimators, which points directly to the feasibility of the proposed approach in large databases. We further evaluate the mechanism $\mathcal{E}$ and the companion estimators through experiments on real datasets from Netflix and Facebook. Experimental results show improvement over the state-of-art MWEM algorithm and verify the scaling behavior $O(1/n)$ of the minimax distortion.
Censorship in the Wild: Analyzing Internet Filtering in Syria
Venue: arXiv cs.CY 2014
Year: 2014

Internet censorship is enforced by numerous governments worldwide, however, due to the lack of publicly available information, as well as the inherent risks of performing active measurements, it is often hard for the research community to investigate censorship practices in the wild. Thus, the leak of 600GB worth of logs from 7 Blue Coat SG-9000 proxies, deployed in Syria to filter Internet traffic at a country scale, represents a unique opportunity to provide a detailed snapshot of a real-world censorship ecosystem. This paper presents the methodology and the results of a measurement analysis of the leaked Blue Coat logs, revealing a relatively stealthy, yet quite targeted, censorship. We find that traffic is filtered in several ways: using IP addresses and domain names to block subnets or websites, and keywords or categories to target specific content. We show that keyword-based censorship produces some collateral damage as many requests are blocked even if they do not relate to sensitive content. We also discover that Instant Messaging is heavily censored, while filtering of social media is limited to specific pages. Finally, we show that Syrian users try to evade censorship by using web/socks proxies, Tor, VPNs, and BitTorrent. To the best of our knowledge, our work provides the first analytical look into Internet filtering in Syria.
Periodic configurations of subshifts on groups
Venue: arXiv cs.FL 2014
Year: 2014

We study the density of periodic configurations for shift spaces defined on (the Cayley graph of) a finitely generated group. We prove that in the case of a full shift on a residually finite group and in that of a group shift space on an abelian group, the periodic configurations are dense. In the one-dimensional case we prove the density for irreducible sofic shifts. In connection with this we study the surjunctivity of cellular automata and local selfmappings. Some related decision problems for shift spaces of finite type are also investigated.
Processing Succinct Matrices and Vectors
Venue: arXiv cs.DS 2014
Year: 2014

We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to MTDD_+ by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for MTDD_+-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes PSPACE$-complete, and the same problem is NP-complete for MTDD_+-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is #P-complete.
Parallel computation of echelon forms
Venue: arXiv cs.SC 2014
Year: 2014

We propose efficient parallel algorithms and implementations on shared memory architectures of LU factorization over a finite field. Compared to the corresponding numerical routines, we have identified three main difficulties specific to linear algebra over finite fields. First, the arithmetic complexity could be dominated by modular reductions. Therefore, it is mandatory to delay as much as possible these reductions while mixing fine-grain parallelizations of tiled iterative and recursive algorithms. Second, fast linear algebra variants, e.g., using Strassen-Winograd algorithm, never suffer from instability and can thus be widely used in cascade with the classical algorithms. There, trade-offs are to be made between size of blocks well suited to those fast variants or to load and communication balancing. Third, many applications over finite fields require the rank profile of the matrix (quite often rank deficient) rather than the solution to a linear system. It is thus important to design parallel algorithms that preserve and compute this rank profile. Moreover, as the rank profile is only discovered during the algorithm, block size has then to be dynamic. We propose and compare several block decomposition: tile iterative with left-looking, right-looking and Crout variants, slab and tile recursive. Experiments demonstrate that the tile recursive variant performs better and matches the performance of reference numerical software when no rank deficiency occur. Furthermore, even in the most heterogeneous case, namely when all pivot blocks are rank deficient, we show that it is possbile to maintain a high efficiency.
Zero-Determinant Strategies in the Iterated Public Goods Game
Venue: arXiv cs.GT 2014
Year: 2014

Recently, Press and Dyson have proposed a new class of probabilistic and conditional strategies for the two-player iterated Prisoner's Dilemma, so-called zero-determinant strategies. A player adopting zero-determinant strategies is able to pin the expected payoff of the opponents or to enforce a linear relationship between his own payoff and the opponents' payoff, in a unilateral way. This paper considers zero-determinant strategies in the iterated public goods game, a representative multi-player evolutionary game where in each round each player will choose whether or not put his tokens into a public pot, and the tokens in this pot are multiplied by a factor larger than one and then evenly divided among all players. The analytical and numerical results exhibit a similar yet different scenario to the case of two-player games: (i) with small number of players or a small multiplication factor, a player is able to unilaterally pin the expected total payoff of all other players; (ii) a player is able to set the ratio between his payoff and the total payoff of all other players, but this ratio is limited by an upper bound if the multiplication factor exceeds a threshold that depends on the number of players.
Representative Families: A Unified Tradeoff-Based Approach
Venue: arXiv cs.DS 2014
Year: 2014

Let $M=(E,{\cal I})$ be a matroid, and let $\cal S$ be a family of subsets of size $p$ of $E$. A subfamily $\widehat{\cal S}\subseteq{\cal S}$ represents ${\cal S}$ if for every pair of sets $X\in{\cal S}$ and $Y\subseteq E\setminus X$ such that $X\cup Y\in{\cal I}$, there is a set $\widehat{X}\in\widehat{\cal S}$ disjoint from $Y$ such that $\widehat{X}\cup Y\in{\cal I}$. Fomin et al. (Proc. ACM-SIAM Symposium on Discrete Algorithms, 2014) introduced a powerful technique for fast computation of representative families for uniform matroids. In this paper, we show that this technique leads to a unified approach for substantially improving the running times of parameterized algorithms for some classic problems. This includes, among others, $k$-Partial Cover, $k$-Internal Out-Branching, and Long Directed Cycle. Our approach exploits an interesting tradeoff between running time and the size of the representative families.
Characterizing Workload of Web Applications on Virtualized Servers
Venue: arXiv cs.PF 2014
Year: 2014

With the ever increasing demands of cloud computing services, planning and management of cloud resources has become a more and more important issue which directed affects the resource utilization and SLA and customer satisfaction. But before any management strategy is made, a good understanding of applications' workload in virtualized environment is the basic fact and principle to the resource management methods. Unfortunately, little work has been focused on this area. Lack of raw data could be one reason; another reason is that people still use the traditional models or methods shared under non-virtualized environment. The study of applications' workload in virtualized environment should take on some of its peculiar features comparing to the non-virtualized environment. In this paper, we are open to analyze the workload demands that reflect applications' behavior and the impact of virtualization. The results are obtained from an experimental cloud testbed running web applications, specifically the RUBiS benchmark application. We profile the workload dynamics on both virtualized and non-virtualized environments and compare the findings. The experimental results are valuable for us to estimate the performance of applications on computer architectures, to predict SLA compliance or violation based on the projected application workload and to guide the decision making to support applications with the right hardware.
Dynamic Matching Market Design
Venue: arXiv cs.GT 2014
Year: 2014

We introduce a simple benchmark model of dynamic matching in networked markets, where agents arrive and depart stochastically and the network of acceptable transactions among agents forms a random graph. We analyze our model from three perspectives: waiting, optimization, and information. The main insight of our analysis is that waiting to thicken the market can be substantially more important than increasing the speed of transactions, and this is quite robust to the presence of waiting costs. From an optimization perspective, naive local algorithms, that choose the right time to match agents but do not exploit global network structure, can perform very close to optimal algorithms. From an information perspective, algorithms that employ even partial information on agents' departure times perform substantially better than those that lack such information. To elicit agents' departure times, we design an incentive-compatible continuous-time dynamic mechanism without transfers.
Auto Spell Suggestion for High Quality Speech Synthesis in Hindi
Venue: arXiv cs.CL 2014
Year: 2014

The goal of Text-to-Speech (TTS) synthesis in a particular language is to convert arbitrary input text to intelligible and natural sounding speech. However, for a particular language like Hindi, which is a highly confusing language (due to very close spellings), it is not an easy task to identify errors/mistakes in input text and an incorrect text degrade the quality of output speech hence this paper is a contribution to the development of high quality speech synthesis with the involvement of Spellchecker which generates spell suggestions for misspelled words automatically. Involvement of spellchecker would increase the efficiency of speech synthesis by providing spell suggestions for incorrect input text. Furthermore, we have provided the comparative study for evaluating the resultant effect on to phonetic text by adding spellchecker on to input text.
Evaluating ECG Capturing Using Sound-Card of PC/Laptop
Venue: arXiv cs.OH 2014
Year: 2014

The purpose of the Evaluating ECG capturing using sound-card of PC/Laptop is provided portable and low cost ECG monitoring system using laptop and mobile phones. There is no need to interface micro controller or any other device to transmit ECG data. This research is based on hardware design, implementation, signal capturing and Evaluation of an ECG processing and analyzing system which attend the physicians in heart disease diagnosis. Some important modification is given in design part to avoid all definitive ECG instrument problems faced in previous designs. Moreover, attenuate power frequency noise and noise that produces from patient's body have required additional developments. The hardware design has basically three units: transduction and conditioning Unit, interfacing unit and data processing unit.The most focusing factor is the ECG signal/data transmits in laptop/PC via microphone pin. The live simulation is possible using SOUNDSCOPE software in PC/Laptop. The software program that is written in MATLAB and LAB-View performs data acquisition (record, stored, filtration) and several tasks such as QRS detection, calculate heart rate.
Parameter estimation based on interval-valued belief structures
Venue: arXiv cs.AI 2014
Year: 2014

Parameter estimation based on uncertain data represented as belief structures is one of the latest problems in the Dempster-Shafer theory. In this paper, a novel method is proposed for the parameter estimation in the case where belief structures are uncertain and represented as interval-valued belief structures. Within our proposed method, the maximization of likelihood criterion and minimization of estimated parameter's uncertainty are taken into consideration simultaneously. As an illustration, the proposed method is employed to estimate parameters for deterministic and uncertain belief structures, which demonstrates its effectiveness and versatility.
Best of Two Local Models: Local Centralized and Local Distributed Algorithms
Venue: arXiv cs.DS 2014
Year: 2014

We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in $\log^* n$, where $n$ is the number of vertices of the input graph. The recursive centralized local improvement technique by Nguyen and Onak~\cite{onak2008} is employed to obtain an improved distributed approximation scheme for maximum (weighted) matching. The improvement is twofold: we reduce the number of rounds from $O(\log n)$ to $O(\log^*n)$ for a wide range of instances and, our algorithms are deterministic rather than randomized.