OpenRaiser/Intern-Atlas huggingface dataset:
An Evaluation of Impacts in "Nanoscience & nanotechnology:" Steps towards standards for citation analysis
Venue: arXiv cs.DL 2012
Year: 2012

One is inclined to conceptualize impact in terms of citations per publication, and thus as an average. However, citation distributions are skewed, and the average has the disadvantage that the number of publications is used in the denominator. Using hundred percentiles, one can integrate the normalized citation curve and develop an indicator that can be compared across document sets because percentile ranks are defined at the article level. I apply this indicator to the set of 58 journals in the ISI Subject Category of "Nanoscience & nanotechnology," and rank journals, countries, cities, and institutes using non-parametric statistics. The significance levels of results can thus be indicated. The results are first compared with the ISI-Impact Factors, but this Integrated Impact Indicator (I3) can be used with any set downloaded from the (Social) Science Citation Index. The software is made publicly available at the Internet. Visualization techniques are also specified for evaluation by positioning institutes on Google Map overlays.
Whether and Where to Code in the Wireless Relay Channel
Venue: arXiv cs.NI 2012
Year: 2012

The throughput benefits of random linear network codes have been studied extensively for wirelined and wireless erasure networks. It is often assumed that all nodes within a network perform coding operations. In energy-constrained systems, however, coding subgraphs should be chosen to control the number of coding nodes while maintaining throughput. In this paper, we explore the strategic use of network coding in the wireless packet erasure relay channel according to both throughput and energy metrics. In the relay channel, a single source communicates to a single sink through the aid of a half-duplex relay. The fluid flow model is used to describe the case where both the source and the relay are coding, and Markov chain models are proposed to describe packet evolution if only the source or only the relay is coding. In addition to transmission energy, we take into account coding and reception energies. We show that coding at the relay alone while operating in a rateless fashion is neither throughput nor energy efficient. Given a set of system parameters, our analysis determines the optimal amount of time the relay should participate in the transmission, and where coding should be performed.
Wait-Freedom with Advice
Venue: arXiv cs.DC 2012
Year: 2012

We motivate and propose a new way of thinking about failure detectors which allows us to define, quite surprisingly, what it means to solve a distributed task \emph{wait-free} \emph{using a failure detector}. In our model, the system is composed of \emph{computation} processes that obtain inputs and are supposed to output in a finite number of steps and \emph{synchronization} processes that are subject to failures and can query a failure detector. We assume that, under the condition that \emph{correct} synchronization processes take sufficiently many steps, they provide the computation processes with enough \emph{advice} to solve the given task wait-free: every computation process outputs in a finite number of its own steps, regardless of the behavior of other computation processes. Every task can thus be characterized by the \emph{weakest} failure detector that allows for solving it, and we show that every such failure detector captures a form of set agreement. We then obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking.
A note on hitting maximum and maximal cliques with a stable set
Venue: arXiv cs.DM 2012
Year: 2012

It was recently proved that any graph satisfying $ω> \frac 23(Δ+1)$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying $ω\geq \frac 23(Δ+1)$ unless the graph is the strong product of $K_{ω/2}$ and an odd hole. We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.
Learning Topic Models by Belief Propagation
Venue: arXiv cs.LG 2012
Year: 2012

Latent Dirichlet allocation (LDA) is an important hierarchical Bayesian model for probabilistic topic modeling, which attracts worldwide interests and touches on many important applications in text mining, computer vision and computational biology. This paper represents LDA as a factor graph within the Markov random field (MRF) framework, which enables the classic loopy belief propagation (BP) algorithm for approximate inference and parameter estimation. Although two commonly-used approximate inference methods, such as variational Bayes (VB) and collapsed Gibbs sampling (GS), have gained great successes in learning LDA, the proposed BP is competitive in both speed and accuracy as validated by encouraging experimental results on four large-scale document data sets. Furthermore, the BP algorithm has the potential to become a generic learning scheme for variants of LDA-based topic models. To this end, we show how to learn two typical variants of LDA-based topic models, such as author-topic models (ATM) and relational topic models (RTM), using BP based on the factor graph representation.
Dependencies in Formal Mathematics: Applications and Extraction for Coq and Mizar
Venue: arXiv cs.DL 2012
Year: 2012

Two methods for extracting detailed formal dependencies from the Coq and Mizar system are presented and compared. The methods are used for dependency extraction from two large mathematical repositories: the Coq Repository at Nijmegen and the Mizar Mathematical Library. Several applications of the detailed dependency analysis are described and proposed. Motivated by the different applications, we discuss the various kinds of dependencies that we are interested in,and the suitability of various dependency extraction methods.
The Projection Method for Reaching Consensus and the Regularized Power Limit of a Stochastic Matrix
Venue: arXiv cs.MA 2012
Year: 2012

