OpenRaiser/Intern-Atlas huggingface dataset:
Fully Dynamic Bin Packing Revisited
Venue: arXiv cs.DS 2015
Year: 2015

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ration of $1 + ε$ for the number of bins, a relatively simple argument proves a lower bound of $Ω(\frac{1}ε)$ for the migration factor. We establish a nearly matching upper bound of $O(\frac{1}ε^4 \log \frac{1}ε)$ using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items $n$ and in $\frac{1}ε$. The previous best trade-off was for an asymptotic competitive ratio of $\frac{5}{4}$ for the bins (rather than $1+ε$) and needed an amortized number of $O(\log n)$ repackings (while in our scheme the number of repackings is independent of $n$ and non-amortized).
How to Elect a Leader Faster than a Tournament
Venue: arXiv cs.DC 2015
Year: 2015

The problem of electing a leader from among $n$ contenders is one of the fundamental questions in distributed computing. In its simplest formulation, the task is as follows: given $n$ processors, all participants must eventually return a win or lose indication, such that a single contender may win. Despite a considerable amount of work on leader election, the following question is still open: can we elect a leader in an asynchronous fault-prone system faster than just running a $Θ(\log n)$-time tournament, against a strong adaptive adversary? In this paper, we answer this question in the affirmative, improving on a decades-old upper bound. We introduce two new algorithmic ideas to reduce the time complexity of electing a leader to $O(\log^* n)$, using $O(n^2)$ point-to-point messages. A non-trivial application of our algorithm is a new upper bound for the tight renaming problem, assigning $n$ items to the $n$ participants in expected $O(\log^2 n)$ time and $O(n^2)$ messages. We complement our results with lower bound of $Ω(n^2)$ messages for solving these two problems, closing the question of their message complexity.
Analyzing Tensor Power Method Dynamics in Overcomplete Regime
Venue: arXiv cs.LG 2015
Year: 2015

We present a novel analysis of the dynamics of tensor power iterations in the overcomplete regime where the tensor CP rank is larger than the input dimension. Finding the CP decomposition of an overcomplete tensor is NP-hard in general. We consider the case where the tensor components are randomly drawn, and show that the simple power iteration recovers the components with bounded error under mild initialization conditions. We apply our analysis to unsupervised learning of latent variable models, such as multi-view mixture models and spherical Gaussian mixtures. Given the third order moment tensor, we learn the parameters using tensor power iterations. We prove it can correctly learn the model parameters when the number of hidden components $k$ is much larger than the data dimension $d$, up to $k = o(d^{1.5})$. We initialize the power iterations with data samples and prove its success under mild conditions on the signal-to-noise ratio of the samples. Our analysis significantly expands the class of latent variable models where spectral methods are applicable. Our analysis also deals with noise in the input tensor leading to sample complexity result in the application to learning latent variable models.
Answering Conjunctive Queries over $\mathcal{EL}$ Knowledge Bases with Transitive and Reflexive Roles
Venue: arXiv cs.AI 2015
Year: 2015

Answering conjunctive queries (CQs) over $\mathcal{EL}$ knowledge bases (KBs) with complex role inclusions is PSPACE-hard and in PSPACE in certain cases; however, if complex role inclusions are restricted to role transitivity, the tight upper complexity bound has so far been unknown. Furthermore, the existing algorithms cannot handle reflexive roles, and they are not practicable. Finally, the problem is tractable for acyclic CQs and $\mathcal{ELH}$, and NP-complete for unrestricted CQs and $\mathcal{ELHO}$ KBs. In this paper we complete the complexity landscape of CQ answering for several important cases. In particular, we present a practicable NP algorithm for answering CQs over $\mathcal{ELHO}^s$ KBs---a logic containing all of OWL 2 EL, but with complex role inclusions restricted to role transitivity. Our preliminary evaluation suggests that the algorithm can be suitable for practical use. Moreover, we show that, even for a restricted class of so-called arborescent acyclic queries, CQ answering over $\mathcal{EL}$ KBs becomes NP-hard in the presence of either transitive or reflexive roles. Finally, we show that answering arborescent CQs over $\mathcal{ELHO}$ KBs is tractable, whereas answering acyclic CQs is NP-hard.
Spatial Source Subtraction Based on Incomplete Measurements of Relative Transfer Function
Venue: arXiv cs.SD 2015
Year: 2015

