OpenRaiser/Intern-Atlas huggingface dataset:
Finding Associations and Computing Similarity via Biased Pair Sampling
Venue: arXiv cs.DS 2010
Year: 2010

This version is ***superseded*** by a full version that can be found at http://www.itu.dk/people/pagh/papers/mining-jour.pdf, which contains stronger theoretical results and fixes a mistake in the reporting of experiments. Abstract: Sampling-based methods have previously been proposed for the problem of finding interesting associations in data, even for low-support items. While these methods do not guarantee precise results, they can be vastly more efficient than approaches that rely on exact counting. However, for many similarity measures no such methods have been known. In this paper we show how a wide variety of measures can be supported by a simple biased sampling method. The method also extends to find high-confidence association rules. We demonstrate theoretically that our method is superior to exact methods when the threshold for "interesting similarity/confidence" is above the average pairwise similarity/confidence, and the average support is not too low. Our method is particularly good when transactions contain many items. We confirm in experiments on standard association mining benchmarks that this gives a significant speedup on real data sets (sometimes much larger than the theoretical guarantees). Reductions in computation time of over an order of magnitude, and significant savings in space, are observed.
Compressed Blind De-convolution
Venue: arXiv cs.IT 2010
Year: 2010

Suppose the signal x is realized by driving a k-sparse signal u through an arbitrary unknown stable discrete-linear time invariant system H. These types of processes arise naturally in Reflection Seismology. In this paper we are interested in several problems: (a) Blind-Deconvolution: Can we recover both the filter $H$ and the sparse signal $u$ from noisy measurements? (b) Compressive Sensing: Is x compressible in the conventional sense of compressed sensing? Namely, can x, u and H be reconstructed from a sparse set of measurements. We develop novel L1 minimization methods to solve both cases and establish sufficient conditions for exact recovery for the case when the unknown system H is auto-regressive (i.e. all pole) of a known order. In the compressed sensing/sampling setting it turns out that both H and x can be reconstructed from O(k log(n)) measurements under certain technical conditions on the support structure of u. Our main idea is to pass x through a linear time invariant system G and collect O(k log(n)) sequential measurements. The filter G is chosen suitably, namely, its associated Toeplitz matrix satisfies the RIP property. We develop a novel LP optimization algorithm and show that both the unknown filter H and the sparse input u can be reliably estimated.
Hypergraphic LP Relaxations for Steiner Trees
Venue: arXiv cs.DM 2010
Year: 2010

We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this LP, and studying its relation to other linear relaxations. Our results are the following. Structural results: We extend the technique of uncrossing, usually applied to families of sets, to families of partitions. As a consequence we show that any basic feasible solution to the partition LP formulation has sparse support. Although the number of variables could be exponential, the number of positive variables is at most the number of terminals. Relations with other relaxations: We show the equivalence of the partition LP relaxation with other known hypergraphic relaxations. We also show that these hypergraphic relaxations are equivalent to the well studied bidirected cut relaxation, if the instance is quasibipartite. Integrality gap upper bounds: We show an upper bound of sqrt(3) ~ 1.729 on the integrality gap of these hypergraph relaxations in general graphs. In the special case of uniformly quasibipartite instances, we show an improved upper bound of 73/60 ~ 1.216. By our equivalence theorem, the latter result implies an improved upper bound for the bidirected cut relaxation as well.
Physical layer network coding with multiple antennas
Venue: arXiv cs.NI 2010
Year: 2010

The two-phase MIMO NC (network coding) scheme can be used to boost the throughput in a two-way relay channel in which nodes are equipped with multiple antennas. The obvious strategy is for the relay node to extract the individual packets from the two end nodes and mix the two packets to form a network-coded packet. In this paper, we propose a new scheme called MIMO PNC (physical network coding), in which the relay extracts the summation and difference of the two end packets and then converts them to the network-coded form. MIMO PNC is a natural combination of the single-antenna PNC scheme and the linear MIMO detection scheme. The advantages of MIMO PNC are many. First, it removes the stringent carrier-phase requirement in single-antenna PNC. Second, it is linear in complexity with respect to the constellation size and the number of simultaneous data streams in MIMO. Simulation shows that MIMO PNC outperforms the straightforward MIMO NC significantly under random Rayleigh fading channel. Based on our analysis, we further conjecture that MIMO PNC outperforms MIMO NC under all possible realizations of the channel.
Slepian-Wolf Coding Over Cooperative Relay Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper deals with the problem of multicasting a set of discrete memoryless correlated sources (DMCS) over a cooperative relay network. Necessary conditions with cut-set interpretation are presented. A \emph{Joint source-Wyner-Ziv encoding/sliding window decoding} scheme is proposed, in which decoding at each receiver is done with respect to an ordered partition of other nodes. For each ordered partition a set of feasibility constraints is derived. Then, utilizing the sub-modular property of the entropy function and a novel geometrical approach, the results of different ordered partitions are consolidated, which lead to sufficient conditions for our problem. The proposed scheme achieves operational separation between source coding and channel coding. It is shown that sufficient conditions are indeed necessary conditions in two special cooperative networks, namely, Aref network and finite-field deterministic network. Also, in Gaussian cooperative networks, it is shown that reliable transmission of all DMCS whose Slepian-Wolf region intersects the cut-set bound region within a constant number of bits, is feasible. In particular, all results of the paper are specialized to obtain an achievable rate region for cooperative relay networks which includes relay networks and two-way relay networks.
Algorithmic randomness and monotone complexity on product space
Venue: arXiv cs.IT 2010
Year: 2010

