OpenRaiser/Intern-Atlas huggingface dataset:
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line : Algorithms and Complexity
Venue: arXiv cs.CG 2014
Year: 2014

Finding a maximum independent set (MIS) of a given fam- ily of axis-parallel rectangles is a basic problem in computational geom- etry and combinatorics. This problem has attracted significant atten- tion since the sixties, when Wegner conjectured that the corresponding duality gap, i.e., the maximum possible ratio between the maximum independent set and the minimum hitting set (MHS), is bounded by a universal constant. An interesting special case, that may prove use- ful to tackling the general problem, is the diagonal-intersecting case, in which the given family of rectangles is intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6 approximation algorithm for MHS in this setting, and showed that the duality gap is between 3/2 and 6. In this paper we improve upon these results. First we show that MIS in diagonal-intersecting families is NP-complete, providing one smallest subclass for which MIS is provably hard. Then, we derive an $O(n^2)$-time algorithm for the maximum weight independent set when, in addition the rectangles intersect below the diagonal. This improves and extends a classic result of Lubiw, and amounts to obtain a 2-approximation algo- rithm for the maximum weight independent set of rectangles intersecting a diagonal. Finally, we prove that for diagonal-intersecting families the duality gap is between 2 and 4. The upper bound, which implies an approximation algorithm of the same factor, follows from a simple com- binatorial argument, while the lower bound represents the best known lower bound on the duality gap, even in the general case.
An Extensive Experimental Study on the Cluster-based Reference Set Reduction for speeding-up the k-NN Classifier
Venue: arXiv cs.LG 2014
Year: 2014

The k-Nearest Neighbor (k-NN) classification algorithm is one of the most widely-used lazy classifiers because of its simplicity and ease of implementation. It is considered to be an effective classifier and has many applications. However, its major drawback is that when sequential search is used to find the neighbors, it involves high computational cost. Speeding-up k-NN search is still an active research field. Hwang and Cho have recently proposed an adaptive cluster-based method for fast Nearest Neighbor searching. The effectiveness of this method is based on the adjustment of three parameters. However, the authors evaluated their method by setting specific parameter values and using only one dataset. In this paper, an extensive experimental study of this method is presented. The results, which are based on five real life datasets, illustrate that if the parameters of the method are carefully defined, one can achieve even better classification performance.
A Note on Pushdown Automata Systems
Venue: arXiv cs.FL 2014
Year: 2014

In (Csuhaj-Varju et. al. 2000) Parallel Communicating Systems of Pushdown Automata (PCPA) were introduced and shown to be able to simulate nondeterministic one-way multi-head pushdown automata in returning mode, even if communication is restricted to be one-way having a single target component. A simulation of such centralized PCPA by one-way multi-head pushdown automata (Balan 2009) turned out to be incomplete (Otto 2012). Subsequently it was shown that centralized returning PCPA are universal even if the number of components is two (Petersen 2013) and thus are separated from one-way multi-head pushdown automata. Another line of research modified the definition of PCPA such that communication is asynchronous (Otto 2013). While the simulation of one-way multi-head pushdown automata is still possible, now a converse construction shows this model in returning mode to be equivalent to the one-way multi-head pushdown automaton in a very precise sense. It was left open, whether non-centralized returning PCPA of degree two are universal. In the first part of the paper we show this to be the case. Then we turn our attention to Uniform Distributed Pushdown Automata Systems (UDPAS). These systems of automata work in turn on a single tape. We show that UPDAS accepting with empty stack do not form a hierarchy depending on the number of components and that the membership problem is complete in NP, answering two open problems from (Arroyo et. al. 2012).
On the group-theoretic structure of lifted filter banks
Venue: arXiv cs.IT 2014
Year: 2014