Relative impulse responses between microphones are usually long and dense due to the reverberant acoustic environment. Estimating them from short and noisy recordings poses a long-standing challenge of audio signal processing. In this paper we apply a novel strategy based on ideas of Compressed Sensing. Relative transfer function (RTF) corresponding to the relative impulse response can often be estimated accurately from noisy data but only for certain frequencies. This means that often only an incomplete measurement of the RTF is available. A complete RTF estimate can be obtained through finding its sparsest representation in the time-domain: that is, through computing the sparsest among the corresponding relative impulse responses. Based on this approach, we propose to estimate the RTF from noisy data in three steps. First, the RTF is estimated using any conventional method such as the non-stationarity-based estimator by Gannot et al. or through Blind Source Separation. Second, frequencies are determined for which the RTF estimate appears to be accurate. Third, the RTF is reconstructed through solving a weighted $\ell_1$ convex program, which we propose to solve via a computationally efficient variant of the SpaRSA (Sparse Reconstruction by Separable Approximation) algorithm. An extensive experimental study with real-world recordings has been conducted. It has been shown that the proposed method is capable of improving many conventional estimators used as the first step in most situations.
Multi-modal Image Registration for Correlative Microscopy
Venue: arXiv cs.CV 2015
Year: 2015

Correlative microscopy is a methodology combining the functionality of light microscopy with the high resolution of electron microscopy and other microscopy technologies. Image registration for correlative microscopy is quite challenging because it is a multi-modal, multi-scale and multi-dimensional registration problem. In this report, I introduce two methods of image registration for correlative microscopy. The first method is based on fiducials (beads). I generate landmarks from the fiducials and compute the similarity transformation matrix based on three pairs of nearest corresponding landmarks. A least-squares matching process is applied afterwards to further refine the registration. The second method is inspired by the image analogies approach. I introduce the sparse representation model into image analogies. I first train representative image patches (dictionaries) for pre-registered datasets from two different modalities, and then I use the sparse coding technique to transfer a given image to a predicted image from one modality to another based on the learned dictionaries. The final image registration is between the predicted image and the original image corresponding to the given image in the different modality. The method transforms a multi-modal registration problem to a mono-modal one. I test my approaches on Transmission Electron Microscopy (TEM) and confocal microscopy images. Experimental results of the methods are also shown in this report.
Minimal Realization Problems for Hidden Markov Models
Venue: arXiv cs.LG 2015
Year: 2015

Consider a stationary discrete random process with alphabet size d, which is assumed to be the output process of an unknown stationary Hidden Markov Model (HMM). Given the joint probabilities of finite length strings of the process, we are interested in finding a finite state generative model to describe the entire process. In particular, we focus on two classes of models: HMMs and quasi-HMMs, which is a strictly larger class of models containing HMMs. In the main theorem, we show that if the random process is generated by an HMM of order less or equal than k, and whose transition and observation probability matrix are in general position, namely almost everywhere on the parameter space, both the minimal quasi-HMM realization and the minimal HMM realization can be efficiently computed based on the joint probabilities of all the length N strings, for N > 4 lceil log_d(k) rceil +1. In this paper, we also aim to compare and connect the two lines of literature: realization theory of HMMs, and the recent development in learning latent variable models with tensor decomposition techniques.
On the exponential convergence of the Kaczmarz algorithm
Venue: arXiv cs.SY 2015
Year: 2015

The Kaczmarz algorithm (KA) is a popular method for solving a system of linear equations. In this note we derive a new exponential convergence result for the KA. The key allowing us to establish the new result is to rewrite the KA in such a way that its solution path can be interpreted as the output from a particular dynamical system. The asymptotic stability results of the corresponding dynamical system can then be leveraged to prove exponential convergence of the KA. The new bound is also compared to existing bounds.
A Discrete Logarithm-based Approach to Compute Low-Weight Multiples of Binary Polynomials
Venue: arXiv cs.DM 2015
Year: 2015

Being able to compute efficiently a low-weight multiple of a given binary polynomial is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best known general purpose algorithm is based on the generalized birthday problem. We describe an alternative approach which is based on discrete logarithms and has much lower memory complexity requirements with a comparable time complexity.
Measure of combined effects of morphological parameters of inclusions within composite materials via stochastic homogenization to determine effective mechanical properties
Venue: arXiv cs.CE 2015
Year: 2015

In our previous papers we have described efficient and reliable methods of generation of representative volume elements (RVE) perfectly suitable for analysis of composite materials via stochastic homogenization. In this paper we profit from these methods to analyze the influence of the morphology on the effective mechanical properties of the samples. More precisely, we study the dependence of main mechanical characteristics of a composite medium on various parameters of the mixture of inclusions composed of spheres and cylinders. On top of that we introduce various imperfections to inclusions and observe the evolution of effective properties related to that. The main computational approach used throughout the work is the FFT-based homogenization technique, validated however by comparison with the direct finite elements method. We give details on the features of the method and the validation campaign as well. Keywords: Composite materials, Cylindrical and spherical reinforcements, Mechanical properties, Stochastic homogenization.
Energy-efficient Decoders for Compressive Sensing: Fundamental Limits and Implementations
Venue: arXiv cs.IT 2015
Year: 2015

