OpenRaiser/Intern-Atlas huggingface dataset:
Expressibility in the Lambda Calculus with Letrec
Venue: arXiv cs.PL 2013
Year: 2013

We investigate the relationship between finite terms in lambda-letrec, the lambda calculus with letrec, and the infinite lambda terms they express. As there are easy examples of lambda-terms that, intuitively, are not unfoldings of terms in lambda-letrec, we consider the question: How can those infinite lambda terms be characterised that are lamda-letrec-expressible in the sense that they can be obtained as infinite unfoldings of terms in lambda-letrec? For 'observing' infinite lambda-terms through repeated 'experiments' carried out at the head of the term we introduce two rewrite systems (with rewrite relations) -reg-> and -reg+-> that decompose the term, and produce 'generated subterms' in two notions. Thereby the sort of the step can be observed as well as its target, a generated subterm. In both systems there are four sorts of decomposition steps: -lambda-> steps (decomposing a lambda-abstraction), -@0> and -@1> steps (decomposing an application into its function and argument), and respectively, -del-> steps (delimiting the scope of an abstraction, for -reg->), and -S-> (delimiting of scopes, for -reg+->). These steps take place on infinite lambda-terms furnished with a leading prefix of abstractions for gathering previously encountered lambda-abstractions and keeping the generated subterms closed. We call an infinite lambda-term 'regular'/'strongly regular' if its set of -reg-> -reachable / -reg-> -reachable generated subterms is finite. Furthermore, we analyse the binding structure of lambda-terms with the concept of 'binding-capturing chain'. Using these concepts, we answer the question above by providing two characterisations of lambda-letrec-expressibility. For all infinite lambda-terms M, the following statements are equivalent: (i) M is lambda-letrec-expressible; (ii) M is strongly regular; (iii) M is regular, and it only has finite binding-capturing chains.
A Sub-Nyquist Radar Prototype: Hardware and Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

Traditional radar sensing typically involves matched filtering between the received signal and the shape of the transmitted pulse. Under the confinement of classic sampling theorem this requires that the received signals must first be sampled at twice the baseband bandwidth, in order to avoid aliasing. The growing demands for target distinction capability and spatial resolution imply significant growth in the bandwidth of the transmitted pulse. Thus, correlation based radar systems require high sampling rates, and with the large amounts of data sampled also necessitate vast memory capacity. In addition, real-time processing of the data typically results in high power consumption. Recently, new approaches for radar sensing and detection were introduced, based on the Finite Rate of Innovation and Xampling frameworks. These techniques allow significant reduction in sampling rate, implying potential power savings, while maintaining the system's detection capabilities at high enough SNR. Here we present for the first time a design and implementation of a Xampling-based hardware prototype that allows sampling of radar signals at rates much lower than Nyquist. We demostrate by real-time analog experiments that our system is able to maintain reasonable detection capabilities, while sampling radar signals that require sampling at a rate of about 30MHz at a total rate of 1Mhz.
Statistical Common Author Networks (SCAN)
Venue: arXiv cs.DL 2013
Year: 2013

A new method for visualizing the relatedness of scientific areas is developed that is based on measuring the overlap of researchers between areas. It is found that closely related areas have a high propensity to share a larger number of common authors. A methodology for comparing areas of vastly different sizes and to handle name homonymy is constructed, allowing for the robust deployment of this method on real data sets. A statistical analysis of the probability distributions of the common author overlap that accounts for noise is carried out along with the production of network maps with weighted links proportional to the overlap strength. This is demonstrated on two case studies, complexity science and neutrino physics, where the level of relatedness of areas within each area is expected to vary greatly. It is found that the results returned by this method closely match the intuitive expectation that the broad, multidisciplinary area of complexity science possesses areas that are weakly related to each other while the much narrower area of neutrino physics shows very strongly related areas.
Toward Resource-Optimal Consensus over the Wireless Medium
Venue: arXiv cs.IT 2013
Year: 2013

We carry out a comprehensive study of the resource cost of averaging consensus in wireless networks. Most previous approaches suppose a graphical network, which abstracts away crucial features of the wireless medium, and measure resource consumption only in terms of the total number of transmissions required to achieve consensus. Under a path-loss dominated model, we study the resource requirements of consensus with respect to three wireless-appropriate metrics: total transmit energy, elapsed time, and time-bandwidth product. First we characterize the performance of several popular gossip algorithms, showing that they may be order-optimal with respect to transmit energy but are strictly suboptimal with respect to elapsed time and time-bandwidth product. Further, we propose a new consensus scheme, termed hierarchical averaging, and show that it is nearly order-optimal with respect to all three metrics. Finally, we examine the effects of quantization, showing that hierarchical averaging provides a nearly order-optimal tradeoff between resource consumption and quantization error.
Iterative graph cuts for image segmentation with a nonlinear statistical shape prior
Venue: arXiv cs.CV 2013
Year: 2013