We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen's theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, Bayesian statistics for individual random sequences. Formerly Lambalgen's theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Comp. 2008]. In this paper we show the theorem without the assumption.
Minimal Polynomial Algorithms for Finite Sequences
Venue: arXiv cs.IT 2010
Year: 2010

We show that a straightforward rewrite of a known minimal polynomial algorithm yields a simpler version of a recent algorithm of A. Salagean.
Fast Arc-Annotated Subsequence Matching in Linear Space
Venue: arXiv cs.DS 2010
Year: 2010

An arc-annotated string is a string of characters, called bases, augmented with a set of pairs, called arcs, each connecting two bases. Given arc-annotated strings $P$ and $Q$ the arc-preserving subsequence problem is to determine if $P$ can be obtained from $Q$ by deleting bases from $Q$. Whenever a base is deleted any arc with an endpoint in that base is also deleted. Arc-annotated strings where the arcs are ``nested'' are a natural model of RNA molecules that captures both the primary and secondary structure of these. The arc-preserving subsequence problem for nested arc-annotated strings is basic primitive for investigating the function of RNA molecules. Gramm et al. [ACM Trans. Algorithms 2006] gave an algorithm for this problem using $O(nm)$ time and space, where $m$ and $n$ are the lengths of $P$ and $Q$, respectively. In this paper we present a new algorithm using $O(nm)$ time and $O(n + m)$ space, thereby matching the previous time bound while significantly reducing the space from a quadratic term to linear. This is essential to process large RNA molecules where the space is likely to be a bottleneck. To obtain our result we introduce several novel ideas which may be of independent interest for related problems on arc-annotated strings.
Towards Power Efficient MAC Protocol for In-Body and On-Body Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper presents an empirical discussion on the design and implementation of a power-efficient Medium Access Control (MAC) protocol for in-body and on-body sensor networks. We analyze the performance of a beacon-enabled IEEE 802.15.4, PB-TDMA, and S-MAC protocols for on-body sensor networks. We further present a Traffic Based Wakeup Mechanism that utilizes the traffic patterns of the BAN Nodes (BNs) to accommodate the entire BSN traffic. To enable a logical connection between different BNs working on different frequency bands, a method called Bridging function is proposed. The Bridging function integrates all BNs working on different bands into a complete BSN.
Hitting all maximum cliques with a stable set using lopsided independent transversals
Venue: arXiv cs.DM 2010
Year: 2010

