OpenRaiser/Intern-Atlas huggingface dataset:
At Low SNR Asymmetric Quantizers Are Better
Venue: arXiv cs.IT 2013
Year: 2013

We study the capacity of the discrete-time Gaussian channel when its output is quantized with a one-bit quantizer. We focus on the low signal-to-noise ratio (SNR) regime, where communication at very low spectral efficiencies takes place. In this regime a symmetric threshold quantizer is known to reduce channel capacity by a factor of 2/pi, i.e., to cause an asymptotic power loss of approximately two decibels. Here it is shown that this power loss can be avoided by using asymmetric threshold quantizers and asymmetric signaling constellations. To avoid this power loss, flash-signaling input distributions are essential. Consequently, one-bit output quantization of the Gaussian channel reduces spectral efficiency. Threshold quantizers are not only asymptotically optimal: at every fixed SNR a threshold quantizer maximizes capacity among all one-bit output quantizers. The picture changes on the Rayleigh-fading channel. In the noncoherent case a one-bit output quantizer causes an unavoidable low-SNR asymptotic power loss. In the coherent case, however, this power loss is avoidable provided that we allow the quantizer to depend on the fading level.
A PSPACE-Complete First Order Fragment of Computability Logic
Venue: arXiv cs.LO 2013
Year: 2013

In a recently launched research program for developing logic as a formal theory of (interactive) computability, several very interesting logics have been introduced and axiomatized. These fragments of the larger Computability Logic aim not only to describe "what" can be computed, but also provide a mechanism for extracting computational algorithms from proofs. Among the most expressive and fundamental of these is CL4, known to be (constructively) sound and complete with respect to the underlying computational semantics. Furthermore, the fragment of CL4 not containing blind quantifiers was shown to be decidable in polynomial space. The present work extends this result and proves that this fragment is, in fact, PSPACE-complete.
Gaming is a hard job, but someone has to do it!
Venue: arXiv cs.CC 2013
Year: 2013

We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Then we apply such "metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble~3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.
An Efficient Primal-Dual Prox Method for Non-Smooth Optimization
Venue: arXiv cs.LG 2013
Year: 2013

We study the non-smooth optimization problems in machine learning, where both the loss function and the regularizer are non-smooth functions. Previous studies on efficient empirical loss minimization assume either a smooth loss function or a strongly convex regularizer, making them unsuitable for non-smooth optimization. We develop a simple yet efficient method for a family of non-smooth optimization problems where the dual form of the loss function is bilinear in primal and dual variables. We cast a non-smooth optimization problem into a minimax optimization problem, and develop a primal dual prox method that solves the minimax optimization problem at a rate of $O(1/T)$ {assuming that the proximal step can be efficiently solved}, significantly faster than a standard subgradient descent method that has an $O(1/\sqrt{T})$ convergence rate. Our empirical study verifies the efficiency of the proposed method for various non-smooth optimization problems that arise ubiquitously in machine learning by comparing it to the state-of-the-art first order methods.
Tree-Automatic Well-Founded Trees
Venue: arXiv cs.LO 2013
Year: 2013

We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega^omega. Moreover, we make a step towards proving that the ranks of tree-automatic well-founded partial orders are bounded by omega^omega^omega: we prove this bound for what we call upwards linear partial orders. As an application of our result, we show that the isomorphism problem for tree-automatic well-founded trees is complete for level Delta^0_{omega^omega} of the hyperarithmetical hierarchy with respect to Turing-reductions.
Non-Random Coding Error Exponent for Lattices
Venue: arXiv cs.IT 2013
Year: 2013

An upper bound on the error probability of specific lattices, based on their distance-spectrum, is constructed. The derivation is accomplished using a simple alternative to the Minkowski-Hlawka mean-value theorem of the geometry of numbers. In many ways, the new bound greatly resembles the Shulman-Feder bound for linear codes. Based on the new bound, an error-exponent is derived for specific lattice sequences (of increasing dimension) over the AWGN channel. Measuring the sequence's gap to capacity, using the new exponent, is demonstrated.
Error-Correction in Flash Memories via Codes in the Ulam Metric
Venue: arXiv cs.IT 2013
Year: 2013

We consider rank modulation codes for flash memories that allow for handling arbitrary charge-drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed \emph{translocation rank codes} account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include derivation of the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes for permutations, and permutation codes in the Hamming distance.
A quantum genetic algorithm with quantum crossover and mutation operations
Venue: arXiv cs.NE 2013
Year: 2013