The polyphase-with-advance matrix representations of whole-sample symmetric (WS) unimodular filter banks form a multiplicative matrix Laurent polynomial group. Elements of this group can always be factored into lifting matrices with half-sample symmetric (HS) off-diagonal lifting filters; such linear phase lifting factorizations are specified in the ISO/IEC JPEG 2000 image coding standard. Half-sample symmetric unimodular filter banks do not form a group, but such filter banks can be partially factored into a cascade of whole-sample antisymmetric (WA) lifting matrices starting from a concentric, equal-length HS base filter bank. An algebraic framework called a group lifting structure has been introduced to formalize the group-theoretic aspects of matrix lifting factorizations. Despite their pronounced differences, it has been shown that the group lifting structures for both the WS and HS classes satisfy a polyphase order-increasing property that implies uniqueness ("modulo rescaling") of irreducible group lifting factorizations in both group lifting structures. These unique factorization results can in turn be used to characterize the group-theoretic structure of the groups generated by the WS and HS group lifting structures.
Timing, Carrier, and Frame Synchronization of Burst-Mode CPM
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose a complete synchronization algorithm for continuous phase modulation (CPM) signals in burst-mode transmission over additive white Gaussian noise (AWGN) channels. The timing and carrier recovery are performed through a data-aided (DA) maximum likelihood algorithm, which jointly estimates symbol timing, carrier phase, and frequency offsets based on an optimized synchronization preamble. Our algorithm estimates the frequency offset via a one dimensional grid search, after which symbol timing and carrier phase are computed via simple closed-form expressions. The mean-square error (MSE) of the algorithm's estimates reveals that it performs very close to the theoretical Cramér-Rao bound (CRB) for various CPMs at signal-to-noise ratios (SNRs) as low as 0 dB. Furthermore, we present a frame synchronization algorithm that detects the arrival of bursts and estimates the start-of-signal. We simulate the performance of the frame synchronization algorithm along with the timing and carrier recovery algorithm. The bit error rate results demonstrate near ideal synchronization performance for low SNRs and short preambles.
On the index of Simon's congruence for piecewise testability
Venue: arXiv cs.FL 2014
Year: 2014

Simon's congruence, denoted \sim_n, relates words having the same subwords of length up to n. We show that, over a k-letter alphabet, the number of words modulo \sim_n is in 2^{Θ(n^{k-1} log n)}.
Microscopic Evolution of Social Networks by Triad Position Profile
Venue: arXiv cs.SI 2014
Year: 2014

Disentangling the mechanisms underlying the social network evolution is one of social science's unsolved puzzles. Preferential attachment is a powerful mechanism explaining social network dynamics, yet not able to explain all scaling-laws in social networks. Recent advances in understanding social network dynamics demonstrate that several scaling-laws in social networks follow as natural consequences of triadic closure. Macroscopic comparisons between them are discussed empirically in many works. However the network evolution drives not only the emergence of macroscopic scaling but also the microscopic behaviors. Here we exploit two fundamental aspects of the network microscopic evolution: the individual influence evolution and the process of link formation. First we develop a novel framework for the microscopic evolution, where the mechanisms of preferential attachment and triadic closure are well balanced. Then on four real-world datasets we apply our approach for two microscopic problems: node's prominence prediction and link prediction, where our method yields significant predictive improvement over baseline solutions. Finally to be rigorous and comprehensive, we further observe that our framework has a stronger generalization capacity across different kinds of social networks for two microscopic prediction problems. We unveil the significant factors with a greater degree of precision than has heretofore been possible, and shed new light on networks evolution.
Multi-channel Wireless Networks with Infrastructure Support: Capacity and Delay
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we propose a novel multi-channel network with infrastructure support, called an \textit{MC-IS} network, which has not been studied in the literature. To the best of our knowledge, we are the first to study such an \textit{MC-IS} network. Our \textit{MC-IS} network is equipped with a number of infrastructure nodes which can communicate with common nodes using a number of channels where a communication between a common node and an infrastructure node is called an infrastructure communication and a communication between two common nodes is called an ad-hoc communication. Our proposed \textit{MC-IS} network has a number of advantages over three existing conventional networks, namely a single-channel wireless ad hoc network (called an \textit{SC-AH} network), a multi-channel wireless ad hoc network (called an \textit{MC-AH} network) and a single-channel network with infrastructure support (called an \textit{SC-IS} network). In particular, the \textit{network capacity} of our proposed \textit{MC-IS} network is $\sqrt{n \log n}$ times higher than that of an \textit{SC-AH} network and an \textit{MC-AH} network and the same as that of an \textit{SC-IS} network, where $n$ is the number of nodes in the network. The \textit{average delay} of our \textit{MC-IS} network is $\sqrt{\log n/n}$ times lower than that of an \textit{SC-AH} network and an \textit{MC-AH} network, and $\min(C_I,m)$ times lower than the average delay of an \textit{SC-IS} network, where $C_I$ and $m$ denote the number of channels dedicated for infrastructure communications and the number of interfaces mounted at each infrastructure node, respectively.
On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem
Venue: arXiv cs.CC 2014
Year: 2014