In the coordination/consensus problem for multi-agent systems, a well-known condition of achieving consensus is the presence of a spanning arborescence in the communication digraph. The paper deals with the discrete consensus problem in the case where this condition is not satisfied. A characterization of the subspace $T_P$ of initial opinions (where $P$ is the influence matrix) that \emph{ensure} consensus in the DeGroot model is given. We propose a method of coordination that consists of: (1) the transformation of the vector of initial opinions into a vector belonging to $T_P$ by orthogonal projection and (2) subsequent iterations of the transformation $P.$ The properties of this method are studied. It is shown that for any non-periodic stochastic matrix $P,$ the resulting matrix of the orthogonal projection method can be treated as a regularized power limit of $P.$
Parameterized Matching in the Streaming Model
Venue: arXiv cs.DS 2012
Year: 2012

We study the problem of parameterized matching in a stream where we want to output matches between a pattern of length m and the last m symbols of the stream before the next symbol arrives. Parameterized matching is a natural generalisation of exact matching where an arbitrary one-to-one relabelling of pattern symbols is allowed. We show how this problem can be solved in constant time per arriving stream symbol and sublinear, near optimal space with high probability. Our results are surprising and important: it has been shown that almost no streaming pattern matching problems can be solved (not even randomised) in less than Theta(m) space, with exact matching as the only known problem to have a sublinear, near optimal space solution. Here we demonstrate that a similar sublinear, near optimal space solution is achievable for an even more challenging problem. The proof is considerably more complex than that for exact matching.
Incremental Relaying for the Gaussian Interference Channel with a Degraded Broadcasting Relay
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies incremental relay strategies for a two-user Gaussian relay-interference channel with an in-band-reception and out-of-band-transmission relay, where the link between the relay and the two receivers is modelled as a degraded broadcast channel. It is shown that generalized hash-and-forward (GHF) can achieve the capacity region of this channel to within a constant number of bits in a certain weak relay regime, where the transmitter-to-relay link gains are not unboundedly stronger than the interference links between the transmitters and the receivers. The GHF relaying strategy is ideally suited for the broadcasting relay because it can be implemented in an incremental fashion, i.e., the relay message to one receiver is a degraded version of the message to the other receiver. A generalized-degree-of-freedom (GDoF) analysis in the high signal-to-noise ratio (SNR) regime reveals that in the symmetric channel setting, each common relay bit can improve the sum rate roughly by either one bit or two bits asymptotically depending on the operating regime, and the rate gain can be interpreted as coming solely from the improvement of the common message rates, or alternatively in the very weak interference regime as solely coming from the rate improvement of the private messages. Further, this paper studies an asymmetric case in which the relay has only a single single link to one of the destinations. It is shown that with only one relay-destination link, the approximate capacity region can be established for a larger regime of channel parameters. Further, from a GDoF point of view, the sum-capacity gain due to the relay can now be thought as coming from either signal relaying only, or interference forwarding only.
Gaming security by obscurity
Venue: arXiv cs.CR 2012
Year: 2012

