OpenRaiser/Intern-Atlas huggingface dataset:
Greedy Adaptive Compression in Signal-Plus-Noise Models
Venue: arXiv cs.IT 2012
Year: 2012

The purpose of this article is to examine the greedy adaptive measurement policy in the context of a linear Guassian measurement model with an optimization criterion based on information gain. In the special case of sequential scalar measurements, we provide sufficient conditions under which the greedy policy actually is optimal in the sense of maximizing the net information gain. In the general setting, we also discuss cases where the greedy policy is not optimal.
U-Note: Capture the Class and Access it Everywhere
Venue: arXiv cs.HC 2012
Year: 2012

We present U-Note, an augmented teaching and learning system leveraging the advantages of paper while letting teachers and pupils benefit from the richness that digital media can bring to a lecture. U-Note provides automatic linking between the notes of the pupils' notebooks and various events that occurred during the class (such as opening digital documents, changing slides, writing text on an interactive whiteboard...). Pupils can thus explore their notes in conjunction with the digital documents that were presented by the teacher during the lesson. Additionally, they can also listen to what the teacher was saying when a given note was written. Finally, they can add their own comments and documents to their notebooks to extend their lecture notes. We interviewed teachers and deployed questionnaires to identify both teachers and pupils' habits: most of the teachers use (or would like to use) digital documents in their lectures but have problems in sharing these resources with their pupils. The results of this study also show that paper remains the primary medium used for knowledge keeping, sharing and editing by the pupils. Based on these observations, we designed U-Note, which is built on three modules. U-Teach captures the context of the class: audio recordings, the whiteboard contents, together with the web pages, videos and slideshows displayed during the lesson. U-Study binds pupils' paper notes (taken with an Anoto digital pen) with the data coming from U-Teach and lets pupils access the class materials at home, through their notebooks. U-Move lets pupils browse lecture materials on their smartphone when they are not in front of a computer.
Many-Task Computing and Blue Waters
Venue: arXiv cs.DC 2012
Year: 2012

This report discusses many-task computing (MTC) generically and in the context of the proposed Blue Waters systems, which is planned to be the largest NSF-funded supercomputer when it begins production use in 2012. The aim of this report is to inform the BW project about MTC, including understanding aspects of MTC applications that can be used to characterize the domain and understanding the implications of these aspects to middleware and policies. Many MTC applications do not neatly fit the stereotypes of high-performance computing (HPC) or high-throughput computing (HTC) applications. Like HTC applications, by definition MTC applications are structured as graphs of discrete tasks, with explicit input and output dependencies forming the graph edges. However, MTC applications have significant features that distinguish them from typical HTC applications. In particular, different engineering constraints for hardware and software must be met in order to support these applications. HTC applications have traditionally run on platforms such as grids and clusters, through either workflow systems or parallel programming systems. MTC applications, in contrast, will often demand a short time to solution, may be communication intensive or data intensive, and may comprise very short tasks. Therefore, hardware and software for MTC must be engineered to support the additional communication and I/O and must minimize task dispatch overheads. The hardware of large-scale HPC systems, with its high degree of parallelism and support for intensive communication, is well suited for MTC applications. However, HPC systems often lack a dynamic resource-provisioning feature, are not ideal for task communication via the file system, and have an I/O system that is not optimized for MTC-style applications. Hence, additional software support is likely to be required to gain full benefit from the HPC hardware.
A versatile and accurate approximation for LRU cache performance
Venue: arXiv cs.NI 2012
Year: 2012

In a 2002 paper, Che and co-authors proposed a simple approach for estimating the hit rates of a cache operating the least recently used (LRU) replacement policy. The approximation proves remarkably accurate and is applicable to quite general distributions of object popularity. This paper provides a mathematical explanation for the success of the approximation, notably in configurations where the intuitive arguments of Che, et al clearly do not apply. The approximation is particularly useful in evaluating the performance of current proposals for an information centric network where other approaches fail due to the very large populations of cacheable objects to be taken into account and to their complex popularity law, resulting from the mix of different content types and the filtering effect induced by the lower layers in a cache hierarchy.
Beyond the Blacklist: Modeling Malware Spread and the Effect of Interventions
Venue: arXiv cs.CR 2012
Year: 2012

Malware spread among websites and between websites and clients is an increasing problem. Search engines play an important role in directing users to websites and are a natural control point for intervening, using mechanisms such as blacklisting. The paper presents a simple Markov model of malware spread through large populations of websites and studies the effect of two interventions that might be deployed by a search provider: blacklisting infected web pages by removing them from search results entirely and a generalization of blacklisting, called depreferencing, in which a website's ranking is decreased by a fixed percentage each time period the site remains infected. We analyze and study the trade-offs between infection exposure and traffic loss due to false positives (the cost to a website that is incorrectly blacklisted) for different interventions. As expected, we find that interventions are most effective when websites are slow to remove infections. Surprisingly, we also find that low infection or recovery rates can increase traffic loss due to false positives. Our analysis also shows that heavy-tailed distributions of website popularity, as documented in many studies, leads to high sample variance of all measured outcomes. These result implies that it will be difficult to determine empirically whether certain website interventions are effective, and it suggests that theoretical models such as the one described in this paper have an important role to play in improving web security.
Generalized selfish bin packing
Venue: arXiv cs.GT 2012
Year: 2012

