OpenRaiser/Intern-Atlas huggingface dataset:
Heat kernel based community detection
Venue: arXiv cs.SI 2016
Year: 2016

The heat kernel is a particular type of graph diffusion that, like the much-used personalized PageRank diffusion, is useful in identifying a community nearby a starting seed node. We present the first deterministic, local algorithm to compute this diffusion and use that algorithm to study the communities that it produces. Our algorithm is formally a relaxation method for solving a linear system to estimate the matrix exponential in a degree-weighted norm. We prove that this algorithm stays localized in a large graph and has a worst-case constant runtime that depends only on the parameters of the diffusion, not the size of the graph. Our experiments on real-world networks indicate that the communities produced by this method have better conductance than those produced by PageRank, although they take slightly longer to compute on large graphs. On a real-world community identification task, the heat kernel communities perform better than those from the PageRank diffusion.
Online Square-into-Square Packing
Venue: arXiv cs.DM 2016
Year: 2016

In 1967, Moon and Moser proved a tight bound on the critical density of squares in squares: any set of squares with a total area of at most 1/2 can be packed into a unit square, which is tight. The proof requires full knowledge of the set, as the algorithmic solution consists in sorting the objects by decreasing size, and packing them greedily into shelves. Since then, the online version of the problem has remained open; the best upper bound is still 1/2, while the currently best lower bound is 1/3, due to Han et al. (2008). In this paper, we present a new lower bound of 11/32, based on a dynamic shelf allocation scheme, which may be interesting in itself. We also give results for the closely related problem in which the size of the square container is not fixed, but must be dynamically increased in order to ac- commodate online sequences of objects. For this variant, we establish an upper bound of 3/7 for the critical density, and a lower bound of 1/8. When aiming for accommodating an online sequence of squares, this corresponds to a 2.82...- competitive method for minimizing the required container size, and a lower bound of 1.33 . . . for the achievable factor.
Joins via Geometric Resolutions: Worst-case and Beyond
Venue: arXiv cs.DB 2016
Year: 2016

We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes classical and recent worst-case algorithmic results on computing joins. In addition, we use our framework and the same algorithm to show a series of what are colloquially known as beyond worst-case results. The framework allows us to prove results for data stored in Btrees, multidimensional data structures, and even multiple indices per table. A key idea in our framework is formalizing the inference one does with an index as a type of geometric resolution; transforming the algorithmic problem of computing joins to a geometric problem. Our notion of geometric resolution can be viewed as a geometric analog of logical resolution. In addition to the geometry and logic connections, our algorithm can also be thought of as backtracking search with memoization.
Ornstein Isomorphism and Algorithmic Randomness
Venue: arXiv cs.IT 2016
Year: 2016

In 1970, Donald Ornstein proved a landmark result in dynamical systems, viz., two Bernoulli systems with the same entropy are isomorphic except for a measure 0 set. Keane and Smorodinsky gave a finitary proof of this result. They also indicated how one can generalize the result to mixing Markov Shifts. We adapt their construction to show that if two computable mixing Markov systems have the same entropy, then there is a layerwise computable isomorphism defined on all Martin-Lof random points in the system. Since the set of Martin-Lof random points forms a measure 1 set, it implies the classical result for such systems. This result uses several recent developments in computable analysis and algorithmic randomness. Following the work by Braverman, Nandakumar, and Hoyrup and Rojas introduced discontinuous functions into the study of algorithmic randomness. We utilize Hoyrup and Rojas' elegant notion of layerwise computable functions to produce the test of randomness in our result. Further, we use the recent result of the effective Shannon-McMillan-Breiman theorem, independently established by Hochman and Hoyrup to prove the properties of our construction. We show that the result cannot be improved to include all points in the systems - only trivial computable isomorphisms exist between systems with the same entropy.
A Stochastic Temporal Model of Polyphonic MIDI Performance with Ornaments
Venue: arXiv cs.AI 2016
Year: 2016

We study indeterminacies in realization of ornaments and how they can be incorporated in a stochastic performance model applicable for music information processing such as score-performance matching. We point out the importance of temporal information, and propose a hidden Markov model which describes it explicitly and represents ornaments with several state types. Following a review of the indeterminacies, they are carefully incorporated into the model through its topology and parameters, and the state construction for quite general polyphonic scores is explained in detail. By analyzing piano performance data, we find significant overlaps in inter-onset-interval distributions of chordal notes, ornaments, and inter-chord events, and the data is used to determine details of the model. The model is applied for score following and offline score-performance matching, yielding highly accurate matching for performances with many ornaments and relatively frequent errors, repeats, and skips.
Efficient Advert Assignment
Venue: arXiv cs.GT 2016
Year: 2016

