OpenRaiser/Intern-Atlas huggingface dataset:
Achieving Super-Resolution in Multi-Rate Sampling Systems via Efficient Semidefinite Programming
Venue: arXiv cs.IT 2016
Year: 2016

Super-resolution theory aims to estimate the discrete components lying in a continuous space that constitute a sparse signal with optimal precision. This work investigates the potential of recent super-resolution techniques for spectral estimation in multi-rate sampling systems. It shows that, under the existence of a common supporting grid, and under a minimal separation constraint, the frequencies of a spectrally sparse signal can be exactly jointly recovered from the output of a semidefinite program (SDP). The algorithmic complexity of this approach is discussed, and an equivalent SDP of minimal dimension is derived by extending the Gram parametrization properties of sparse trigonometric polynomials.
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem
Venue: arXiv cs.DM 2016
Year: 2016

We study a special kind of bounds (so called forbidden subgraph bounds, cf. Feige, Verbitsky '02) for parallel repetition of multi-prover games. First, we show that forbidden subgraph upper bounds for $r \ge 3$ provers imply the same bounds for the density Hales-Jewett theorem for alphabet of size $r$. As a consequence, this yields a new family of games with slow decrease in the parallel repetition value. Second, we introduce a new technique for proving exponential forbidden subgraph upper bounds and explore its power and limitations. In particular, we obtain exponential upper bounds for two-prover games with question graphs of treewidth at most two and show that our method cannot give exponential bounds for all two-prover graphs.
Reliable Physical-layer Network Coding Supporting Real Applications
Venue: arXiv cs.NI 2016
Year: 2016

This paper presents the first reliable physical-layer network coding (PNC) system that supports real TCP/IP applications for the two-way relay network (TWRN). Theoretically, PNC could boost the throughput of TWRN by a factor of 2 compared with traditional scheduling (TS) in the high signal-to-noise (SNR) regime. Although there have been many theoretical studies on PNC performance, there have been relatively few experimental and implementation efforts. Our earlier PNC prototype, built in 2012, was an offline system that processed signals offline. For a system that supports real applications, signals must be processed online in real-time. Our real-time reliable PNC prototype, referred to as RPNC, solves a number of key challenges to enable the support of real TCP/IP applications. The enabling components include: 1) a time-slotted system that achieves us-level synchronization for the PNC system; 2) reduction of PNC signal processing complexity to meet real-time constraints; 3) an ARQ design tailored for PNC to ensure reliable packet delivery; 4) an interface to the application layer. We took on the challenge to implement all the above with general-purpose processors in PC through an SDR platform rather than ASIC or FPGA. With all these components, we have successfully demonstrated image exchange with TCP and twoparty video conferencing with UDP over RPNC. Experimental results show that the achieved throughput approaches the PHYlayer data rate at high SNR, demonstrating the high efficiency of the RPNC system.
Almost All Even Yao-Yao Graphs Are Spanners
Venue: arXiv cs.DS 2016
Year: 2016