Consider a system of two polynomial equations in two variables: $$F(X,Y)=G(X,Y)=0$$ where $F \in \rr[X,Y]$ has degree $d \geq 1$ and $G \in \rr[X,Y]$ has $t$ monomials. We show that the system has only $O(d^3t+d^2t^3)$ real solutions when it has a finite number of real solutions. This is the first polynomial bound for this problem. In particular, the bounds coming from the theory of fewnomials are exponential in $t$, and count only nondegenerate solutions. More generally, we show that if the set of solutions is infinite, it still has at most $O(d^3t+d^2t^3)$ connected components. By contrast, the following question seems to be open: if $F$ and $G$ have at most $t$ monomials, is the number of (nondegenerate) solutions polynomial in $t$? The authors' interest for these problems was sparked by connections between lower bounds in algebraic complexity theory and upper bounds on the number of real roots of "sparse like" polynomials.
Information Relaxation is Ultradiffusive
Venue: arXiv cs.SI 2014
Year: 2014

We investigate how the overall response to a piece of information (a story or an article) evolves and relaxes as a function of time in social networks like Reddit, Digg and Youtube. This response or popularity is measured in terms of the number of votes/comments that the story (or article) accrued over time. We find that the temporal evolution of popularity can be described by a universal function whose parameters depend upon the system under consideration. Unlike most previous studies, which empirically investigated the dynamics of voting behavior, we also give a theoretical interpretation of the observed behavior using ultradiffusion. Whether it is the inter-arrival time between two consecutive votes on a story on Reddit or the comments on a video shared on Youtube, there is always a hierarchy of time scales in information propagation. One vote/comment might occur almost simultaneously with the previous, whereas another vote/comment might occur hours after the preceding one. This hierarchy of time scales leads us to believe that the dynamical response of users to information is ultradiffusive in nature. We show that a ultradiffusion based stochastic process can be used to rationalize the observed temporal evolution.
Measuring Triple-Helix Synergy in the Russian Innovation Systems at Regional, Provincial, and National Levels
Venue: arXiv cs.CY 2014
Year: 2014

We measure synergy for the Russian national, provincial, and regional innovation systems as reduction of uncertainty using mutual information among the three distributions of firm sizes, technological knowledge-bases of firms, and geographical locations. Half a million data at firm level in 2011 were obtained from the Orbis database of Bureau Van Dijk. The firm level data were aggregated at the levels of eight Federal Districts, the regional level of 83 Federal Subjects, and the single level of the Russian Federation. Not surprisingly, the knowledge base of the economy is concentrated in the Moscow region (22.8%); St. Petersburg follows with 4.0%. Only 0.4% of the firms are classified as high-tech, and 2.7% as medium-tech manufacturing (NACE, Rev. 2). Except in Moscow itself, high-tech manufacturing does not add synergy to any other unit at any of the various levels of geographical granularity; instead it disturbs regional coordination even in the region surrounding Moscow ("Moscow Region"). In the case of medium-tech manufacturing, there is also synergy in St. Petersburg. Knowledge-intensive services (KIS; including laboratories) contribute 12.8% to the economy in terms of establishments and contribute to the synergy in all Federal Districts (except the North-Caucasian Federal District), but only in 30 of the 83 Federal Subjects. The synergy in KIS is concentrated in centers of administration. Unlike Western European countries, the knowledge-intensive services (which are often state-affiliated) thus provide backbone to an emerging knowledge-based economy at the level of Federal Districts, but the economy is otherwise not knowledge-based (except for the Moscow region).
Scalable Verification of Markov Decision Processes
Venue: arXiv cs.DS 2014
Year: 2014

