OpenRaiser/Intern-Atlas huggingface dataset:
The number and degree distribution of spanning trees in the Tower of Hanoi graph
Venue: arXiv cs.DM 2015
Year: 2015

The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the num- ber and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.
iCellular: Define Your Own Cellular Network Access on Commodity Smartphones
Venue: arXiv cs.NI 2015
Year: 2015

Leveraging multi-carrier access offers a promising approach to boosting access quality in mobile networks. However, our experiments show that the potential benefits are hard to fulfill due to fundamental limitations in the network-controlled design. To overcome these limitations, we propose iCellular, which allows users to define and intelligently select their own cellular network access from multiple carriers. iCellular reuses the existing device-side mechanisms and the standard cellular network procedure, but leverages the end device's intelligence to be proactive and adaptive in multi-carrier selection. It performs adaptive monitoring to ensure responsive selection and minimal service disruption, and enhances carrier selection with online learning and runtime decision fault prevention. It is deployable on commodity phones without any infrastructure/hardware change. We implement iCellular on commodity Nexus 6 phones and leverage Google Project-Fi's efforts to test multi-carrier access among two top US carriers: T-Mobile and Sprint. Our experiments confirm that iCellular helps users with up to 3.74x throughput improvement (7x suspension and 1.9x latency reduction) over the state-of-art selection. Moreover, iCellular locates the best-quality carrier in most cases, with negligible overhead on CPU, memory and energy consumption.
Type-Directed Synthesis of Products
Venue: arXiv cs.PL 2015
Year: 2015

Software synthesis - the process of generating complete, general-purpose programs from specifications - has become a hot research topic in the past few years. For decades the problem was thought to be insurmountable: the search space of possible programs is far too massive to efficiently traverse. Advances in efficient constraint solving have overcome this barrier, enabling a new generation of effective synthesis systems. Most existing systems compile synthesis tasks down to low-level SMT instances, sacrificing high-level semantic information while solving only first-order problems (i.e., filling integer holes). Recent work takes an alternative approach, using the Curry-Howard isomorphism and techniques from automated theorem proving to construct higher-order programs with algebraic datatypes. My thesis involved extending this type-directed synthesis engine to handle product types, which required significant modifications to both the underlying theory and the tool itself. Product types streamline other language features, eliminating variable-arity constructors among other workarounds employed in the original synthesis system. A form of logical conjunction, products are invertible, making it possible to equip the synthesis system with an efficient theorem-proving technique called focusing that eliminates many of the nondeterministic choices inherent in proof search. These theoretical enhancements informed a new version of the type-directed synthesis prototype implementation, which remained performance-competitive with the original synthesizer. A significant advantage of the type-directed synthesis framework is its extensibility; this thesis is a roadmap for future such efforts to increase the expressive power of the system.
Spectrally and Energy Efficient OFDM (SEE-OFDM) for Intensity Modulated Optical Wireless Systems
Venue: arXiv cs.IT 2015
Year: 2015

Spectrally and energy efficient orthogonal frequency division multiplexing (SEE-OFDM) is an optical OFDM technique based on combining multiple asymmetrically clipped optical OFDM (ACO-OFDM) signals into one OFDM signal. By summing different components together, SEE-OFDM can achieve the same spectral efficiency as DC-biased optical OFDM (DCO-OFDM) without an energy-inefficient DC-bias. This paper introduces multiple methods for decoding a SEE-OFDM symbol and shows that an iterative decoder with hard decisions gives the best performance. Being a multi-component format, different energy allocation amongst the different components of SEE-OFDM is possible. However, equal energy allocation performs 1.5 dB better than unequal energy allocation. A hard-decision, iterative subtraction receiver can further increase performance by another 1.5 dB over soft-decision subtraction and reconstruction receivers. SEE-OFDM consistently performs 3 dB or better and with higher spectral efficiency than ACO-OFDM at the same bit-error-rate (BER). Comparing other combination methods at the same BER, SEE-OFDM performs up to 3 dB better than hybrid asymmetrically clipped optical (OFDM) (HACO-OFDM) and up to 1.5 dB better than asymmetrically and symmetrically clipped optical OFDM (ASCO-OFDM) and enhanced unipolar OFDM (eU-OFDM) when using hard decisions at the receiver. Additionally, SEE-OFDM has the best peak-to-average-power rate (PAPR) as compared to the other combination OFDM formats and ACO-OFDM, which makes it excellent for any range limited optical source, such as laser diodes and light-emitting diodes (LEDs). In summary, SEE-OFDM is shown to have excellent properties to glean additional capacity from an intensity modulation and direct detection (IM/DD) optical wireless communications system.
Graph properties in node-query setting: effect of breaking symmetry
Venue: arXiv cs.CC 2015
Year: 2015