The fundamental problem considered in this paper is "What is the \textit{energy} consumed for the implementation of a \emph{compressive sensing} decoding algorithm on a circuit?". Using the "information-friction" framework, we examine the smallest amount of \textit{bit-meters} as a measure for the energy consumed by a circuit. We derive a fundamental lower bound for the implementation of compressive sensing decoding algorithms on a circuit. In the setting where the number of measurements scales linearly with the sparsity and the sparsity is sub-linear with the length of the signal, we show that the \textit{bit-meters} consumption for these algorithms is order-tight, i.e., it matches the lower bound asymptotically up to a constant factor. Our implementations yield interesting insights into design of energy-efficient circuits that are not captured by the notion of computational efficiency alone.
Sketching as a Tool for Numerical Linear Algebra
Venue: arXiv cs.DS 2015
Year: 2015

This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties. Much of the expensive computation can then be performed on the smaller matrix, thereby accelerating the solution for the original problem. In this survey we consider least squares as well as robust regression problems, low rank approximation, and graph sparsification. We also discuss a number of variants of these problems. Finally, we discuss the limitations of sketching methods.
An infinitary model of linear logic
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, we construct an infinitary variant of the relational model of linear logic, where the exponential modality is interpreted as the set of finite or countable multisets. We explain how to interpret in this model the fixpoint operator Y as a Conway operator alternatively defined in an inductive or a coinductive way. We then extend the relational semantics with a notion of color or priority in the sense of parity games. This extension enables us to define a new fixpoint operator Y combining both inductive and coinductive policies. We conclude the paper by sketching the connection between the resulting model of lambda-calculus with recursion and higher-order model-checking.
Distributed Linear Precoding and User Selection in Coordinated Multicell Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this manuscript we tackle the problem of semi-distributed user selection with distributed linear precoding for sum rate maximization in multiuser multicell systems. A set of adjacent base stations (BS) form a cluster in order to perform coordinated transmission to cell-edge users, and coordination is carried out through a central processing unit (CU). However, the message exchange between BSs and the CU is limited to scheduling control signaling and no user data or channel state information (CSI) exchange is allowed. In the considered multicell coordinated approach, each BS has its own set of cell-edge users and transmits only to one intended user while interference to non-intended users at other BSs is suppressed by signal steering (precoding). We use two distributed linear precoding schemes, Distributed Zero Forcing (DZF) and Distributed Virtual Signal-to-Interference-plus-Noise Ratio (DVSINR). Considering multiple users per cell and the backhaul limitations, the BSs rely on local CSI to solve the user selection problem. First we investigate how the signal-to-noise-ratio (SNR) regime and the number of antennas at the BSs affect the effective channel gain (the magnitude of the channels after precoding) and its relationship with multiuser diversity. Considering that user selection must be based on the type of implemented precoding, we develop metrics of compatibility (estimations of the effective channel gains) that can be computed from local CSI at each BS and reported to the CU for scheduling decisions. Based on such metrics, we design user selection algorithms that can find a set of users that potentially maximizes the sum rate. Numerical results show the effectiveness of the proposed metrics and algorithms for different configurations of users and antennas at the base stations.
Hybrid Full-/Half-Duplex System Analysis in Heterogeneous Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

Full-duplex (FD) radio has been introduced for bidirectional communications on the same temporal and spectral resources so as to maximize spectral efficiency. In this paper, motivated by the recent advances in FD radios, we provide a foundation for hybrid-duplex heterogeneous networks (HDHNs), composed of multi-tier networks with a mixture of access points (APs), operating either in bidirectional FD mode or downlink half-duplex (HD) mode. Specifically, we characterize the net- work interference from FD-mode cells, and derive the HDHN throughput by accounting for AP spatial density, self-interference cancellation (IC) capability, and transmission power of APs and users. By quantifying the HDHN throughput, we present the effect of network parameters and the self-IC capability on the HDHN throughput, and show the superiority of FD mode for larger AP densities (i.e., larger network interference and shorter communication distance) or higher self-IC capability. Furthermore, our results show operating all APs in FD or HD achieves higher throughput compared to the mixture of two mode APs in each tier network, and introducing hybrid-duplex for different tier networks improves the heterogenous network throughput.
Distributed Interference Management Policies for Heterogeneous Small Cell Networks
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of interference management in large-scale small cell networks, where each user equipment (UE) needs to determine in a distributed manner when and at what power level it should transmit to its serving small cell base station (SBS) such that a given network performance criterion is maximized subject to minimum quality of service (QoS) requirements by the UEs. We first propose a distributed algorithm for the UE-SBS pairs to find a subset of weakly interfering UE-SBS pairs, namely the maximal independent sets (MISs) of the interference graph in logarithmic time (with respect to the number of UEs). Then we propose a novel problem formulation which enables UE-SBS pairs to determine the optimal fractions of time occupied by each MIS in a distributed manner. We analytically bound the performance of our distributed policy in terms of the competitive ratio with respect to the optimal network performance, which is obtained in a centralized manner with NP (non-deterministic polynomial time) complexity. Remarkably, the competitive ratio is independent of the network size, which guarantees scalability in terms of performance for arbitrarily large networks. Through simulations, we show that our proposed policies achieve significant performance improvements (from 150% to 700%) over the existing policies.
Approximating capacitated $k$-median with $(1+ε)k$ open facilities
Venue: arXiv cs.DS 2015
Year: 2015