Markov decision processes (MDP) are useful to model concurrent process optimisation problems, but verifying them with numerical methods is often intractable. Existing approximative approaches do not scale well and are limited to memoryless schedulers. Here we present the basis of scalable verification for MDPSs, using an O(1) memory representation of history-dependent schedulers. We thus facilitate scalable learning techniques and the use of massively parallel verification.
Naming Game on Networks: Let Everyone be Both Speaker and Hearer
Venue: arXiv cs.SI 2014
Year: 2014

To investigate how consensus is reached on a large self-organized peer-to-peer network, we extended the naming game model commonly used in language and communication to Naming Game in Groups (NGG). Differing from other existing naming game models, in NGG, everyone in the population (network) can be both speaker and hearer simultaneously, which resembles in a closer manner to real-life scenarios. Moreover, NGG allows the transmission (communication) of multiple words (opinions) for multiple intra-group consensuses. The communications among indirectly-connected nodes are also enabled in NGG. We simulated and analyzed the consensus process in some typical network topologies, including random-graph networks, small-world networks and scale-free networks, to better understand how global convergence (consensus) could be reached on one common word. The results are interpreted on group negotiation of a peer-to-peer network, which shows that global consensus in the population can be reached more rapidly when more opinions are permitted within each group or when the negotiating groups in the population are larger in size. The novel features and properties introduced by our model have demonstrated its applicability in better investigating general consensus problems on peer-to-peer networks.
An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
Venue: arXiv cs.IT 2014
Year: 2014

This paper designs and evaluates a practical algorithm, called practical recursive projected compressive sensing (Prac-ReProCS), for recovering a time sequence of sparse vectors $S_t$ and a time sequence of dense vectors $L_t$ from their sum, $M_t:= S_t + L_t$, when any subsequence of the $L_t$'s lies in a slowly changing low-dimensional subspace. A key application where this problem occurs is in video layering where the goal is to separate a video sequence into a slowly changing background sequence and a sparse foreground sequence that consists of one or more moving regions/objects. Prac-ReProCS is a practical modification of its theoretical counterpart which was analyzed in our recent work. Experimental comparisons demonstrating the advantage of the approach for both simulated and real videos are shown. Extension to the undersampled case is also developed.
Journal Maps, Interactive Overlays, and the Measurement of Interdisciplinarity on the Basis of Scopus Data (1996-2012)
Venue: arXiv cs.DL 2014
Year: 2014

Using Scopus data, we construct a global map of science based on aggregated journal-journal citations from 1996-2012 (N of journals = 20,554). This base map enables users to overlay downloads from Scopus interactively. Using a single year (e.g., 2012), results can be compared with mappings based on the Journal Citation Reports at the Web-of-Science (N = 10,936). The Scopus maps are more detailed at both the local and global levels because of their greater coverage, including, for example, the arts and humanities. The base maps can be interactively overlaid with journal distributions in sets downloaded from Scopus, for example, for the purpose of portfolio analysis. Rao-Stirling diversity can be used as a measure of interdisciplinarity in the sets under study. Maps at the global and the local level, however, can be very different because of the different levels of aggregation involved. Two journals, for example, can both belong to the humanities in the global map, but participate in different specialty structures locally. The base map and interactive tools are available online (with instructions) at http://www.leydesdorff.net/scopus_ovl.
Fractional Interference Alignment: An Interference Alignment Scheme for Finite Alphabet Signals
Venue: arXiv cs.IT 2014
Year: 2014