Standard bin packing is the problem of partitioning a set of items with positive sizes no larger than 1 into a minimum number of subsets (called bins) each having a total size of at most 1. In bin packing games, an item has a positive weight, and given a valid packing or partition of the items, each item has a cost or a payoff associated with it. We study a class of bin packing games where the payoff of an item is the ratio between its weight and the total weight of items packed with it, that is, the cost sharing is based linearly on the weights of items. We study several types of pure Nash equilibria: standard Nash equilibria, strong equilibria, strictly Pareto optimal equilibria, and weakly Pareto optimal equilibria. We show that any game of this class admits all these types of equilibria. We study the (asymptotic) prices of anarchy and stability (PoA and PoS) of the problem with respect to these four types of equilibria, for the two cases of general weights and of unit weights. We show that while the case of general weights is strongly related to the well-known First Fit algorithm, and all the four PoA values are equal to 1.7, this is not true for unit weights. In particular, we show that all of them are strictly below 1.7, the strong PoA is equal to approximately 1.691 (another well-known number in bin packing) while the strictly Pareto optimal PoA is much lower. We show that all the PoS values are equal to 1, except for those of strong equilibria, which is equal to 1.7 for general weights, and to approximately 1.611824 for unit weights. This last value is not known to be the (asymptotic) approximation ratio of any well-known algorithm for bin packing. Finally, we study convergence to equilibria.
Generalized FMD Detection for Spectrum Sensing Under Low Signal-to-Noise Ratio
Venue: arXiv cs.AI 2012
Year: 2012

Spectrum sensing is a fundamental problem in cognitive radio. We propose a function of covariance matrix based detection algorithm for spectrum sensing in cognitive radio network. Monotonically increasing property of function of matrix involving trace operation is utilized as the cornerstone for this algorithm. The advantage of proposed algorithm is it works under extremely low signal-to-noise ratio, like lower than -30 dB with limited sample data. Theoretical analysis of threshold setting for the algorithm is discussed. A performance comparison between the proposed algorithm and other state-of-the-art methods is provided, by the simulation on captured digital television (DTV) signal.
Boundary Conditions of Subharmonic Oscillations in Fixed-Switching-Frequency DC-DC Converters
Venue: arXiv cs.SY 2012
Year: 2012

Design-oriented boundary conditions for subharmonic oscillations are of great interest recently. Based on a subharmonic oscillation boundary condition reported in a PhD thesis more than a decade ago, extended new boundary conditions are derived in closed forms for general switching DC-DC converters. Sampled-data and harmonic balance analyses are applied and generate equivalent results. It is shown that equivalent series resistance causes the boundary conditions for voltage/current mode control to have similar forms. Some recently reported boundary conditions become special cases in view of the general boundary conditions derived. New Nyquist-like design-oriented plots are proposed to predict or prevent the occurrence of the subharmonic oscillation. The relation between the crossover frequency and the subharmonic oscillation is also analyzed.
A Simple Unsupervised Color Image Segmentation Method based on MRF-MAP
Venue: arXiv cs.CV 2012
Year: 2012

Color image segmentation is an important topic in the image processing field. MRF-MAP is often adopted in the unsupervised segmentation methods, but their performance are far behind recent interactive segmentation tools supervised by user inputs. Furthermore, the existing related unsupervised methods also suffer from the low efficiency, and high risk of being trapped in the local optima, because MRF-MAP is currently solved by iterative frameworks with inaccurate initial color distribution models. To address these problems, the letter designs an efficient method to calculate the energy functions approximately in the non-iteration style, and proposes a new binary segmentation algorithm based on the slightly tuned Lanczos eigensolver. The experiments demonstrate that the new algorithm achieves competitive performance compared with two state-of-art segmentation methods.
A Frequency Domain Steganography using Z Transform (FDSZT)
Venue: arXiv cs.CR 2012
Year: 2012

Image steganography is art of hiding information onto the cover image. In this proposal a transformed domain based gray scale image authentication/data hiding technique using Z transform (ZT) termed as FDSZT, has been proposed. ZTransform is applied on 2x2 masks of the source image in row major order to transform original sub image (cover image) block to its corresponding frequency domain. One bit of the hidden image is embedded in each mask of the source image onto the fourth LSB of transformed coefficient based on median value of the mask. A delicate handle has also been performed as post embedding operation for proper decoding. Stego sub image is obtained through a reverse transform as final step of embedding in a mask. During the process of embedding, dimension of the hidden image followed by the content of the message/hidden image are embedded. Reverse process is followed during decoding. High PSNR obtained for various images conform the quality of invisible watermark of FDSZT.
Live-Musikprogrammierung in Haskell
Venue: arXiv cs.PL 2012
Year: 2012