In the capacitated $k$-median (\CKM) problem, we are given a set $F$ of facilities, each facility $i \in F$ with a capacity $u_i$, a set $C$ of clients, a metric $d$ over $F \cup C$ and an integer $k$. The goal is to open $k$ facilities in $F$ and connect the clients $C$ to the open facilities such that each facility $i$ is connected by at most $u_i$ clients, so as to minimize the total connection cost. In this paper, we give the first constant approximation for \CKM, that only violates the cardinality constraint by a factor of $1+ε$. This generalizes the result of [Li15], which only works for the uniform capacitated case. Moreover, the approximation ratio we obtain is $O\big(\frac{1}{ε^2}\log\frac1ε\big)$, which is an exponential improvement over the ratio of $\exp(O(1/ε^2))$ in [Li15]. The natural LP relaxation for the problem, which almost all previous algorithms for \CKM are based on, has unbounded integrality gap even if $(2-ε)k$ facilities can be opened. We introduce a novel configuration LP for the problem, that overcomes this integrality gap.
Output Constrained Lossy Source Coding with Limited Common Randomness
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies a Shannon-theoretic version of the generalized distribution preserving quantization problem where a stationary and memoryless source is encoded subject to a distortion constraint and the additional requirement that the reproduction also be stationary and memoryless with a given distribution. The encoder and decoder are stochastic and assumed to have access to independent common randomness. Recent work has characterized the minimum achievable coding rate at a given distortion level when unlimited common randomness is available. Here we consider the general case where the available common randomness may be rate limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. We also consider two variations of this problem where we investigate the effect of relaxing the strict output distribution constraint and the role of `private randomness' used by the decoder on the rate region. Our results have strong connections with Cuff's recent work on distributed channel synthesis. In particular, our achievability proof combines a coupling argument with the approach developed by Cuff, where instead of explicitly constructing the encoder-decoder pair, a joint distribution is constructed from which a desired encoder-decoder pair is established. We show however that for our problem, the separated solution of first finding an optimal channel and then synthesizing this channel results in a suboptimal rate region.
Falling Rule Lists
Venue: arXiv cs.AI 2015
Year: 2015

Falling rule lists are classification models consisting of an ordered list of if-then rules, where (i) the order of rules determines which example should be classified by each rule, and (ii) the estimated probability of success decreases monotonically down the list. These kinds of rule lists are inspired by healthcare applications where patients would be stratified into risk sets and the highest at-risk patients should be considered first. We provide a Bayesian framework for learning falling rule lists that does not rely on traditional greedy decision tree learning methods.
Almost Optimal Pseudorandom Generators for Spherical Caps
Venue: arXiv cs.CC 2015
Year: 2015

Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing pseudorandom generators (PRGs) for halfspaces over the sphere, aka spherical caps, which besides being interesting and basic geometric objects, also arise frequently in the analysis of various randomized algorithms (e.g., randomized rounding). We give an explicit PRG which fools spherical caps within error $ε$ and has an almost optimal seed-length of $O(\log n + \log(1/ε) \cdot \log\log(1/ε))$. For an inverse-polynomially growing error $ε$, our generator has a seed-length optimal up to a factor of $O( \log \log {(n)})$. The most efficient PRG previously known (due to Kane, 2012) requires a seed-length of $Ω(\log^{3/2}{(n)})$ in this setting. We also obtain similar constructions to fool halfspaces with respect to the Gaussian distribution. Our construction and analysis are significantly different from previous works on PRGs for halfspaces and build on the iterative dimension reduction ideas of Kane et. al. (2011) and Celis et. al. (2013), the \emph{classical moment problem} from probability theory and explicit constructions of \emph{orthogonal designs} based on the seminal work of Bourgain and Gamburd (2011) on expansion in Lie groups.