Interference Alignment (IA) is a transmission scheme which achieves 1/2 Degrees-of-Freedom (DoF) per transmit-antenna per user. The constraints imposed on the scheme are based on the linear receiver since conventional IA assumes Gaussian signaling. However, when the transmitters employ Finite Alphabet (FA) signaling, neither the conventional IA precoders nor the linear receiver are optimal structures. Therefore, a novel Fractional Interference Alignment (FIA) scheme is introduced when FA signals are used, where the alignment constraints are now based on the non-linear, minimum distance (MD) detector. Since DoF is defined only as signal-to-noise ratio tends to infinity, we introduce a new metric called SpAC (number of Symbols transmitted-per-transmit Antenna-per-Channel use) for analyzing the FIA scheme. The maximum SpAC is one, and the FIA achieves any value of SpAC in the range [0,1]. The key motivation for this work is that numerical simulations with FA signals and MD detector for fixed SpAC (=1/2, as in IA) over a set of optimization problems, like minimizing bit error rate or maximizing the mutual information, achieves a significantly better error rate performance when compared to the existing algorithms that minimize mean square error or maximize signal-to-interference plus noise ratio.
MuPAD codes which implement limit-computable functions that cannot be bounded by any computable function
Venue: arXiv cs.CC 2014
Year: 2014

For a positive integer n, let f(n) denote the smallest non-negative integer b such that for each system S \subseteq {x_k=1,x_i+x_j=x_k,x_i*x_j=x_k: i,j,k \in {1,...,n}} with a solution in non-negative integers x_1,...,x_n, there exists a solution of S in {0,...,b}^n. We prove that the function f is strictly increasing and dominates all computable functions. We present an infinite loop in MuPAD which takes as input a positive integer n and returns a non-negative integer on each iteration. Let g(n,m) denote the number returned on the m-th iteration, if n is taken as input. Then, g(n,m) \leq m-1, 0=g(n,1)<1=g(n,2) \leq g(n,3) \leq g(n,4) \leq ... and g(n,f(n))<f(n)=g(n,f(n)+1)=g(n,f(n)+2)=g(n,f(n)+3)=.... A MuPAD code constructed on another principle contains a repeat-until loop and implements a limit-computable function ξ: N-->N that cannot be bounded by any computable function. This code takes as input a non-negative integer n, immediately returns 0, and computes a system S of polynomial equations. If the loop terminates for S, then the next instruction is executed and returns ξ(n).
Pulse-Doppler Signal Processing with Quadrature Compressive Sampling
Venue: arXiv cs.IT 2014
Year: 2014

Quadrature compressive sampling (QuadCS) is a newly introduced sub-Nyquist sampling for acquiring inphase and quadrature (I/Q) components of radio-frequency signals. For applications to pulse-Doppler radars, the QuadCS outputs can be arranged in 2-dimensional data similar to that by Nyquist sampling. This paper develops a compressive sampling pulse-Doppler (CoSaPD) processing scheme from the sub-Nyquist samples. The CoSaPD scheme follows Doppler estimation/detection and range estimation and is conducted on the sub-Nyquist samples without recovering the Nyquist samples. The Doppler estimation is realized through spectrum analyzer as in classic processing. The detection is done on the Doppler bin data. The range estimation is performed through sparse recovery algorithms on the detected targets and thus the computational load is reduced. The detection threshold can be set at a low value for improving detection probability and then the introduced false targets are removed in the range estimation stage through inherent detection characteristic in the recovery algorithms. Simulation results confirm our findings. The CoSaPD scheme with the data at one eighth the Nyquist rate and for SNR above -25dB can achieve performance of the classic processing with Nyquist samples.