Shape-based regularization has proven to be a useful method for delineating objects within noisy images where one has prior knowledge of the shape of the targeted object. When a collection of possible shapes is available, the specification of a shape prior using kernel density estimation is a natural technique. Unfortunately, energy functionals arising from kernel density estimation are of a form that makes them impossible to directly minimize using efficient optimization algorithms such as graph cuts. Our main contribution is to show how one may recast the energy functional into a form that is minimizable iteratively and efficiently using graph cuts.
Distributed Channel Synthesis
Venue: arXiv cs.IT 2013
Year: 2013

Two familiar notions of correlation are rediscovered as the extreme operating points for distributed synthesis of a discrete memoryless channel, in which a stochastic channel output is generated based on a compressed description of the channel input. Wyner's common information is the minimum description rate needed. However, when common randomness independent of the input is available, the necessary description rate reduces to Shannon's mutual information. This work characterizes the optimal trade-off between the amount of common randomness used and the required rate of description. We also include a number of related derivations, including the effect of limited local randomness, rate requirements for secrecy, applications to game theory, and new insights into common information duality. Our proof makes use of a soft covering lemma, known in the literature for its role in quantifying the resolvability of a channel. The direct proof (achievability) constructs a feasible joint distribution over all parts of the system using a soft covering, from which the behavior of the encoder and decoder is inferred, with no explicit reference to joint typicality or binning. Of auxiliary interest, this work also generalizes and strengthens this soft covering tool.
Differentially Private Data Analysis of Social Networks via Restricted Sensitivity
Venue: arXiv cs.CR 2013
Year: 2013

We introduce the notion of restricted sensitivity as an alternative to global and smooth sensitivity to improve accuracy in differentially private data analysis. The definition of restricted sensitivity is similar to that of global sensitivity except that instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over a restricted class of datasets. Specifically, given a query f and a hypothesis H about the structure of a dataset D, we show generically how to transform f into a new query f_H whose global sensitivity (over all datasets including those that do not satisfy H) matches the restricted sensitivity of the query f. Moreover, if the belief of the querier is correct (i.e., D is in H) then f_H(D) = f(D). If the belief is incorrect, then f_H(D) may be inaccurate. We demonstrate the usefulness of this notion by considering the task of answering queries regarding social-networks, which we model as a combination of a graph and a labeling of its vertices. In particular, while our generic procedure is computationally inefficient, for the specific definition of H as graphs of bounded degree, we exhibit efficient ways of constructing f_H using different projection-based techniques. We then analyze two important query classes: subgraph counting queries (e.g., number of triangles) and local profile queries (e.g., number of people who know a spy and a computer-scientist who know each other). We demonstrate that the restricted sensitivity of such queries can be significantly lower than their smooth sensitivity. Thus, using restricted sensitivity we can maintain privacy whether or not D is in H, while providing more accurate results in the event that H holds true.
Brain-Computer Interface Controlled Robotic Gait Orthosis
Venue: arXiv cs.HC 2013
Year: 2013

Reliance on wheelchairs after spinal cord injury (SCI) leads to many medical co-morbidities. Treatment of these conditions contributes to the majority of SCI health care costs. Restoring able-body-like ambulation after SCI may reduce the incidence of these conditions, and increase independence and quality of life. However, no biomedical solution exists that can reverse this lost neurological function, and hence novel methods are needed. Brain-computer interface (BCI) controlled lower extremity prosthesis may constitute one such novel approach. One subject with able-body and one with paraplegia due to SCI underwent electroencephalogram (EEG) recording while engaged in alternating epochs of idling and walking kinesthetic motor imagery (KMI). These data were analyzed to generate an EEG prediction model for online BCI operation. A commercial robotic gait orthosis (RoGO) system (treadmill suspended), was interfaced with the BCI computer. In an online test, the subjects were tasked to ambulate using the BCI-RoGO system when prompted by computerized cues. The performance of this system was assessed with cross-correlation analysis, and omission and false alarm rates. The offline accuracy of the EEG prediction model averaged 86.3%. The cross-correlation between instructional cues and BCI-RoGO walking epochs averaged 0.812 +/- 0.048 (p-value<10^-4). There were on average 0.8 false alarms per session and no omissions. This is the first time a person with parapegia due to SCI regained basic brain-controlled ambulation, thereby indicating that restoring brain-controlled ambulation is feasible. Future work will test this system in a population of individuals with SCI. If successful, this may justify future development of invasive BCI-controlled lower extremity prostheses. This system may also be applied to incomplete SCI to improve neurological outcomes beyond those of standard physiotherapy.
How Penalty Leads to Improvement: a Measurement Study of Wireless Backoff
Venue: arXiv cs.NI 2013
Year: 2013