We aim to compose algorithmic music in an interactive way with multiple participants. To this end we develop an interpreter for a sub-language of the non-strict functional programming language Haskell that allows to modify the program during its execution. Our system can be used both for musical live-coding and for demonstration and education of functional programming.
Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games
Venue: arXiv cs.GT 2012
Year: 2012

We study coordination mechanisms for Scheduling Games (with unrelated machines). In these games, each job represents a player, who needs to choose a machine for its execution, and intends to complete earliest possible. Our goal is to design scheduling policies that always admit a pure Nash equilibrium and guarantee a small price of anarchy for the l_k-norm social cost --- the objective balances overall quality of service and fairness. We consider policies with different amount of knowledge about jobs: non-clairvoyant, strongly-local and local. The analysis relies on the smooth argument together with adequate inequalities, called smooth inequalities. With this unified framework, we are able to prove the following results. First, we study the inefficiency in l_k-norm social costs of a strongly-local policy SPT and a non-clairvoyant policy EQUI. We show that the price of anarchy of policy SPT is O(k). We also prove a lower bound of Omega(k/log k) for all deterministic, non-preemptive, strongly-local and non-waiting policies (non-waiting policies produce schedules without idle times). These results ensure that SPT is close to optimal with respect to the class of l_k-norm social costs. Moreover, we prove that the non-clairvoyant policy EQUI has price of anarchy O(2^k). Second, we consider the makespan (l_infty-norm) social cost by making connection within the l_k-norm functions. We revisit some local policies and provide simpler, unified proofs from the framework's point of view. With the highlight of the approach, we derive a local policy Balance. This policy guarantees a price of anarchy of O(log m), which makes it the currently best known policy among the anonymous local policies that always admit a pure Nash equilibrium.
The Secure Generation of RSA Moduli Using Poor RNG
Venue: arXiv cs.CR 2012
Year: 2012

We discuss a procedure, which should be called Lenstra's fix, for producing secure RSA moduli even when the random number generation is very poor.
Relay Channel with Orthogonal Components and Structured Interference Known at the Source
Venue: arXiv cs.IT 2012
Year: 2012

A relay channel with orthogonal components that is affected by an interference signal that is noncausally available only at the source is studied. The interference signal has structure in that it is produced by another transmitter communicating with its own destination. Moreover, the interferer is not willing to adjust its communication strategy to minimize the interference. Knowledge of the interferer's signal may be acquired by the source, for instance, by exploiting HARQ retransmissions on the interferer's link. The source can then utilize the relay not only for communicating its own message, but also for cooperative interference mitigation at the destination by informing the relay about the interference signal. Proposed transmission strategies are based on partial decode-and-forward (PDF) relaying and leverage the interference structure. Achievable schemes are derived for discrete memoryless models, Gaussian and Ricean fading channels. Furthermore, optimal strategies are identified in some special cases. Finally, numerical results bring insight into the advantages of utilizing the interference structure at the source, relay or destination.
Wireless Peer-to-Peer Scheduling in Mobile Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper considers peer-to-peer scheduling for a network with multiple wireless devices. A subset of the devices are mobile users that desire specific files. Each user may already have certain popular files in its cache. The remaining devices are access points that typically have access to a larger set of files. Users can download packets of their requested file from an access point or from a nearby user. Our prior work optimizes peer scheduling in a general setting, but the resulting delay can be large when applied to mobile networks. This paper focuses on the mobile case, and develops a new algorithm that reduces delay by opportunistically grabbing packets from current neighbors. However, it treats a simpler model where each user desires a single file with infinite length. An algorithm that provably optimizes throughput utility while incentivizing participation is developed for this case. The algorithm extends as a simple heuristic in more general cases with finite file sizes and random active and idle periods.
The best of both worlds: stochastic and adversarial bandits
Venue: arXiv cs.LG 2012
Year: 2012

We present a new bandit algorithm, SAO (Stochastic and Adversarial Optimal), whose regret is, essentially, optimal both for adversarial rewards and for stochastic rewards. Specifically, SAO combines the square-root worst-case regret of Exp3 (Auer et al., SIAM J. on Computing 2002) and the (poly)logarithmic regret of UCB1 (Auer et al., Machine Learning 2002) for stochastic rewards. Adversarial rewards and stochastic rewards are the two main settings in the literature on (non-Bayesian) multi-armed bandits. Prior work on multi-armed bandits treats them separately, and does not attempt to jointly optimize for both. Our result falls into a general theme of achieving good worst-case performance while also taking advantage of "nice" problem instances, an important issue in the design of algorithms with partially known inputs.
(weak) Calibration is Computationally Hard
Venue: arXiv cs.GT 2012
Year: 2012