Rabern recently proved that any graph with omega >= (3/4)(Delta+1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with omega > (2/3)(Delta+1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size.
Big Macs and Eigenfactor Scores: Don't Let Correlation Coefficients Fool You
Venue: arXiv cs.DL 2010
Year: 2010

The Eigenfactor Metrics provide an alternative way of evaluating scholarly journals based on an iterative ranking procedure analogous to Google's PageRank algorithm. These metrics have recently been adopted by Thomson-Reuters and are listed alongside the Impact Factor in the Journal Citation Reports. But do these metrics differ sufficiently so as to be a useful addition to the bibliometric toolbox? Davis (2008) has argued otherwise, based on his finding of a 0.95 correlation coefficient between Eigenfactor score and Total Citations for a sample of journals in the field of medicine. This conclusion is mistaken; here we illustrate the basic statistical fallacy to which Davis succumbed. We provide a complete analysis of the 2006 Journal Citation Reports and demonstrate that there are statistically and economically significant differences between the information provided by the Eigenfactor Metrics and that provided by Impact Factor and Total Citations.
Cooperative Feedback for Multi-Antenna Cognitive Radio Networks
Venue: arXiv cs.IT 2010
Year: 2010

Cognitive beamforming (CB) is a multi-antenna technique for efficient spectrum sharing between primary users (PUs) and secondary users (SUs) in a cognitive radio network. Specifically, a multi-antenna SU transmitter applies CB to suppress the interference to the PU receivers as well as enhance the corresponding SU-link performance. In this paper, for a multiple-input-single-output (MISO) SU channel coexisting with a single-input-single-output (SISO) PU channel, we propose a new and practical paradigm for designing CB based on the finite-rate cooperative feedback from the PU receiver to the SU transmitter. Specifically, the PU receiver communicates to the SU transmitter the quantized SU-to-PU channel direction information (CDI) for computing the SU transmit beamformer, and the interference power control (IPC) signal that regulates the SU transmission power according to the tolerable interference margin at the PU receiver. Two CB algorithms based on cooperative feedback are proposed: one restricts the SU transmit beamformer to be orthogonal to the quantized SU-to-PU channel direction and the other relaxes such a constraint. In addition, cooperative feedforward of the SU CDI from the SU transmitter to the PU receiver is exploited to allow more efficient cooperative feedback. The outage probabilities of the SU link for different CB and cooperative feedback/feedforward algorithms are analyzed, from which the optimal bit-allocation tradeoff between the CDI and IPC feedback is characterized.
Counting Triangulations of Planar Point Sets
Venue: arXiv cs.DM 2010
Year: 2010

We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl (2006), which has led to the previous best upper bound of $43^n$ for the problem. Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, we derive new upper bounds for the number of planar graphs ($o(239.4^n)$), spanning cycles ($O(70.21^n)$), and spanning trees ($160^n$).
Bounded Independence Fools Degree-2 Threshold Functions
Venue: arXiv cs.CC 2010
Year: 2010

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of k-wise independent distributions, we obtain a broad class of explicit generators that epsilon-fool the class of degree-2 threshold functions with seed length log(n)*poly(1/epsilon). Our approach is quite robust: it easily extends to yield that the intersection of any constant number of degree-2 threshold functions is epsilon-fooled by poly(1/epsilon)-wise independence. Our results also hold if the entries of x are k-wise independent standard normals, implying for example that bounded independence derandomizes the Goemans-Williamson hyperplane rounding scheme. To achieve our results, we introduce a technique we dub multivariate FT-mollification, a generalization of the univariate form introduced by Kane et al. (SODA 2010) in the context of streaming algorithms. Along the way we prove a generalized hypercontractive inequality for quadratic forms which takes the operator norm of the associated matrix into account. These techniques may be of independent interest.
Scheduling Sensors for Guaranteed Sparse Coverage
Venue: arXiv cs.NI 2010
Year: 2010

Sensor networks are particularly applicable to the tracking of objects in motion. For such applications, it may not necessary that the whole region be covered by sensors as long as the uncovered region is not too large. This notion has been formalized by Balasubramanian et.al. as the problem of $κ$-weak coverage. This model of coverage provides guarantees about the regions in which the objects may move undetected. In this paper, we analyse the theoretical aspects of the problem and provide guarantees about the lifetime achievable. We introduce a number of practical algorithms and analyse their significance. The main contribution is a novel linear programming based algorithm which provides near-optimal lifetime. Through extensive experimentation, we analyse the performance of these algorithms based on several parameters defined.
Computation- and Space-Efficient Implementation of SSA
Venue: arXiv cs.NA 2010
Year: 2010

The computational complexity of different steps of the basic SSA is discussed. It is shown that the use of the general-purpose "blackbox" routines (e.g. found in packages like LAPACK) leads to huge waste of time resources since the special Hankel structure of the trajectory matrix is not taken into account. We outline several state-of-the-art algorithms (for example, Lanczos-based truncated SVD) which can be modified to exploit the structure of the trajectory matrix. The key components here are hankel matrix-vector multiplication and hankelization operator. We show that both can be computed efficiently by the means of Fast Fourier Transform. The use of these methods yields the reduction of the worst-case computational complexity from O(N^3) to O(k N log(N)), where N is series length and k is the number of eigentriples desired.
A New Approach to Analyzing Patterns of Collaboration in Co-authorship Networks - Mesoscopic Analysis and Interpretation
Venue: arXiv cs.CY 2010
Year: 2010

This paper focuses on methods to study patterns of collaboration in co-authorship networks at the mesoscopic level. We combine qualitative methods (participant interviews) with quantitative methods (network analysis) and demonstrate the application and value of our approach in a case study comparing three research fields in chemistry. A mesoscopic level of analysis means that in addition to the basic analytic unit of the individual researcher as node in a co-author network, we base our analysis on the observed modular structure of co-author networks. We interpret the clustering of authors into groups as bibliometric footprints of the basic collective units of knowledge production in a research specialty. We find two types of coauthor-linking patterns between author clusters that we interpret as representing two different forms of cooperative behavior, transfer-type connections due to career migrations or one-off services rendered, and stronger, dedicated inter-group collaboration. Hence the generic coauthor network of a research specialty can be understood as the overlay of two distinct types of cooperative networks between groups of authors publishing in a research specialty. We show how our analytic approach exposes field specific differences in the social organization of research.
Autosolvability of halting problem instances for instruction sequences
Venue: arXiv cs.LO 2010
Year: 2010

We position Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines. The mere requirement that a program of a certain kind must solve the halting problem for all programs of that kind leads to a contradiction in the case of a recent unsolvability result regarding the halting problem for programs. In this paper, we investigate this autosolvability requirement in a setting in which programs take the form of instruction sequences.
The Communication of Meaning and the Structuration of Expectations: Giddens' "structuration theory" and Luhmann's "self-organization"
Venue: arXiv cs.CY 2010
Year: 2010

The communication of meaning as different from (Shannon-type) information is central to Luhmann's social systems theory and Giddens' structuration theory of action. These theories share an emphasis on reflexivity, but focus on meaning along a divide between inter-human communication and intentful action as two different systems of reference. Recombining these two theories into a theory about the structuration of expectations, interactions, organization, and self-organization of intentional communications can be simulated based on algorithms from the computation of anticipatory systems. The self-organizing and organizing layers remain rooted in the double contingency of the human encounter which provides the variation. Organization and self-organization of communication are reflexive upon and therefore reconstructive of each other. Using mutual information in three dimensions, the imprint of meaning processing in the modeling system on the historical organization of uncertainty in the modeled system can be measured. This is shown empirically in the case of intellectual organization as "structurating" structure in the textual domain of scientific articles.
Grammar-Based Compression in a Streaming Model
Venue: arXiv cs.DS 2010
Year: 2010

We show that, given a string $s$ of length $n$, with constant memory and logarithmic passes over a constant number of streams we can build a context-free grammar that generates $s$ and only $s$ and whose size is within an $\Oh{\min (g \log g, \sqrt{n \log g})}$-factor of the minimum $g$. This stands in contrast to our previous result that, with polylogarithmic memory and polylogarithmic passes over a single stream, we cannot build such a grammar whose size is within any polynomial of $g$.
Extending Karger's randomized min-cut Algorithm for a Synchronous Distributed setting
Venue: arXiv cs.DS 2010
Year: 2010

A min-cut that seperates vertices s and t in a network is an edge set of minimum weight whose removal will disconnect s and t. This problem is the dual of the well known s-t max-flow problem. Several algorithms for the min-cut problem are based on max-flow computation although the fastest known min-cut algorithms are not flow based. The well known Karger's randomized algorithm for min-cut is a non-flow based method for solving the (global) min-cut problem of finding the min s-t cut over all pair of vertices s,t in a weighted undirected graph. This paper presents an adaptation of Karger's algorithm for a synchronous distributed setting where each node is allowed to perform only local computations. The paper essentially addresses the technicalities involved in circumventing the limitations imposed by a distributed setting to the working of Karger's algorithm. While the correctness proof follows directly from Karger's algorithm, the complexity analysis differs significantly. The algorithm achieves the same probability of success as the original algorithm with O(mn^{2}) message complexity and O(n^{2}) time complexity, where n and m denote the number of vertices and edges in the graph.
Algorithms and Hardness for Subspace Approximation
Venue: arXiv cs.DS 2010
Year: 2010

The subspace approximation problem Subspace($k$,$p$) asks for a $k$-dimensional linear subspace that fits a given set of points optimally, where the error for fitting is a generalization of the least squares fit and uses the $\ell_{p}$ norm instead. Most of the previous work on subspace approximation has focused on small or constant $k$ and $p$, using coresets and sampling techniques from computational geometry. In this paper, extending another line of work based on convex relaxation and rounding, we give a polynomial time algorithm, \emph{for any $k$ and any $p \geq 2$}, with the approximation guarantee roughly $γ_{p} \sqrt{2 - \frac{1}{n-k}}$, where $γ_{p}$ is the $p$-th moment of a standard normal random variable N(0,1). We show that the convex relaxation we use has an integrality gap (or "rank gap") of $γ_{p} (1 - ε)$, for any constant $ε> 0$. Finally, we show that assuming the Unique Games Conjecture, the subspace approximation problem is hard to approximate within a factor better than $γ_{p} (1 - ε)$, for any constant $ε> 0$.
Construction Sequences and Certifying 3-Connectedness
Venue: arXiv cs.DS 2010
Year: 2010

Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Gruenbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to the K_4 can be computed in O(|V|^2) time by extending Barnette and Gruenbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.