Despite much theoretical work, different modifications of backoff protocols in 802.11 networks lack empirical evidence demonstrating their real-life performance. To fill the gap we have set out to experiment with performance of exponential backoff by varying its backoff factor. Despite the satisfactory results for throughput, we have witnessed poor fairness manifesting in severe capture effect. The design of standard backoff protocol allows already successful nodes to remain successful, giving little chance to those nodes that failed to capture the channel in the beginning. With this at hand, we ask a conceptual question: Can one improve the performance of wireless backoff by introducing a mechanism of self-penalty, when overly successful nodes are penalized with big contention windows? Our real-life measurements using commodity hardware demonstrate that in many settings such mechanism not only allows to achieve better throughput, but also assures nearly perfect fairness. We further corroborate these results with simulations and an analytical model. Finally, we present a backoff factor selection protocol which can be implemented in access points to enable deployment of the penalty backoff protocol to consumer devices.
Coding Opportunity Densification Strategies for Instantly Decodable Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we aim to identify the strategies that can maximize and monotonically increase the density of the coding opportunities in instantly decodable network coding (IDNC).Using the well-known graph representation of IDNC, first derive an expression for the exact evolution of the edge set size after the transmission of any arbitrary coded packet. From the derived expressions, we show that sending commonly wanted packets for all the receivers can maximize the number of coding opportunities. Since guaranteeing such property in IDNC is usually impossible, this strategy does not guarantee the achievement of our target. Consequently, we further investigate the problem by deriving the expectation of the edge set size evolution after ignoring the identities of the packets requested by the different receivers and considering only their numbers. We then employ this expected expression to show that serving the maximum number of receivers having the largest numbers of missing packets and erasure probabilities tends to both maximize and monotonically increase the expected density of coding opportunities. Simulation results justify our theoretical findings. Finally, we validate the importance of our work through two case studies showing that our identified strategy outperforms the step-by-step service maximization solution in optimizing both the IDNC completion delay and receiver goodput.
Generalized Formulation of Weighted Optimal Guidance Laws with Impact Angle Constraint
Venue: arXiv cs.SY 2013
Year: 2013

The purpose of this paper is to investigate the generalized formulation of weighted optimal guidance laws with impact angle constraint. From the generalized formulation, we explicitly find the feasible set of weighting functions that lead to analytical forms of weighted optimal guidance laws. This result has potential significance because it can provide additional degrees of freedom in designing a guidance law that accomplishes the specified guidance objective.
Joint Spatial Division and Multiplexing
Venue: arXiv cs.IT 2013
Year: 2013

We propose Joint Spatial Division and Multiplexing (JSDM), an approach to multiuser MIMO downlink that exploits the structure of the correlation of the channel vectors in order to allow for a large number of antennas at the base station while requiring reduced-dimensional Channel State Information at the Transmitter (CSIT). This allows for significant savings both in the downlink training and in the CSIT feedback from the user terminals to the base station, thus making the use of a large number of base station antennas potentially suitable also for Frequency Division Duplexing (FDD) systems, for which uplink/downlink channel reciprocity cannot be exploited. JSDM forms the multiuser MIMO downlink precoder by concatenating a pre-beamforming matrix, which depends only on the channel second-order statistics, with a classical multiuser precoder, based on the instantaneous knowledge of the resulting reduced dimensional effective channels. We prove a simple condition under which JSDM incurs no loss of optimality with respect to the full CSIT case. For linear uniformly spaced arrays, we show that such condition is closely approached when the number of antennas is large. For this case, we use Szego asymptotic theory of large Toeplitz matrices to design a DFT-based pre-beamforming scheme requiring only coarse information about the users angles of arrival and angular spread. Finally, we extend these ideas to the case of a two-dimensional base station antenna array, with 3-dimensional beamforming, including multiple beams in the elevation angle direction. We provide guidelines for the pre-beamforming optimization and calculate the system spectral efficiency under proportional fairness and maxmin fairness criteria, showing extremely attractive performance. Our numerical results are obtained via an asymptotic random matrix theory tool known as deterministic equivalent approximation.
Error Rate Analysis of GF(q) Network Coded Detect-and-Forward Wireless Relay Networks Using Equivalent Relay Channel Models
Venue: arXiv cs.IT 2013
Year: 2013