The query complexity of graph properties is well-studied when queries are on edges. We investigate the same when queries are on nodes. In this setting a graph $G = (V, E)$ on $n$ vertices and a property $\mathcal{P}$ are given. A black-box access to an unknown subset $S \subseteq V$ is provided via queries of the form `Does $i \in S$?'. We are interested in the minimum number of queries needed in worst case in order to determine whether $G[S]$, the subgraph of $G$ induced on $S$, satisfies $\mathcal{P}$. Apart from being combinatorially rich, this setting allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on hereditary graph properties. The monotone functions in the node-query setting translate precisely to the hereditary graph properties. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on $G$, namely that of vertex-transitivity, the query complexity for any hereditary graph property in our setting is the worst possible, i.e., $n$. We show that in the absence of any symmetry on $G$ it can fall as low as $O(n^{1/(d + 1) })$ where $d$ denotes the minimum possible degree of a minimal forbidden sub-graph for $\mathcal{P}$. In particular, every hereditary property benefits at least quadratically. The main question left open is: can it go exponentially low for some hereditary property? We show that the answer is no for any hereditary property with {finitely many} forbidden subgraphs by exhibiting a bound of $Ω(n^{1/k})$ for some constant $k$ depending only on the property. For general ones we rule out the possibility of the query complexity falling down to constant by showing $Ω(\log n/ \log \log n)$ bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdös and Rado.
Approximate Association via Dissociation
Venue: arXiv cs.DS 2015
Year: 2015

A vertex set $X$ of a graph $G$ is an association set if each component of $G - X$ is a clique, or a dissociation set if each component of $G - X$ is a single vertex or a single edge. Interestingly, $G - X$ is then precisely a graph containing no induced $P_3$'s or containing no $P_3$'s, respectively. We observe some special structures and show that if none of them exists, then the minimum association set problem can be reduced to the minimum (weighted) dissociation set problem. This yields the first nontrivial approximation algorithm for association set, and its approximation ratio is 2.5, matching the best result of the closely related cluster editing problem. The reduction is based on a combinatorial study of modular decomposition of graphs free of these special structures. Further, a novel algorithmic use of modular decomposition enables us to implement this approach in $O(m n + n^2)$ time.
Fast k-best Sentence Compression
Venue: arXiv cs.CL 2015
Year: 2015

A popular approach to sentence compression is to formulate the task as a constrained optimization problem and solve it with integer linear programming (ILP) tools. Unfortunately, dependence on ILP may make the compressor prohibitively slow, and thus approximation techniques have been proposed which are often complex and offer a moderate gain in speed. As an alternative solution, we introduce a novel compression algorithm which generates k-best compressions relying on local deletion decisions. Our algorithm is two orders of magnitude faster than a recent ILP-based method while producing better compressions. Moreover, an extensive evaluation demonstrates that the quality of compressions does not degrade much as we move from single best to top-five results.
MUSAN: A Music, Speech, and Noise Corpus
Venue: arXiv cs.SD 2015
Year: 2015

This report introduces a new corpus of music, speech, and noise. This dataset is suitable for training models for voice activity detection (VAD) and music/speech discrimination. Our corpus is released under a flexible Creative Commons license. The dataset consists of music from several genres, speech from twelve languages, and a wide assortment of technical and non-technical noises. We demonstrate use of this corpus for music/speech discrimination on Broadcast news and VAD for speaker identification.
Low-Complexity Channel Reconstruction Methods Based on SVD-ZF Precoding in Massive 3D-MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the low-complexity channel reconstruction methods for downlink precoding in massive multiple-Input multiple-Output (MIMO) systems. When the user is allocated less streams than the number of its antennas, the base station (BS) or user usually utilizes the singular value decomposition (SVD) to get the effective channels, whose dimension is equal to the number of streams. This process is called channel reconstruction and done in BS for time division duplex (TDD) mode. However, with the increasing of antennas in BS, the computation burden of SVD is getting incredible. Here, we propose a series of novel low-complexity channel reconstruction methods for downlink precoding in 3D spatial channel model. We consider different correlations between elevation and azimuth antennas, and divide the large dimensional matrix SVD into two kinds of small-size matrix SVD. The simulation results show that the proposed methods only produce less than 10% float computation than the traditional SVD zero-forcing (SVD-ZF) precoding method, while keeping nearly the same performance of 1Gbps.
The Singular Value Decomposition, Applications and Beyond
Venue: arXiv cs.LG 2015
Year: 2015

The singular value decomposition (SVD) is not only a classical theory in matrix computation and analysis, but also is a powerful tool in machine learning and modern data analysis. In this tutorial we first study the basic notion of SVD and then show the central role of SVD in matrices. Using majorization theory, we consider variational principles of singular values and eigenvalues. Built on SVD and a theory of symmetric gauge functions, we discuss unitarily invariant norms, which are then used to formulate general results for matrix low rank approximation. We study the subdifferentials of unitarily invariant norms. These results would be potentially useful in many machine learning problems such as matrix completion and matrix data classification. Finally, we discuss matrix low rank approximation and its recent developments such as randomized SVD, approximate matrix multiplication, CUR decomposition, and Nystrom approximation. Randomized algorithms are important approaches to large scale SVD as well as fast matrix computations.
On the Covering Radius of the Second Order Reed-Muller Code of Length 128
Venue: arXiv cs.IT 2015
Year: 2015

In 1981, Schatz proved that the covering radius of the binary Reed-Muller code $RM(2,6)$ is 18. For $RM(2,7)$, we only know that its covering radius is between 40 and 44. In this paper, we prove that the covering radius of the binary Reed-Muller code $RM(2,7)$ is at most 42. Moreover, we give a sufficient and necessary condition for Boolean functions of 7-variable to achieve the second-order nonlinearity 42.
Privacy Prediction of Images Shared on Social Media Sites Using Deep Features
Venue: arXiv cs.CV 2015
Year: 2015

Online image sharing in social media sites such as Facebook, Flickr, and Instagram can lead to unwanted disclosure and privacy violations, when privacy settings are used inappropriately. With the exponential increase in the number of images that are shared online every day, the development of effective and efficient prediction methods for image privacy settings are highly needed. The performance of models critically depends on the choice of the feature representation. In this paper, we present an approach to image privacy prediction that uses deep features and deep image tags as feature representations. Specifically, we explore deep features at various neural network layers and use the top layer (probability) as an auto-annotation mechanism. The results of our experiments show that models trained on the proposed deep features and deep image tags substantially outperform baselines such as those based on SIFT and GIST as well as those that use "bag of tags" as features.
$\mathbb{Z}_p\mathbb{Z}_p[u]$-additive codes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study $\mathbb{Z}_p\mathbb{Z}_p[u]$-additive codes, where $p$ is prime and $u^{2}=0$. In particular, we determine a Gray map from $ \mathbb{Z}_p\mathbb{Z}_p[u]$ to $\mathbb{Z}_p^{ α+2 β}$ and study generator and parity check matrices for these codes. We prove that a Gray map $Φ$ is a distance preserving map from ($\mathbb{Z}_p\mathbb{Z}_p[u]$,Gray distance) to ($\mathbb{Z}_p^{α+2β}$,Hamming distance), it is a weight preserving map as well. Furthermore we study the structure of $\mathbb{Z}_p\mathbb{Z}_p[u]$-additive cyclic codes.
Close Communication and 2-Clubs in Corporate Networks: Europe 2010
Venue: arXiv cs.SI 2015
Year: 2015

Corporate networks, as induced by interlocking directorates between corporations, provide structures of personal communication at the level of their boards. This paper studies such networks from a perspective of close communication in sub-networks, where each pair of nodes (boards of a corporation) are either neighbours, or have a common neighbour. These correspond to subgraphs of diameter at most 2, designated by us earlier as 2-clubs, with three types (coteries, social circles and hamlets) as degrees of close communication in social networks, within the concept of boroughs of a network. Boroughs are maximal areas and containers of close communication between nodes of a network. This framework is applied in this paper to an analysis of corporate board interlocks between the top 300 European corporations 2010, as studied by Heemkerk (2013), with data provided by him for that purpose. The paper gives results for several perspectives of close communication in the European corporate network of 2010, a year close to the global crash of 2008, as a further elaboration of those given in Heemskerk (2013).
Regression for citation data: An evaluation of different methods
Venue: arXiv cs.DL 2015
Year: 2015

Citations are increasingly used for research evaluations. It is therefore important to identify factors affecting citation scores that are unrelated to scholarly quality or usefulness so that these can be taken into account. Regression is the most powerful statistical technique to identify these factors and hence it is important to identify the best regression strategy for citation data. Citation counts tend to follow a discrete lognormal distribution and, in the absence of alternatives, have been investigated with negative binomial regression. Using simulated discrete lognormal data (continuous lognormal data rounded to the nearest integer) this article shows that a better strategy is to add one to the citations, take their log and then use the general linear (ordinary least squares) model for regression (e.g., multiple linear regression, ANOVA), or to use the generalised linear model without the log. Reasonable results can also be obtained if all the zero citations are discarded, the log is taken of the remaining citation counts and then the general linear model is used, or if the generalised linear model is used with the continuous lognormal distribution. Similar approaches are recommended for altmetric data, if it proves to be lognormally distributed.
Distributions for cited articles from individual subjects and years
Venue: arXiv cs.DL 2015
Year: 2015

The citations to a set of academic articles are typically unevenly shared, with many articles attracting few citations and few attracting many. It is important to know more precisely how citations are distributed in order to help statistical analyses of citations, especially for sets of articles from a single discipline and a small range of years, as normally used for research evaluation. This article fits discrete versions of the power law, the lognormal distribution and the hooked power law to 20 different Scopus categories, using citations to articles published in 2004 and ignoring uncited articles. The results show that, despite its popularity, the power law is not a suitable model for collections of articles from a single subject and year, even for the purpose of estimating the slope of the tail of the citation data. Both the hooked power law and the lognormal distributions fit best for some subjects but neither is a universal optimal choice and parameter estimates for both seem to be unreliable. Hence only the hooked power law and discrete lognormal distributions should be considered for subject-and-year-based citation analysis in future and parameter estimates should always be interpreted cautiously.
Stability analysis of semiconductor manufacturing process with EWMA run-to-run controllers
Venue: arXiv cs.SY 2015
Year: 2015

In the semiconductor manufacturing batch processes, each step is a complicated physiochemical batch process; generally it is difficult to perform measurements online or carry out the measurement for each run, and hence there will be delays in the feedback of the system. The effect of the delay on the stability of the system is an important issue which needs to be understood. Based on the exponentially weighted moving average (EWMA) algorithm, we propose two kinds of controllers, EWMA-I and II controllers for single product process and mixed product process in semiconductor manufacturing in this paper. For the single product process, the stabilities of systems with both controllers which undergo different kinds of metrology delays are investigated. Necessary and sufficient conditions for the stochastic stability are established. Routh-Hurwitz criterion and Lyapunov's direct method are used to obtain the stability regions for the system with fixed metrology delay. By using Lyapunov's direct method, the stability region is established for the system with fixed sampling metrology and with stochastic metrology delay. We also extended the theorems of single product process to mixed product process. Based on the proposed theorems, some numerical examples are provided to illustrate the stability of the delay system.
PSD estimation in Beamspace for Estimating Direct-to-Reverberant Ratio from A Reverberant Speech Signal
Venue: arXiv cs.SD 2015
Year: 2015

A method for estimation of direct-to-reverberant ratio (DRR) using a microphone array is proposed. The proposed method estimates the power spectral density (PSD) of the direct sound and the reverberation using the algorithm \textit{PSD estimation in beamspace} with a microphone array and calculates the DRR of the observed signal. The speech corpus of the ACE (Acoustic Characterisation of Environments) Challenge was utilised for evaluating the practical feasibility of the proposed method. The experimental results revealed that the proposed method was able to effectively estimate the DRR from a recording of a reverberant speech signal which included various environmental noise.
Asynchronous Parallel Computing Algorithm implemented in 1D Heat Equation with CUDA
Venue: arXiv cs.DC 2015
Year: 2015

In this note, we present the stability as well as performance analysis of asynchronous parallel computing algorithm implemented in 1D heat equation with CUDA. The primary objective of this note lies in dissemination of asynchronous parallel computing algorithm by providing CUDA code for fast and easy implementation. We show that the simulations carried out on nVIDIA GPU device with asynchronous scheme outperforms synchronous parallel computing algorithm. In addition, we also discuss some drawbacks of asynchronous parallel computing algorithms.
Enabling Learning by Teaching: Intuitive Composing of E-Learning Modules
Venue: arXiv cs.CY 2015
Year: 2015

In an effort to foster learning by teaching, we propose the development of a canvas system that makes composing e-learning modules intuitive. We try to empower and liberate non-technical module users by lowering the bar for turning them into module authors, a bar previously set far too high. In turn, this stimulates learning through teaching. By making a damn fine piece of software, we furthermore make module authoring more pleasant for experienced authors as well. We propose a system that initially enables users to easily compose H5P modules. These modules are successively easy to share and modify. Through gamification we encourage authors to share their work, and to improve the works of others.
Subsampling in Smoothed Range Spaces
Venue: arXiv cs.CG 2015
Year: 2015

We consider smoothed versions of geometric range spaces, so an element of the ground set (e.g. a point) can be contained in a range with a non-binary value in $[0,1]$. Similar notions have been considered for kernels; we extend them to more general types of ranges. We then consider approximations of these range spaces through $\varepsilon $-nets and $\varepsilon $-samples (aka $\varepsilon$-approximations). We characterize when size bounds for $\varepsilon $-samples on kernels can be extended to these more general smoothed range spaces. We also describe new generalizations for $\varepsilon $-nets to these range spaces and show when results from binary range spaces can carry over to these smoothed ones.