In the context of evolutionary quantum computing in the literal meaning, a quantum crossover operation has not been introduced so far. Here, we introduce a novel quantum genetic algorithm which has a quantum crossover procedure performing crossovers among all chromosomes in parallel for each generation. A complexity analysis shows that a quadratic speedup is achieved over its classical counterpart in the dominant factor of the run time to handle each generation.
Adaptively Sharing Time-Series with Differential Privacy
Venue: arXiv cs.DB 2013
Year: 2013

Sharing real-time aggregate statistics of private data is of great value to the public to perform data mining for understanding important phenomena, such as Influenza outbreaks and traffic congestion. However, releasing time-series data with standard differential privacy mechanism has limited utility due to high correlation between data values. We propose FAST, a novel framework to release real-time aggregate statistics under differential privacy based on filtering and adaptive sampling. To minimize the overall privacy cost, FAST adaptively samples long time-series according to the detected data dynamics. To improve the accuracy of data release per time stamp, FAST predicts data values at non-sampling points and corrects noisy observations at sampling points. Our experiments with real-world as well as synthetic data sets confirm that FAST improves the accuracy of released aggregates even under small privacy cost and can be used to enable a wide range of monitoring applications.
Finding a most biased coin with fewest flips
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of learning a most biased coin among a set of coins by tossing the coins adaptively. The goal is to minimize the number of tosses until we identify a coin i* whose posterior probability of being most biased is at least 1-delta for a given delta. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy -- a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs tools from the field of Markov games.
A Regularized Graph Layout Framework for Dynamic Network Visualization
Venue: arXiv cs.SI 2013
Year: 2013

Many real-world networks, including social and information networks, are dynamic structures that evolve over time. Such dynamic networks are typically visualized using a sequence of static graph layouts. In addition to providing a visual representation of the network structure at each time step, the sequence should preserve the mental map between layouts of consecutive time steps to allow a human to interpret the temporal evolution of the network. In this paper, we propose a framework for dynamic network visualization in the on-line setting where only present and past graph snapshots are available to create the present layout. The proposed framework creates regularized graph layouts by augmenting the cost function of a static graph layout algorithm with a grouping penalty, which discourages nodes from deviating too far from other nodes belonging to the same group, and a temporal penalty, which discourages large node movements between consecutive time steps. The penalties increase the stability of the layout sequence, thus preserving the mental map. We introduce two dynamic layout algorithms within the proposed framework, namely dynamic multidimensional scaling (DMDS) and dynamic graph Laplacian layout (DGLL). We apply these algorithms on several data sets to illustrate the importance of both grouping and temporal regularization for producing interpretable visualizations of dynamic networks.
High Volume Computing: Identifying and Characterizing Throughput Oriented Workloads in Data Centers
Venue: arXiv cs.DC 2013
Year: 2013

For the first time, this paper systematically identifies three categories of throughput oriented workloads in data centers: services, data processing applications, and interactive real-time applications, whose targets are to increase the volume of throughput in terms of processed requests or data, or supported maximum number of simultaneous subscribers, respectively, and we coin a new term high volume computing (in short HVC) to describe those workloads and data center computer systems designed for them. We characterize and compare HVC with other computing paradigms, e.g., high throughput computing, warehouse-scale computing, and cloud computing, in terms of levels, workloads, metrics, coupling degree, data scales, and number of jobs or service instances. We also preliminarily report our ongoing work on the metrics and benchmarks for HVC systems, which is the foundation of designing innovative data center computer systems for HVC workloads.
Innovation as a Nonlinear Process, the Scientometric Perspective, and the Specification of an "Innovation Opportunities Explorer"
Venue: arXiv cs.DL 2013
Year: 2013

The process of innovation follows non-linear patterns across the domains of science, technology, and the economy. Novel bibliometric mapping techniques can be used to investigate and represent distinctive, but complementary perspectives on the innovation process (e.g., "demand" and "supply") as well as the interactions among these perspectives. The perspectives can be represented as "continents" of data related to varying extents over time. For example, the different branches of Medical Subject Headings (MeSH) in the Medline database provide sources of such perspectives (e.g., "Diseases" versus "Drugs and Chemicals"). The multiple-perspective approach enables us to reconstruct facets of the dynamics of innovation, in terms of selection mechanisms shaping localizable trajectories and/or resulting in more globalized regimes. By expanding the data with patents and scholarly publications, we demonstrate the use of this multi-perspective approach in the case of RNA Interference (RNAi). The possibility to develop an "Innovation Opportunities Explorer" is specified.
Dictionary learning under global sparsity constraint
Venue: arXiv cs.DS 2013
Year: 2013