This paper investigates simple means of analyzing the error rate performance of a general q-ary Galois Field network coded detect-and-forward cooperative relay network with known relay error statistics at the destination. Equivalent relay channels are used in obtaining an approximate error rate of the relay network, from which the diversity order is found. Error rate analyses using equivalent relay channel models are shown to be closely matched with simulation results. Using the equivalent relay channels, low complexity receivers are developed whose performances are close to that of the optimal maximum likelihood receiver.
Fused Multiple Graphical Lasso
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we consider the problem of estimating multiple graphical models simultaneously using the fused lasso penalty, which encourages adjacent graphs to share similar structures. A motivating example is the analysis of brain networks of Alzheimer's disease using neuroimaging data. Specifically, we may wish to estimate a brain network for the normal controls (NC), a brain network for the patients with mild cognitive impairment (MCI), and a brain network for Alzheimer's patients (AD). We expect the two brain networks for NC and MCI to share common structures but not to be identical to each other; similarly for the two brain networks for MCI and AD. The proposed formulation can be solved using a second-order method. Our key technical contribution is to establish the necessary and sufficient condition for the graphs to be decomposable. Based on this key property, a simple screening rule is presented, which decomposes the large graphs into small subgraphs and allows an efficient estimation of multiple independent (small) subgraphs, dramatically reducing the computational cost. We perform experiments on both synthetic and real data; our results demonstrate the effectiveness and efficiency of the proposed approach.
Counterfactual Reasoning and Learning Systems
Venue: arXiv cs.LG 2013
Year: 2013

This work shows how to leverage causal inference to understand the behavior of complex learning systems interacting with their environment and predict the consequences of changes to the system. Such predictions allow both humans and algorithms to select changes that improve both the short-term and long-term performance of such systems. This work is illustrated by experiments carried out on the ad placement system associated with the Bing search engine.
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
Venue: arXiv cs.CC 2013
Year: 2013

We study the problem of obtaining deterministic black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an deterministic white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg^2 S), this is analogous (in the terminology of boolean pseudorandomness) to a seed-length of lg^2 S, which is the seed length of the pseudorandom generators of Nisan and Impagliazzo-Nisan-Wigderson for read-once oblivious boolean branching programs. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg^2 S/lglg S), corresponding to a seed length of lg^2 S/lglg S. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounded width, where no pseudorandom generator (or hitting set) with seed length o(lg^2 S) is known. In follow up work, we strengthened a result of Mulmuley, and showed that derandomizing a particular case of the Noether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using the results of the present work, this gives a derandomization of Noether Normalization in that case, which Mulmuley conjectured would difficult due to its relations to problems in algebraic geometry. We also show that several other circuit classes can be black-box reduced to read-once oblivious ABPs, including set-multilinear ABPs (a generalization of depth-3 set-multilinear formulas), non-commutative ABPs (generalizing non-commutative formulas), and (semi-)diagonal depth-4 circuits (as introduced by Saxena).
Entropy Bounds for Discrete Random Variables via Maximal Coupling
Venue: arXiv cs.IT 2013
Year: 2013

This paper derives new bounds on the difference of the entropies of two discrete random variables in terms of the local and total variation distances between their probability mass functions. The derivation of the bounds relies on maximal coupling, and they apply to discrete random variables which are defined over finite or countably infinite alphabets. Loosened versions of these bounds are demonstrated to reproduce some previously reported results. The use of the new bounds is exemplified for the Poisson approximation, where bounds on the local and total variation distances follow from Stein's method.
Faster spectral sparsification and numerical algorithms for SDD matrices
Venue: arXiv cs.DS 2013
Year: 2013

We study algorithms for spectral graph sparsification. The input is a graph $G$ with $n$ vertices and $m$ edges, and the output is a sparse graph $\tilde{G}$ that approximates $G$ in an algebraic sense. Concretely, for all vectors $x$ and any $ε>0$, $\tilde{G}$ satisfies $$ (1-ε) x^T L_G x \leq x^T L_{\tilde{G}} x \leq (1+ε) x^T L_G x, $$ where $L_G$ and $L_{\tilde{G}}$ are the Laplacians of $G$ and $\tilde{G}$ respectively. We show that the fastest known algorithm for computing a sparsifier with $O(n\log n/ε^2)$ edges can actually run in $\tilde{O}(m\log^2 n)$ time, an $O(\log n)$ factor faster than before. We also present faster sparsification algorithms for slightly dense graphs. Specifically, we give an algorithm that runs in $\tilde{O}(m\log n)$ time and generates a sparsifier with $\tilde{O}(n\log^3{n}/ε^2)$ edges. This implies that a sparsifier with $O(n\log n/ε^2)$ edges can be computed in $\tilde{O}(m\log n)$ time for graphs with more than $O(n\log^4 n)$ edges. We also give an $\tilde{O}(m)$ time algorithm for graphs with more than $n\log^5 n (\log \log n)^3$ edges of polynomially bounded weights, and an $O(m)$ algorithm for unweighted graphs with more than $n\log^8 n (\log \log n)^3 $ edges and $n\log^{10} n (\log \log n)^5$ edges in the weighted case. The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of slightly dense SDD matrices.