We develop a framework for the analysis of large-scale Ad-auctions where adverts are assigned over a continuum of search types. For this pay-per-click market, we provide an efficient mechanism that maximizes social welfare. In particular, we show that the social welfare optimization can be solved in separate optimizations conducted on the time-scales relevant to the search platform and advertisers. Here, on each search occurrence, the platform solves an assignment problem and, on a slower time-scale, each advertiser submits a bid which matches its demand for click-throughs with supply. Importantly, knowledge of global parameters, such as the distribution of search terms, is not required when separating the problem in this way. Exploiting the information asymmetry between the platform and advertiser, we describe a simple mechanism which incentivizes truthful bidding and has a unique Nash equilibrium that is socially optimal, and thus implements our decomposition. Further, we consider models where advertisers adapt their bids smoothly over time, and prove convergence to the solution that maximizes social welfare. Finally, we describe several extensions which illustrate the flexibility and tractability of our framework.
Technical Report : ContikiMAC vs X-MAC performance analysis
Venue: arXiv cs.NI 2016
Year: 2016

This paper try to better understand the performance of ContikiMAC compared to X-MAC. ContikiMAC achieves a transmission by repeatedly transmitting a data packet until the reception of an ACK from the destination. While X-MAC uses a stream of small size strobes to advertise the destination of the incoming transmission. A priori, X-MAC is then less bandwidth consumptive. To better understand the efficiency of ContikiMAC, despite an intuitively more consumptive transmitting procedure, we have compared this protocol to an updated version of X-MAC which has been designed with the goal to obtain a more objective comparison. At our best knowledge, this kind of "objective" and detailed analysis has never been produced. Both protocols performances are evaluated in terms of number of retransmissions, latency, packet delivery ratio (PDR) and duty-cycle. Our study reveals that the combination of the fast-sleep optimization shortening the wake-up period with a transmission procedure more efficient helps ContikiMAC to obtain a better PDR at the cost of a reduced latency and energy consumption.
Deciphering a novel image cipher based on mixed transformed Logistic maps
Venue: arXiv cs.CR 2016
Year: 2016

Since John von Neumann suggested utilizing Logistic map as a random number generator in 1947, a great number of encryption schemes based on Logistic map and/or its variants have been proposed. This paper re-evaluates the security of an image cipher based on transformed logistic maps and proves that the image cipher can be deciphered efficiently under two different conditions: 1) two pairs of known plain-images and the corresponding cipher-images with computational complexity of $O(2^{18}+L)$; 2) two pairs of chosen plain-images and the corresponding cipher-images with computational complexity of $O(L)$, where $L$ is the number of pixels in the plain-image. In contrast, the required condition in the previous deciphering method is eighty-seven pairs of chosen plain-images and the corresponding cipher-images with computational complexity of $O(2^{7}+L)$. In addition, three other security flaws existing in most Logistic-map-based ciphers are also reported.
Online Bin Stretching with Three Bins
Venue: arXiv cs.DS 2016
Year: 2016

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of $11/8 = 1.375$ for three bins. Additionally, we present a lower bound of $45/33 = 1.\overline{36}$ for Online Bin Stretching on three bins and a lower bound of $19/14$ for four and five bins that were discovered using a computer search.
Automata in SageMath---Combinatorics meet Theoretical Computer Science
Venue: arXiv cs.FL 2016
Year: 2016

The new finite state machine package in the mathematics software system SageMath is presented and illustrated by many examples. Several combinatorial problems, in particular digit problems, are introduced, modeled by automata and transducers and solved using SageMath. In particular, we compute the asymptotic Hamming weight of a non-adjacent-form-like digit expansion, which was not known before.
Blind MIMOME Wiretap Channel with Delayed CSIT
Venue: arXiv cs.IT 2016
Year: 2016

We study the Gaussian MIMOME wiretap channel where a transmitter wishes to communicate a confidential message to a legitimate receiver in the presence of eavesdroppers, while the eavesdroppers should not be able to decode the confidential message. Each node in the network is equipped with arbitrary number of antennas. Furthermore, channels are time varying, and there is no channel state information available at the transmitter (CSIT) with respect to eavesdroppers' channels; and transmitter only has access to delayed CSIT of the channel to the legitimate receiver. The secure degrees of freedom (SDoF) for such network has only been characterized for special cases, and is unknown in general. We completely characterize the SDoF of this network for all antenna configurations. In particular, we strictly improve the state-of-the-art achievable scheme for this network by proposing more efficient artificial noise alignment at the receivers. Furthermore, we develop a tight upper bound by utilizing 4 important inequalities that provide lower bounds on the received signal dimensions at receivers which supply delayed CSIT or no CSIT, or at a collection of receivers where some supply no CSIT. These inequalities together allow for analysis of signal dimensions in networks with asymmetric CSIT; and as a result, we present a converse proof that leads to characterization of SDoF for all possible antenna configurations.
Mending the Big-Data Missing Information
Venue: arXiv cs.OH 2016
Year: 2016