A new method is proposed in this paper to learn overcomplete dictionary from training data samples. Differing from the current methods that enforce similar sparsity constraint on each of the input samples, the proposed method attempts to impose global sparsity constraint on the entire data set. This enables the proposed method to fittingly assign the atoms of the dictionary to represent various samples and optimally adapt to the complicated structures underlying the entire data set. By virtue of the sparse coding and sparse PCA techniques, a simple algorithm is designed for the implementation of the method. The efficiency and the convergence of the proposed algorithm are also theoretically analyzed. Based on the experimental results implemented on a series of signal and image data sets, it is apparent that our method performs better than the current dictionary learning methods in original dictionary recovering, input data reconstructing, and salient data structure revealing.
Undominated Groves Mechanisms
Venue: arXiv cs.GT 2013
Year: 2013

The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally not budget balanced. That is, under such mechanisms, payments may flow into or out of the system of the agents, resulting in deficits or reduced utilities for the agents. We consider the following problem: within the family of Groves mechanisms, we want to identify mechanisms that give the agents the highest utilities, under the constraint that these mechanisms must never incur deficits. We adopt a prior-free approach. We introduce two general measures for comparing mechanisms in prior-free settings. We say that a non-deficit Groves mechanism $M$ {\em individually dominates} another non-deficit Groves mechanism $M'$ if for every type profile, every agent's utility under $M$ is no less than that under $M'$, and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism $M$ {\em collectively dominates} another non-deficit Groves mechanism $M'$ if for every type profile, the agents' total utility under $M$ is no less than that under $M'$, and this holds with strict inequality for at least one type profile. The above definitions induce two partial orders on non-deficit Groves mechanisms. We study the maximal elements corresponding to these two partial orders, which we call the {\em individually undominated} mechanisms and the {\em collectively undominated} mechanisms, respectively.
Friends FTW! Friendship, Collaboration and Competition in Halo: Reach
Venue: arXiv cs.SI 2013
Year: 2013

How important are friendships in determining success by individuals and teams in complex collaborative environments? By combining a novel data set containing the dynamics of millions of ad hoc teams from the popular multiplayer online first person shooter Halo: Reach with survey data on player demographics, play style, psychometrics and friendships derived from an anonymous online survey, we investigate the impact of friendship on collaborative and competitive performance. In addition to finding significant differences in player behavior across these variables, we find that friendships exert a strong influence, leading to both improved individual and team performance--even after controlling for the overall expertise of the team--and increased pro-social behaviors. Players also structure their in-game activities around social opportunities, and as a result hidden friendship ties can be accurately inferred directly from behavioral time series. Virtual environments that enable such friendship effects will thus likely see improved collaboration and competition.
A framework for integrated design of algorithmic architectural forms
Venue: arXiv cs.CE 2013
Year: 2013

This paper presents a methodology and software tools for parametric design of complex architectural objects, called digital or algorithmic forms. In order to provide a flexible tool, the proposed design philosophy involves two open source utilities Donkey and MIDAS written in Grasshopper algorithm editor and C++, respectively, that are to be linked with a scripting-based architectural modellers Rhinoceros, IntelliCAD and the open source Finite Element solver OOFEM. The emphasis is put on the mechanical response in order to provide architects with a consistent learning framework and an insight into structural behaviour of designed objects. As demonstrated on three case studies, the proposed modular solution is capable of handling objects of considerable structural complexity, thereby accelerating the process of finding procedural design parameters from orders of weeks to days or hours.
Biclique-colouring verification complexity and biclique-colouring power graphs
Venue: arXiv cs.DS 2013
Year: 2013