Shannon sought security against the attacker with unlimited computational powers: *if an information source conveys some information, then Shannon's attacker will surely extract that information*. Diffie and Hellman refined Shannon's attacker model by taking into account the fact that the real attackers are computationally limited. This idea became one of the greatest new paradigms in computer science, and led to modern cryptography. Shannon also sought security against the attacker with unlimited logical and observational powers, expressed through the maxim that "the enemy knows the system". This view is still endorsed in cryptography. The popular formulation, going back to Kerckhoffs, is that "there is no security by obscurity", meaning that the algorithms cannot be kept obscured from the attacker, and that security should only rely upon the secret keys. In fact, modern cryptography goes even further than Shannon or Kerckhoffs in tacitly assuming that *if there is an algorithm that can break the system, then the attacker will surely find that algorithm*. The attacker is not viewed as an omnipotent computer any more, but he is still construed as an omnipotent programmer. So the Diffie-Hellman step from unlimited to limited computational powers has not been extended into a step from unlimited to limited logical or programming powers. Is the assumption that all feasible algorithms will eventually be discovered and implemented really different from the assumption that everything that is computable will eventually be computed? The present paper explores some ways to refine the current models of the attacker, and of the defender, by taking into account their limited logical and programming powers. If the adaptive attacker actively queries the system to seek out its vulnerabilities, can the system gain some security by actively learning attacker's methods, and adapting to them?
Precoder Design for Physical Layer Multicasting
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the instantaneous rate maximization and the weighted sum delay minimization problems over a K-user multicast channel, where multiple antennas are available at the transmitter as well as at all the receivers. Motivated by the degree of freedom optimality and the simplicity offered by linear precoding schemes, we consider the design of linear precoders using the aforementioned two criteria. We first consider the scenario wherein the linear precoder can be any complex-valued matrix subject to rank and power constraints. We propose cyclic alternating ascent based precoder design algorithms and establish their convergence to respective stationary points. Simulation results reveal that our proposed algorithms considerably outperform known competing solutions. We then consider a scenario in which the linear precoder can be formed by selecting and concatenating precoders from a given finite codebook of precoding matrices, subject to rank and power constraints. We show that under this scenario, the instantaneous rate maximization problem is equivalent to a robust submodular maximization problem which is strongly NP hard. We propose a deterministic approximation algorithm and show that it yields a bicriteria approximation. For the weighted sum delay minimization problem we propose a simple deterministic greedy algorithm, which at each step entails approximately maximizing a submodular set function subject to multiple knapsack constraints, and establish its performance guarantee.
The ElGamal cryptosystem over circulant matrices
Venue: arXiv cs.CR 2012
Year: 2012

In this paper we study extensively the discrete logarithm problem in the group of non-singular circulant matrices. The emphasis of this study was to find the exact parameters for the group of circulant matrices for a secure implementation. We tabulate these parameters. We also compare the discrete logarithm problem in the group of circulant matrices with the discrete logarithm problem in finite fields and with the discrete logarithm problem in the group of rational points of an elliptic curve.
Optimal Power Allocation for Two-Way Decode-and-Forward OFDM Relay Networks
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a novel two-way decode-and-forward (DF) relay strategy for Orthogonal Frequency Division Multiplexing (OFDM) relay networks. This DF relay strategy employs multi-subcarrier joint channel coding to leverage frequency selective fading, and thus can achieve a higher data rate than the conventional per-subcarrier DF relay strategies. We further propose a low-complexity, optimal power allocation strategy to maximize the data rate of the proposed relay strategy. Simulation results suggest that our strategy obtains a substantial gain over the per-subcarrier DF relay strategies, and also outperforms the amplify-and-forward (AF) relay strategy in a wide signal-to-noise-ratio (SNR) region.
CSI-aided MAC with Multiuser Diversity for Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

Cognitive Radio (CR) aims to increase the spectrum utilization by allowing secondary users (SU) to access unused licensed spectrum bands. To maximize the throughput given limited sensing capability, SUs need to strike a balance between sensing the channels that are not heavily used by primary users (PU) and avoiding collisions with other SUs. To randomize sensing decisions without resorting to multiuser sensing policies, it is proposed to exploit the spatially-variant fading channel conditions on different links by adapting the reward to the channel state information (CSI). Moreover, the proposed channel-adaptive policy favors links with high achievable transmission rate and thus further improves the network throughput.
Interval edge-colorings of graph products
Venue: arXiv cs.DM 2012
Year: 2012

An interval t-coloring of a graph G is a proper edge-coloring of G with colors 1,2,...,t such that at least one edge of G is colored by i, i=1,2,...,t, and the edges incident to each vertex v\in V(G) are colored by d_{G}(v) consecutive colors, where d_{G}(v) is the degree of the vertex v in G. In this paper interval edge-colorings of various graph products are investigated.
Bayesian Locality Sensitive Hashing for Fast Similarity Search
Venue: arXiv cs.DB 2012
Year: 2012

Given a collection of objects and an associated similarity measure, the all-pairs similarity search problem asks us to find all pairs of objects with similarity greater than a certain user-specified threshold. Locality-sensitive hashing (LSH) based methods have become a very popular approach for this problem. However, most such methods only use LSH for the first phase of similarity search - i.e. efficient indexing for candidate generation. In this paper, we present BayesLSH, a principled Bayesian algorithm for the subsequent phase of similarity search - performing candidate pruning and similarity estimation using LSH. A simpler variant, BayesLSH-Lite, which calculates similarities exactly, is also presented. BayesLSH is able to quickly prune away a large majority of the false positive candidate pairs, leading to significant speedups over baseline approaches. For BayesLSH, we also provide probabilistic guarantees on the quality of the output, both in terms of accuracy and recall. Finally, the quality of BayesLSH's output can be easily tuned and does not require any manual setting of the number of hashes to use for similarity estimation, unlike standard approaches. For two state-of-the-art candidate generation algorithms, AllPairs and LSH, BayesLSH enables significant speedups, typically in the range 2x-20x for a wide variety of datasets.
Beating Irrationality: Does Delegating to IT Alleviate the Sunk Cost Effect?
Venue: arXiv cs.HC 2012
Year: 2012