Consider a high-dimensional data set, in which for every data-point there is incomplete information. Each object in the data set represents a real entity, which is described by a point in high-dimensional space. We model the lack of information for a given object as an affine subspace in $\mathbb{R}^d$ whose dimension $k$ is the number of missing features. Our goal in this study is to find clusters of objects where the main problem is to cope with partial information and high dimension. Assuming the data set is separable, namely, its emergence from clusters that can be modeled as a set of disjoint ball in $\mathbb{R}^d$, we suggest a simple data clustering algorithm. Our suggested algorithm use the affine subspaces minimum distance and calculates pair-wise projection of the data achieving poly-logarithmic time complexity. We use probabilistic considerations to prove the algorithm's correctness. These probabilistic results are of independent interest, and can serve to better understand the geometry of high dimensional objects.
Sampling and Distortion Tradeoffs for Bandlimited Periodic Signals
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the optimal sampling strategies (uniform or nonuniform) and distortion tradeoffs for Gaussian bandlimited periodic signals with additive white Gaussian noise are studied. Our emphasis is on characterizing the optimal sampling locations as well as the optimal pre-sampling filter to minimize the reconstruction distortion. We first show that to achieve the optimal distortion, no pre-sampling filter is necessary for any arbitrary sampling rate. Then, we provide a complete characterization of optimal distortion for low and high sampling rates (with respect to the signal bandwidth). We also provide bounds on the reconstruction distortion for rates in the intermediate region. It is shown that nonuniform sampling outperforms uniform sampling for low sampling rates. In addition, the optimal nonuniform sampling set is robust with respect to missing sampling values. On the other hand, for the sampling rates above the Nyquist rate, the uniform sampling strategy is optimal. An extension of the results for random discrete periodic signals is discussed with simulation results indicating that the intuitions from the continuous domain carry over to the discrete domain. Sparse signals are also considered, where it is shown that uniform sampling is optimal above the Nyquist rate.
Distributed noise-shaping quantization: I. Beta duals of finite frames and near-optimal quantization of random measurements
Venue: arXiv cs.IT 2016
Year: 2016

This paper introduces a new algorithm for the so-called "Analysis Problem" in quantization of finite frame representations which provides a near-optimal solution in the case of random measurements. The main contributions include the development of a general quantization framework called distributed noise-shaping, and in particular, beta duals of frames, as well as the performance analysis of beta duals in both deterministic and probabilistic settings. It is shown that for random frames, using beta duals results in near-optimally accurate reconstructions with respect to both the frame redundancy and the number of levels that the frame coefficients are quantized at. More specifically, for any frame $E$ of $m$ vectors in $\mathbb{R}^k$ except possibly from a subset of Gaussian measure exponentially small in $m$ and for any number $L \geq 2$ of quantization levels per measurement to be used to encode the unit ball in $\mathbb{R}^k$, there is an algorithmic quantization scheme and a dual frame together which guarantee a reconstruction error of at most $\sqrt{k}L^{-(1-η)m/k}$, where $η$ can be arbitrarily small for sufficiently large problems. Additional features of the proposed algorithm include low computational cost and parallel implementability.
Role Discovery in Networks
Venue: arXiv cs.SI 2016
Year: 2016

Roles represent node-level connectivity patterns such as star-center, star-edge nodes, near-cliques or nodes that act as bridges to different regions of the graph. Intuitively, two nodes belong to the same role if they are structurally similar. Roles have been mainly of interest to sociologists, but more recently, roles have become increasingly useful in other domains. Traditionally, the notion of roles were defined based on graph equivalences such as structural, regular, and stochastic equivalences. We briefly revisit these early notions and instead propose a more general formulation of roles based on the similarity of a feature representation (in contrast to the graph representation). This leads us to propose a taxonomy of three general classes of techniques for discovering roles that includes (i) graph-based roles, (ii) feature-based roles, and (iii) hybrid roles. We also propose a flexible framework for discovering roles using the notion of similarity on a feature-based representation. The framework consists of two fundamental components: (a) role feature construction and (b) role assignment using the learned feature representation. We discuss the different possibilities for discovering feature-based roles and the tradeoffs of the many techniques for computing them. Finally, we discuss potential applications and future directions and challenges.
Conformant Planning as a Case Study of Incremental QBF Solving
Venue: arXiv cs.LO 2016
Year: 2016

We consider planning with uncertainty in the initial state as a case study of incremental quantified Boolean formula (QBF) solving. We report on experiments with a workflow to incrementally encode a planning instance into a sequence of QBFs. To solve this sequence of incrementally constructed QBFs, we use our general-purpose incremental QBF solver DepQBF. Since the generated QBFs have many clauses and variables in common, our approach avoids redundancy both in the encoding phase and in the solving phase. Experimental results show that incremental QBF solving outperforms non-incremental QBF solving. Our results are the first empirical study of incremental QBF solving in the context of planning and motivate its use in other application domains.
Superconcentrators of Density 25.3
Venue: arXiv cs.DM 2016
Year: 2016