Biclique-colouring is a colouring of the vertices of a graph in such a way that no maximal complete bipartite subgraph with at least one edge is monochromatic. We show that it is coNP-complete to check whether a given function that associates a colour to each vertex is a biclique-colouring, a result that justifies the search for structured classes where the biclique-colouring problem could be efficiently solved. We consider biclique-colouring restricted to powers of paths and powers of cycles. We determine the biclique-chromatic number of powers of paths and powers of cycles. The biclique-chromatic number of a power of a path P_{n}^{k} is max(2k + 2 - n, 2) if n >= k + 1 and exactly n otherwise. The biclique-chromatic number of a power of a cycle C_n^k is at most 3 if n >= 2k + 2 and exactly n otherwise; we additionally determine the powers of cycles that are 2-biclique-colourable. All proofs are algorithmic and provide polynomial-time biclique-colouring algorithms for graphs in the investigated classes.
Cognitive Wyner Networks with Clustered Decoding
Venue: arXiv cs.IT 2013
Year: 2013

We study an interference network where equally-numbered transmitters and receivers lie on two parallel lines, each transmitter opposite its intended receiver. We consider two short-range interference models: the "asymmetric network," where the signal sent by each transmitter is interfered only by the signal sent by its left neighbor (if present), and a "symmetric network," where it is interfered by both its left and its right neighbors. Each transmitter is cognizant of its own message, the messages of the $t_\ell$ transmitters to its left, and the messages of the $t_r$ transmitters to its right. Each receiver decodes its message based on the signals received at its own antenna, at the $r_\ell$ receive antennas to its left, and the $r_r$ receive antennas to its right. For such networks we provide upper and lower bounds on the multiplexing gain, i.e., on the high-SNR asymptotic logarithmic growth of the sum-rate capacity. In some cases our bounds meet, e.g., for the asymmetric network. Our results exhibit an equivalence between the transmitter side-information parameters $t_\ell, t_r$ and the receiver side-information parameters $r_\ell, r_r$ in the sense that increasing/decreasing $t_\ell$ or $t_r$ by a positive integer $δ$ has the same effect on the multiplexing gain as increasing/decreasing $r_\ell$ or $r_r$ by $δ$. Moreover---even in asymmetric networks---there is an equivalence between the left side-information parameters $t_\ell, r_\ell$ and the right side-information parameters $t_r, r_r$.
VoIP Steganography and Its Detection - A Survey
Venue: arXiv cs.CR 2013
Year: 2013

Steganography is an ancient art that encompasses various techniques of information hiding, the aim of which is to secret information into a carrier message. Steganographic methods are usually aimed at hiding the very existence of the communication. Due to the rise in popularity of IP telephony, together with the large volume of data and variety of protocols involved, it is currently attracting the attention of the research community as a perfect carrier for steganographic purposes. This paper is a survey of the existing VoIP steganography (steganophony) methods and their countermeasures.
Matrix Recipes for Hard Thresholding Methods
Venue: arXiv cs.NA 2013
Year: 2013

In this paper, we present and analyze a new set of low-rank recovery algorithms for linear inverse problems within the class of hard thresholding methods. We provide strategies on how to set up these algorithms via basic ingredients for different configurations to achieve complexity vs. accuracy tradeoffs. Moreover, we study acceleration schemes via memory-based techniques and randomized, $ε$-approximate matrix projections to decrease the computational costs in the recovery process. For most of the configurations, we present theoretical analysis that guarantees convergence under mild problem conditions. Simulation results demonstrate notable performance improvements as compared to state-of-the-art algorithms both in terms of reconstruction accuracy and computational complexity.
Data Dissemination in Wireless Networks with Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

We investigate the use of network coding for information dissemination over a wireless network. Using network coding allows for a simple, distributed and robust algorithm where nodes do not need any information from their neighbors. In this paper, we analyze the time needed to diffuse information throughout a network when network coding is implemented at all nodes. We then provide an upper bound for the dissemination time for ad-hoc networks with general topology. Moreover, we derive a relation between dissemination time and the size of the wireless network. It is shown that for a wireless network with N nodes, the dissemination latency is between O(N) and O(N^2), depending on the reception probabilities of the nodes. These observations are validated by the simulation results.
A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
Venue: arXiv cs.NA 2013
Year: 2013

A parallelization of a sweeping preconditioner for 3D Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be O(γ^2 N^{4/3}) and O(γ N log N), where γ(ω) denotes the modestly frequency-dependent number of grid points per Perfectly Matched Layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: "Parallel Sweeping Preconditioner (PSP)" and the underlying distributed multifrontal solver, "Clique".