It is an open problem whether Yao-Yao graphs $\mathsf{YY}_k$ (also known as sparse-Yao graphs) are all spanners when the integer parameter $k$ is large enough. In this paper we show that, for any integer $k\geq 42$, the Yao-Yao graph $\mathsf{YY}_{2k}$ is a $t_k$-spanner, with stretch factor $t_k=6.03+O(k^{-1})$ when $k$ tends to infinity. Our result generalizes the best known result which asserts that all $\mathsf{YY}_{6k}$ are spanners for $k$ large enough [Bauer and Damian, SODA'13]. Our proof is also somewhat simpler.
CLAASIC: a Cortex-Inspired Hardware Accelerator
Venue: arXiv cs.ET 2016
Year: 2016

This work explores the feasibility of specialized hardware implementing the Cortical Learning Algorithm (CLA) in order to fully exploit its inherent advantages. This algorithm, which is inspired in the current understanding of the mammalian neo-cortex, is the basis of the Hierarchical Temporal Memory (HTM). In contrast to other machine learning (ML) approaches, the structure is not application dependent and relies on fully unsupervised continuous learning. We hypothesize that a hardware implementation will be able not only to extend the already practical uses of these ideas to broader scenarios but also to exploit the hardware-friendly CLA characteristics. The architecture proposed will enable an unfeasible scalability for software solutions and will fully capitalize on one of the many CLA advantages: low computational requirements and reduced storage utilization. Compared to a state-of-the-art CLA software implementation it could be possible to improve by 4 orders of magnitude in performance and up to 8 orders of magnitude in energy efficiency. We propose to use a packet-switched network to tackle this. The paper addresses the fundamental issues of such an approach, proposing solutions to achieve scalable solutions. We will analyze cost and performance when using well-known architecture techniques and tools. The results obtained suggest that even with CMOS technology, under constrained cost, it might be possible to implement a large-scale system. We found that the proposed solutions enable a saving of 90% of the original communication costs running either synthetic or realistic workloads.
Charting an Intent Driven Network
Venue: arXiv cs.NI 2016
Year: 2016

The current strong divide between applications and the network control plane is desirable for many reasons; but a downside is that the network is kept in the dark regarding the ultimate purposes and intentions of applications and, as a result, is unable to optimize for these. An alternative approach, explored in this paper, is for applications to declare to the network their abstract intents and assumptions; e.g. "this is a Tweet", or "this application will run within a local domain". Such an enriched semantic has the potential to enable the network better to fulfill application intent, while also helping optimize network resource usage across applications. We refer to this approach as 'intent driven networking' (IDN), and we sketch an incrementally-deployable design to serve as a stepping stone towards a practical realization of the IDN concept within today's Internet.
Persuasive Technologies for Sustainable Urban Mobility
Venue: arXiv cs.HC 2016
Year: 2016

In recent years, the persuasive interventions for inducing sustainable urban mobility behaviours has become a very active research field. This review paper systematically analyses existing approaches and prototype systems and describes and classifies the persuasive strategies used for changing behaviour in the domain of transport. It also studies the results and recommendations derived from pilot studies, and as a result of this analysis highlights the need for personalizing and tailoring persuasive technology to various user characteristics. We also discuss the possible role of context-aware persuasive systems for increasing the number of sustainable choices. Finally, recommendations for future investigations on scholarly persuasive systems are proposed.
Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems
Venue: arXiv cs.DC 2016
Year: 2016

We present dynamic I/O automata (DIOA), a compositional model of dynamic systems. In DIOA, automata can be created and destroyed dynamically, as computation proceeds, and an automaton can dynamically change its signature, i.e., the set of actions in which it can participate. DIOA features operators for parallel composition, action hiding, action renaming, a notion of automaton creation, and a notion of behavioral subtyping by means of trace inclusion. DIOA can model mobility, using signature modification, and is hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. We also show that parallel composition, action hiding, action renaming, and (subject to some technical conditions) automaton creation are all monotonic with respect to trace inclusion: if one component is replaced by another whose traces are a subset of the former, then the set of traces of the system as a whole can only be reduced.
Two-variable Logic with Counting and a Linear Order
Venue: arXiv cs.LO 2016
Year: 2016

We study the finite satisfiability problem for the two-variable fragment of first-order logic extended with counting quantifiers (C2) and interpreted over linearly ordered structures. We show that the problem is undecidable in the case of two linear orders (in the presence of two other binary symbols). In the case of one linear order it is NEXPTIME-complete, even in the presence of the successor relation. Surprisingly, the complexity of the problem explodes when we add one binary symbol more: C2 with one linear order and in the presence of other binary predicate symbols is equivalent, under elementary reductions, to the emptiness problem for multicounter automata.
An Intuitive Tangible Game Controller
Venue: arXiv cs.HC 2016
Year: 2016

This paper outlines the development of a sensory feedback device providing a tangible interface for controlling digital environments, in this example a flight simulator, where the intention for the device is that it is relatively low cost, versatile and intuitive. Gesture based input allows for a more immersive experience, so rather than making the user feel like they are controlling an aircraft the intuitive interface allows the user to become the aircraft that is controlled by the movements of the user's hand. The movements are designed to allow a sense of immersion that would be difficult to achieve with an alternative interface. A vibrotactile based haptic feedback is incorporated in the device to further enhance the connection between the user and the game environment by providing immediate confirmation of game events. When used for navigating an aircraft simulator, this device invites playful action and thrill. It bridges new territory on portable, low cost solutions for haptic devices in gaming contexts.
The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions
Venue: arXiv cs.LG 2016
Year: 2016

This paper studies classification with an abstention option in the online setting. In this setting, examples arrive sequentially, the learner is given a hypothesis class $\mathcal H$, and the goal of the learner is to either predict a label on each example or abstain, while ensuring that it does not make more than a pre-specified number of mistakes when it does predict a label. Previous work on this problem has left open two main challenges. First, not much is known about the optimality of algorithms, and in particular, about what an optimal algorithmic strategy is for any individual hypothesis class. Second, while the realizable case has been studied, the more realistic non-realizable scenario is not well-understood. In this paper, we address both challenges. First, we provide a novel measure, called the Extended Littlestone's Dimension, which captures the number of abstentions needed to ensure a certain number of mistakes. Second, we explore the non-realizable case, and provide upper and lower bounds on the number of abstentions required by an algorithm to guarantee a specified number of mistakes.
Detection and Combining Techniques for Asynchronous Random Access with Time Diversity
Venue: arXiv cs.IT 2016
Year: 2016

Asynchronous random access (RA) protocols are particularly attractive for their simplicity and avoidance of tight synchronization requirements. Recent enhancements have shown that the use of successive interference cancellation (SIC) can largely boost the performance of these schemes. A further step forward in the performance can be attained when diversity combining techniques are applied. In order to enable combining, the detection and association of the packets to their transmitters has to be done prior to decoding. We present a solution to this problem, that articulates into two phases. Non-coherent soft-correlation as well as interference-aware soft-correlation are used for packet detection. We evaluate the detection capabilities of both solutions via numerical simulations. We also evaluate numerically the spectral efficiency achieved by the proposed approach, highlighting its benefits.
Non-iterative Type 4 and 5 Nonuniform FFT Methods in the One-Dimensional Case
Venue: arXiv cs.IT 2016
Year: 2016

The so-called non-uniform FFT (NFFT) is a family of algorithms for efficiently computing the Fourier transform of finite-length signals, whenever the time or frequency grid is nonuniformly spaced. Following the usual classification, there exist five NFFT types. Types 1 and 2 make it possible to pass from the time to the frequency domain with nonuniform input and output grids respectively. Type 3 allows for both input and output nonuniform grids. Finally, types 4 and 5 are the inverses of types 1 and 2 and are expensive computationally, given that they involve iterative methods. In this paper, we solve this last drawback in the one-dimensional case by presenting non-iterative type 4 and 5 NFFT methods that just involve three NFFTs of types 1 or 2 plus some additional FFTs. The methods are based on exploiting the structure of the Lagrange interpolation formula. The paper includes several numerical examples in which the proposed methods are compared with the Gaussian elimination (GE) and conjugate gradient (CG) methods, both in terms of round-off error and computational burden.
Are there too many uncited articles? Zero inflated variants of the discretised lognormal and hooked power law distributions
Venue: arXiv cs.DL 2016
Year: 2016

Although statistical models fit many citation data sets reasonably well with the best fitting models being the hooked power law and discretised lognormal distribution, the fits are rarely close. One possible reason is that there might be more uncited articles than would be predicted by any model if some articles are inherently uncitable. Using data from 23 different Scopus categories, this article tests the assumption that removing a proportion of uncited articles from a citation dataset allows statistical distributions to have much closer fits. It also introduces two new models, zero inflated discretised lognormal distribution and the zero inflated hooked power law distribution and algorithms to fit them. In all 23 cases, the zero inflated version of the discretised lognormal distribution was an improvement on the standard version and in 15 out of 23 cases the zero inflated version of the hooked power law was an improvement on the standard version. Without zero inflation the discretised lognormal models fit the data better than the hooked power law distribution 6 out of 23 times and with it, the discretised lognormal models fit the data better than the hooked power law distribution 9 out of 23 times. Apparently uncitable articles seem to occur due to the presence of academic-related magazines in Scopus categories. In conclusion, future citation analysis and research indicators should take into account uncitable articles, and the best fitting distribution for sets of citation counts from a single subject and year is either the zero inflated discretised lognormal or zero inflated hooked power law.
Data Structure Lower Bounds for Document Indexing Problems
Venue: arXiv cs.DS 2016
Year: 2016

We study data structure problems related to document indexing and pattern matching queries and our main contribution is to show that the pointer machine model of computation can be extremely useful in proving high and unconditional lower bounds that cannot be obtained in any other known model of computation with the current techniques. Often our lower bounds match the known space-query time trade-off curve and in fact for all the problems considered, there is a very good and reasonable match between the our lower bounds and the known upper bounds, at least for some choice of input parameters. The problems that we consider are set intersection queries (both the reporting variant and the semi-group counting variant), indexing a set of documents for two-pattern queries, or forbidden- pattern queries, or queries with wild-cards, and indexing an input set of gapped-patterns (or two-patterns) to find those matching a document given at the query time.
Computation Tree Logic for Synchronization Properties
Venue: arXiv cs.LO 2016
Year: 2016

We present a logic that extends CTL (Computation Tree Logic) with operators that express synchronization properties. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers. This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable. We show that our variant of CTL is decidable and that the model-checking problem is in Delta_3^P = P^{NP^NP}, and is DP-hard. We analogously consider quantifier exchange in extensions of CTL, and we present operators defined using basic operators of CTL* that express the occurrence of infinitely many synchronization points. We show that the model-checking problem remains in Delta_3^P. The distinguishing power of CTL and of our new logic coincide if the Next operator is allowed in the logics, thus the classical bisimulation quotient can be used for state-space reduction before model checking.
Dependency Parsing with LSTMs: An Empirical Evaluation
Venue: arXiv cs.CL 2016
Year: 2016

We propose a transition-based dependency parser using Recurrent Neural Networks with Long Short-Term Memory (LSTM) units. This extends the feedforward neural network parser of Chen and Manning (2014) and enables modelling of entire sequences of shift/reduce transition decisions. On the Google Web Treebank, our LSTM parser is competitive with the best feedforward parser on overall accuracy and notably achieves more than 3% improvement for long-range dependencies, which has proved difficult for previous transition-based parsers due to error propagation and limited context information. Our findings additionally suggest that dropout regularisation on the embedding layer is crucial to improve the LSTM's generalisation.
Sum-Rate Analysis and Optimization of Self-Backhauling Based Full-Duplex Radio Access System
Venue: arXiv cs.IT 2016
Year: 2016

In this article, a radio access system with a self-backhauling full-duplex access node serving legacy half-duplex mobile devices is studied and analyzed. In particular, it is assumed that the access node is using the same center frequency for all the transmissions, meaning that also the backhauling is done using the same frequency resources as the uplink and downlink transmissions. It is further assumed that the access node has a massive array to facilitate efficient beamforming and self-interference nulling in its own receiver. As a starting point, the signal model for the considered access node is first derived, including all the transmitted and received signals within the cell. This is then used as a basis for obtaining the sum-rate expressions, which depict the overall rates experienced by the mobile users that are served by the access node. In addition, the data rate for the bi-directional backhaul link is also derived, since the access node must be able to backhaul itself wirelessly. The maximum achievable sum-rate is then determined by numerically solving an optimization problem constructed from the data rate expressions. The full-duplex scheme is also compared to two alternative transmission schemes, which perform all or some of the transmissions in half-duplex mode. The results show that the full-duplex capability of the access node is beneficial for maximizing the sum-rate, meaning that a simple half-duplex transmission scheme is typically not optimal. In particular, the highest sum-rate is usually provided by a relay type solution, where the access node acts as a full-duplex relay between the mobiles and the backhaul node.
On Number Conservation of Non-uniform Cellular Automata
Venue: arXiv cs.FL 2016
Year: 2016

This paper studies the number conservation property of 1-dimensional non-uniform cellular automata (CAs). In a non-uniform cellular automaton (CA), different cells may follow different rules. The present work considers that the cells follow Wolfram's CAs rules. A characterization tool, named Reachability tree is used to discover the number conservation property of non-uniform CAs. Then a decision algorithm is reported to conclude whether a given non-uniform CA with $n$ cells is number conserving or not. Finally, a synthesis scheme is developed to get an $n$-cell number conserving non-uniform CA.
Faster Average Case Low Memory Semi-External Construction of the Burrows-Wheeler Transform
Venue: arXiv cs.DS 2016
Year: 2016

The Burrows Wheeler transform has applications in data compression as well as full text indexing. Despite its important applications and various existing algorithmic approaches the construction of the transform for large data sets is still challenging. In this paper we present a new semi external memory algorithm for constructing the Burrows Wheeler transform. It is capable of constructing the transform for an input text of length $n$ over a finite alphabet in time $O(n\log^2\log n)$ on average, if sufficient internal memory is available to hold a fixed fraction of the input text. In the worst case the run-time is $O(n\log n \log\log n)$. The amount of space used by the algorithm in external memory is $O(n)$ bits. Based on the serial version we also present a shared memory parallel algorithm running in time $O(\frac{n}{p}\max\{\log^2\log n+\log p\})$ on average when $p$ processors are available.
Parameterized Compilation Lower Bounds for Restricted CNF-formulas
Venue: arXiv cs.AI 2016
Year: 2016

We show unconditional parameterized lower bounds in the area of knowledge compilation, more specifically on the size of circuits in decomposable negation normal form (DNNF) that encode CNF-formulas restricted by several graph width measures. In particular, we show that - there are CNF formulas of size $n$ and modular incidence treewidth $k$ whose smallest DNNF-encoding has size $n^{Ω(k)}$, and - there are CNF formulas of size $n$ and incidence neighborhood diversity $k$ whose smallest DNNF-encoding has size $n^{Ω(\sqrt{k})}$. These results complement recent upper bounds for compiling CNF into DNNF and strengthen---quantitatively and qualitatively---known conditional low\-er bounds for cliquewidth. Moreover, they show that, unlike for many graph problems, the parameters considered here behave significantly differently from treewidth.