An $N$-superconcentrator is a directed, acyclic graph with $N$ input nodes and $N$ output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density $25.3$ (where the density is the number of edges divided by $N$). The previously best known densities were $28$ \cite{Scho2006} and $27.4136$ \cite{YuanK12}.
Error Decay of (almost) Consistent Signal Estimations from Quantized Gaussian Random Projections
Venue: arXiv cs.IT 2016
Year: 2016

This paper provides new error bounds on "consistent" reconstruction methods for signals observed from quantized random projections. Those signal estimation techniques guarantee a perfect matching between the available quantized data and a new observation of the estimated signal under the same sensing model. Focusing on dithered uniform scalar quantization of resolution $δ>0$, we prove first that, given a Gaussian random frame of $\mathbb R^N$ with $M$ vectors, the worst-case $\ell_2$-error of consistent signal reconstruction decays with high probability as $O(\frac{N}{M}\log\frac{M}{\sqrt N})$ uniformly for all signals of the unit ball $\mathbb B^N \subset \mathbb R^N$. Up to a log factor, this matches a known lower bound in $Ω(N/M)$ and former empirical validations in $O(N/M)$. Equivalently, if $M$ exceeds a minimal number of frame coefficients growing like $O(\frac{N}{ε_0}\log \frac{\sqrt N}{ε_0})$, any vectors in $\mathbb B^N$ with $M$ identical quantized projections are at most $ε_0$ apart with high probability. Second, in the context of Quantized Compressed Sensing with $M$ Gaussian random measurements and under the same scalar quantization scheme, consistent reconstructions of $K$-sparse signals of $\mathbb R^N$ have a worst-case error that decreases with high probability as $O(\tfrac{K}{M}\log\tfrac{MN}{\sqrt K^3})$ uniformly for all such signals. Finally, we show that the proximity of vectors whose quantized random projections are only approximately consistent can still be bounded with high probability. A certain level of corruption is thus allowed in the quantization process, up to the appearance of a systematic bias in the reconstruction error of (almost) consistent signal estimates.
Uniform definition of comparable and searchable information on the web
Venue: arXiv cs.IR 2016
Year: 2016

Basically information means selection within a domain (value or definition set) of possibilities. For objectifiable, comparable and precise information the domain should be the same for all. Therefore the global (online) definition of the domain is proposed here. It is advantageous to define an ordered domain, because this allows using numbers for addressing the elements and because nature is ordered in many respects. The original data can be ordered in multiple independent ways. We can define a domain with multiple independent numeric dimensions to reflect this. Because we want to search information in the domain, for quantification of similarity we define a distance function or metric. Therefore we propose "Domain Spaces" (DSs) which are online defined nestable metric spaces. Their elements are called "Domain Vectors" (DVs) and have the simple form: URL (of common DS definition) plus sequence of numbers At this the sequence must be given so that the mapping of numbers to the DS dimensions is clear. By help of appropriate software DVs can be represented e.g. as words and numbers. Compared to words, however, DVs have (as original information) important objectifiable advantages (clear definition, objectivity, information content, range, resolution, efficiency, searchability). Using DSs users can define which information they make searchable and how it is searchable. DSs can be also used to make quantitative (numeric) data as uniform DVs interoperable, comparable and searchable. The approach is demonstrated in an online database with search engine (http://NumericSearch.com). The search procedure is called "Numeric Search". It consists of two systematic steps: 1. Selection of the appropriate DS e.g. by conventional word based search within the DS definitions. 2. Range and/or similarity search of DVs in the selected DS.
Budget-Constrained Item Cold-Start Handling in Collaborative Filtering Recommenders via Optimal Design
Venue: arXiv cs.IR 2016
Year: 2016

It is well known that collaborative filtering (CF) based recommender systems provide better modeling of users and items associated with considerable rating history. The lack of historical ratings results in the user and the item cold-start problems. The latter is the main focus of this work. Most of the current literature addresses this problem by integrating content-based recommendation techniques to model the new item. However, in many cases such content is not available, and the question arises is whether this problem can be mitigated using CF techniques only. We formalize this problem as an optimization problem: given a new item, a pool of available users, and a budget constraint, select which users to assign with the task of rating the new item in order to minimize the prediction error of our model. We show that the objective function is monotone-supermodular, and propose efficient optimal design based algorithms that attain an approximation to its optimum. Our findings are verified by an empirical study using the Netflix dataset, where the proposed algorithms outperform several baselines for the problem at hand.