We show that the existence of a computationally efficient calibration algorithm, with a low weak calibration rate, would imply the existence of an efficient algorithm for computing approximate Nash equilibria - thus implying the unlikely conclusion that every problem in PPAD is solvable in polynomial time.
Sampled-Data and Harmonic Balance Analyses of Average Current-Mode Controlled Buck Converter
Venue: arXiv cs.SY 2012
Year: 2012

Dynamics and stability of average current-mode control of buck converters are analyzed by sampled-data and harmonic balance analyses. An exact sampled-data model is derived. A new continuous-time model "lifted" from the sampled-data model is also derived, and has frequency response matched with experimental data reported previously. Orbital stability is studied and it is found unrelated to the ripple size of the current-loop compensator output. An unstable window of the current-loop compensator pole is found by simulations, and it can be accurately predicted by sampled-data and harmonic balance analyses. A new S plot accurately predicting the subharmonic oscillation is proposed. The S plot assists pole assignment and shows the required ramp slope to avoid instability.
Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
Venue: arXiv cs.DS 2012
Year: 2012

In spite of the extensive studies of the 3-coloring problem with respect to several basic parameters, the complexity status of the 3-coloring problem on graphs with small diameter, i.e. with diameter 2 or 3, has been a longstanding and challenging open question. For graphs with diameter 2 we provide the first subexponential algorithm with complexity $2^{O(\sqrt{n\log n})}$, which is asymptotically the same as the currently best known time complexity for the graph isomorphism (GI) problem. Moreover, we prove that the graph isomorphism problem on 3-colorable graphs with diameter 2 is GI-complete. Furthermore we present a subclass of graphs with diameter 2 that admits a polynomial algorithm for 3-coloring. For graphs with diameter 3 we establish the complexity of 3-coloring by proving that for every $\varepsilon \in [0,1)$, 3-coloring is NP-complete on triangle-free graphs of diameter 3 and radius 2 with $n$ vertices and minimum degree $δ=Θ(n^{\varepsilon})$. Moreover, assuming ETH, we provide three different amplifications of our hardness results to obtain for every $\varepsilon \in [0,1)$ subexponential lower bounds for the complexity of 3-coloring on triangle-free graphs with diameter 3 and minimum degree $δ=Θ(n^{\varepsilon})$. Finally, we provide a 3-coloring algorithm with running time $2^{O(\min\{δΔ,\frac{n}δ\logδ\})}$ for graphs with diameter 3, where $δ$ (resp. $Δ$) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this algorithm is the first subexponential algorithm for graphs with $δ=ω(1)$ and for graphs with $δ=O(1)$ and $Δ=o(n)$. Due to the above lower bounds of the complexity of 3-coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree if the input graph is $δ=Θ(n^{\varepsilon})$, where $\varepsilon \in [1/2,1)$.
A Categorical Model for the Lambda Calculus with Constructors
Venue: arXiv cs.LO 2012
Year: 2012

The lambda calculus with constructors is an extension of the lambda calculus with variadic constructors. It decomposes the pattern-matching a la ML into a case analysis on constants and a commutation rule between case and application constructs. Although this commutation rule does not match with the usual computing intuitions, it makes the calculus expressive and confluent, with a rather simple syntax. In this paper we define a sound notion of categorical model for the lambda calculus with constructors. We then prove that this definition is complete for the fragment of the calculus with no match-failure, using the model of partial equivalence relations.
Take it or Leave it: Running a Survey when Privacy Comes at a Cost
Venue: arXiv cs.GT 2012
Year: 2012

In this paper, we consider the problem of estimating a potentially sensitive (individually stigmatizing) statistic on a population. In our model, individuals are concerned about their privacy, and experience some cost as a function of their privacy loss. Nevertheless, they would be willing to participate in the survey if they were compensated for their privacy cost. These cost functions are not publicly known, however, nor do we make Bayesian assumptions about their form or distribution. Individuals are rational and will misreport their costs for privacy if doing so is in their best interest. Ghosh and Roth recently showed in this setting, when costs for privacy loss may be correlated with private types, if individuals value differential privacy, no individually rational direct revelation mechanism can compute any non-trivial estimate of the population statistic. In this paper, we circumvent this impossibility result by proposing a modified notion of how individuals experience cost as a function of their privacy loss, and by giving a mechanism which does not operate by direct revelation. Instead, our mechanism has the ability to randomly approach individuals from a population and offer them a take-it-or-leave-it offer. This is intended to model the abilities of a surveyor who may stand on a street corner and approach passers-by.