In this research, we investigate the impact of delegating decision making to information technology (IT) on an important human decision bias - the sunk cost effect. To address our research question, we use a unique and very rich dataset containing actual market transaction data for approximately 7,000 pay-per-bid auctions. Thus, unlike previous studies that are primarily laboratory experiments, we investigate the effects of using IT on the proneness to a decision bias in real market transactions. We identify and analyze irrational decision scenarios of auction participants. We find that participants with a higher monetary investment have an increased likelihood of violating the assumption of rationality, due to the sunk cost effect. Interestingly, after controlling for monetary investments, participants who delegate their decision making to IT and, consequently, have comparably lower behavioral investments (e.g., emotional attachment, effort, time) are less prone to the sunk cost effect. In particular, delegation to IT reduces the impact of overall investments on the sunk cost effect by approximately 50%.
Efficient Tracking of Large Classes of Experts
Venue: arXiv cs.LG 2012
Year: 2012

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different "base" expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular we provide a method that can transform any prediction algorithm $\A$ that is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency of $\A$ in the sense that it can be implemented with time and space complexity only $O(n^γ \ln n)$ times larger than that of $\A$, where $n$ is the time horizon and $γ\ge 0$ is a parameter of the algorithm. With $\A$ properly chosen, our algorithm achieves a regret bound of optimal order for $γ>0$, and only $O(\ln n)$ times larger than the optimal order for $γ=0$ for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimal $O(\ln n)$ regret rate with time complexity $O(n^{1+γ}\ln n)$ for any $γ\in (0,1)$.
On the Existence of Hamiltonian Paths for History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes
Venue: arXiv cs.DM 2012
Year: 2012

An acyclic USO on a hypercube is formed by directing its edges in such as way that the digraph is acyclic and each face of the hypercube has a unique sink and a unique source. A path to the global sink of an acyclic USO can be modeled as pivoting in a unit hypercube of the same dimension with an abstract objective function, and vice versa. In such a way, Zadeh's 'least entered rule' and other history based pivot rules can be applied to the problem of finding the global sink of an acyclic USO. In this paper we present some theoretical and empirical results on the existence of acyclic USOs for which the various history based pivot rules can be made to follow a Hamiltonian path. In particular, we develop an algorithm that can enumerate all such paths up to dimension 6 using efficient pruning techniques. We show that Zadeh's original rule admits Hamiltonian paths up to dimension 9 at least, and prove that most of the other rules do not for all dimensions greater than 5.
Can Nondeterminism Help Complementation?
Venue: arXiv cs.LO 2012
Year: 2012

Complementation and determinization are two fundamental notions in automata theory. The close relationship between the two has been well observed in the literature. In the case of nondeterministic finite automata on finite words (NFA), complementation and determinization have the same state complexity, namely Theta(2^n) where n is the state size. The same similarity between determinization and complementation was found for Buchi automata, where both operations were shown to have 2^Θ(n lg n) state complexity. An intriguing question is whether there exists a type of omega-automata whose determinization is considerably harder than its complementation. In this paper, we show that for all common types of omega-automata, the determinization problem has the same state complexity as the corresponding complementation problem at the granularity of 2^Θ(.).
The Decentralized Structure of Collective Attention on the Web
Venue: arXiv cs.IR 2012
Year: 2012

Background: The collective browsing behavior of users gives rise to a flow network transporting attention between websites. By analyzing the structure of this network we uncovered a nontrivial scaling regularity concerning the impact of websites. Methodology: We constructed three clickstreams networks, whose nodes were websites and edges were formed by the users switching between sites. We developed an indicator Ci as a measure of the impact of site i and investigated its correlation with the traffic of the site Ai both on the three networks and across the language communities within the networks. Conclusions: We found that the impact of websites increased slower than their traffic. Specifically, there existed a scaling relationship between Ci and Ai with an exponent gamma smaller than 1. We suggested that this scaling relationship characterized the decentralized structure of the clickstream circulation: the World Wide Web is a system that favors small sites in reassigning the collective attention of users.
Monomials in arithmetic circuits: Complete problems in the counting hierarchy
Venue: arXiv cs.CC 2012
Year: 2012

We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems. We also study these questions for circuits computing multilinear polynomials.