OpenRaiser/Intern-Atlas huggingface dataset:
Direct design of LPV feedback controllers: technical details and numerical examples
Venue: arXiv cs.SY 2014
Year: 2014

The paper contains technical details of recent results developed by the author, regarding the design of LPV controllers directly from experimental data. Two numerical examples are also presented, about control of the Duffing oscillator and control of a two-degree-of-freedom manipulator.
An Efficient Thread Mapping Strategy for Multiprogramming on Manycore Processors
Venue: arXiv cs.DC 2014
Year: 2014

The emergence of multicore and manycore processors is set to change the parallel computing world. Applications are shifting towards increased parallelism in order to utilise these architectures efficiently. This leads to a situation where every application creates its desirable number of threads, based on its parallel nature and the system resources allowance. Task scheduling in such a multithreaded multiprogramming environment is a significant challenge. In task scheduling, not only the order of the execution, but also the mapping of threads to the execution resources is of a great importance. In this paper we state and discuss some fundamental rules based on results obtained from selected applications of the BOTS benchmarks on the 64-core TILEPro64 processor. We demonstrate how previously efficient mapping policies such as those of the SMP Linux scheduler become inefficient when the number of threads and cores grows. We propose a novel, low-overhead technique, a heuristic based on the amount of time spent by each CPU doing some useful work, to fairly distribute the workloads amongst the cores in a multiprogramming environment. Our novel approach could be implemented as a pragma similar to those in the new task-based OpenMP versions, or can be incorporated as a distributed thread mapping mechanism in future manycore programming frameworks. We show that our thread mapping scheme can outperform the native GNU/Linux thread scheduler in both single-programming and multiprogramming environments.
Chemlambda, universality and self-multiplication
Venue: arXiv cs.AI 2014
Year: 2014

We present chemlambda (or the chemical concrete machine), an artificial chemistry with the following properties: (a) is Turing complete, (b) has a model of decentralized, distributed computing associated to it, (c) works at the level of individual (artificial) molecules, subject of reversible, but otherwise deterministic interactions with a small number of enzymes, (d) encodes information in the geometrical structure of the molecules and not in their numbers, (e) all interactions are purely local in space and time. This is part of a larger project to create computing, artificial chemistry and artificial life in a distributed context, using topological and graphical languages.
Energy-Efficient Adaptive Video Transmission: Exploiting Rate Predictions in Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

The unprecedented growth of mobile video traffic is adding significant pressure to the energy drain at both the network and the end user. Energy efficient video transmission techniques are thus imperative to cope with the challenge of satisfying user demand at sustainable costs. In this paper, we investigate how predicted user rates can be exploited for energy efficient video streaming with the popular HTTP-based Adaptive Streaming (AS) protocols (e.g. DASH). To this end, we develop an energy-efficient Predictive Green Streaming (PGS) optimization framework that leverages predictions of wireless data rates to achieve the following objectives 1) minimize the required transmission airtime without causing streaming interruptions, 2) minimize total downlink Base Station (BS) power consumption for cases where BSs can be switched off in deep sleep, and 3) enable a trade-off between AS quality and energy consumption. Our framework is first formulated as a Mixed Integer Linear Program (MILP) where decisions on multi-user rate allocation, video segment quality, and BS transmit power are jointly optimized. Then, to provide an online solution, we present a polynomial-time heuristic algorithm that decouples the PGS problem into multiple stages. We provide a performance analysis of the proposed methods by simulations, and numerical results demonstrate that the PGS framework yields significant energy savings.
Hyperspectral image superresolution: An edge-preserving convex formulation
Venue: arXiv cs.CV 2014
Year: 2014

Hyperspectral remote sensing images (HSIs) are characterized by having a low spatial resolution and a high spectral resolution, whereas multispectral images (MSIs) are characterized by low spectral and high spatial resolutions. These complementary characteristics have stimulated active research in the inference of images with high spatial and spectral resolutions from HSI-MSI pairs. In this paper, we formulate this data fusion problem as the minimization of a convex objective function containing two data-fitting terms and an edge-preserving regularizer. The data-fitting terms are quadratic and account for blur, different spatial resolutions, and additive noise; the regularizer, a form of vector Total Variation, promotes aligned discontinuities across the reconstructed hyperspectral bands. The optimization described above is rather hard, owing to its non-diagonalizable linear operators, to the non-quadratic and non-smooth nature of the regularizer, and to the very large size of the image to be inferred. We tackle these difficulties by tailoring the Split Augmented Lagrangian Shrinkage Algorithm (SALSA)---an instance of the Alternating Direction Method of Multipliers (ADMM)---to this optimization problem. By using a convenient variable splitting and by exploiting the fact that HSIs generally "live" in a low-dimensional subspace, we obtain an effective algorithm that yields state-of-the-art results, as illustrated by experiments.
Recent advances on the log-rank conjecture in communication complexity
Venue: arXiv cs.CC 2014
Year: 2014

The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this conjecture. Recently, there has been renewed interest in this conjecture and its relations to other fundamental problems in complexity theory. This survey describes some of the recent progress, and hints at potential directions for future research.
Performance of Selection Combining for Differential Amplify-and-Forward Relaying Over Time-Varying Channels
Venue: arXiv cs.IT 2014
Year: 2014

Selection combining (SC) at the destination for differential amplify-and-forward (AF) relaying is attractive as it does not require channel state information as compared to the semi maximum-ratio-combining (semi-MRC) while delivering close performance. Performance analysis of the SC scheme was recently reported but only for the case of slow-fading channels. This paper provides an exact average bit-error-rate (BER) of the SC scheme over a general case of time-varying Rayleigh fading channels and when the DBPSK modulation is used together with the non-coherent detection at the destination. The presented analysis is thoroughly verified with simulation results in various fading scenarios. It is shown that the performance of the system is related to the auto-correlation values of the channels. It is also shown that the performance of the SC method is very close to that of the semi-MRC method and the existence of an error floor at high signal-to-noise ratio region is inevitable in both methods. The obtained BER analysis for the SC method can also be used to approximate the BER performance of the MRC method, whose exact analytical evaluation in time-varying channels appears to be difficult.
Coding for Random Projections and Approximate Near Neighbor Search
Venue: arXiv cs.LG 2014
Year: 2014

This technical note compares two coding (quantization) schemes for random projections in the context of sub-linear time approximate near neighbor search. The first scheme is based on uniform quantization while the second scheme utilizes a uniform quantization plus a uniformly random offset (which has been popular in practice). The prior work compared the two schemes in the context of similarity estimation and training linear classifiers, with the conclusion that the step of random offset is not necessary and may hurt the performance (depending on the similarity level). The task of near neighbor search is related to similarity estimation with importance distinctions and requires own study. In this paper, we demonstrate that in the context of near neighbor search, the step of random offset is not needed either and may hurt the performance (sometimes significantly so, depending on the similarity and other parameters).
Factoring Differential Operators in n Variables
Venue: arXiv cs.SC 2014
Year: 2014

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial n'th Weyl algebra, the polynomial n'th shift algebra, and ZZ^n-graded polynomials in the n'th q-Weyl algebra. The most unexpected result is that this noncommutative problem of factoring partial differential operators can be approached effectively by reducing it to the problem of solving systems of polynomial equations over a commutative ring. In the case where a given polynomial is ZZ^n-graded, we can reduce the problem completely to factoring an element in a commutative multivariate polynomial ring. The implementation in Singular is effective on a broad range of polynomials and increases the ability of computer algebra systems to address this important problem. We compare the performance and output of our algorithm with other implementations in commodity computer algebra systems on nontrivial examples.
An efficient GPU acceptance-rejection algorithm for the selection of the next reaction to occur for Stochastic Simulation Algorithms
Venue: arXiv cs.CE 2014
Year: 2014

Motivation: The Stochastic Simulation Algorithm (SSA) has largely diffused in the field of systems biology. This approach needs many realizations for establishing statistical results on the system under study. It is very computationnally demanding, and with the advent of large models this burden is increasing. Hence parallel implementation of SSA are needed to address these needs. At the very heart of the SSA is the selection of the next reaction to occur at each time step, and to the best of our knowledge all implementations are based on an inverse transformation method. However, this method involves a random number of steps to select this next reaction and is poorly amenable to a parallel implementation. Results: Here, we introduce a parallel acceptance-rejection algorithm to select the K next reactions to occur. This algorithm uses a deterministic number of steps, a property well suited to a parallel implementation. It is simple and small, accurate and scalable. We propose a Graphics Processing Unit (GPU) implementation and validate our algorithm with simulated propensity distributions and the propensity distribution of a large model of yeast iron metabolism. We show that our algorithm can handle thousands of selections of next reaction to occur in parallel on the GPU, paving the way to massive SSA. Availability: We present our GPU-AR algorithm that focuses on the very heart of the SSA. We do not embed our algorithm within a full implementation in order to stay pedagogical and allows its rapid implementation in existing software. We hope that it will enable stochastic modelers to implement our algorithm with the benefits of their own optimizations.
Computing discrete logarithm by interval-valued paradigm
Venue: arXiv cs.DS 2014
Year: 2014

Interval-valued computing is a relatively new computing paradigm. It uses finitely many interval segments over the unit interval in a computation as data structure. The satisfiability of Quantified Boolean formulae and other hard problems, like integer factorization, can be solved in an effective way by its massive parallelism. The discrete logarithm problem plays an important role in practice, there are cryptographical methods based on its computational hardness. In this paper we show that the discrete logarithm problem is computable by an interval-valued computing in a polynomial number of steps (within this paradigm).
Throughput Analysis in CSMA/CA Networks using Continuous Time Markov Networks: A Tutorial
Venue: arXiv cs.NI 2014
Year: 2014

This book chapter introduces the use of Continuous Time Markov Networks (CTMN) to analytically capture the operation of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) networks. It is of tutorial nature, and it aims to be an introduction on this topic, providing a clear and easy-to-follow description. To illustrate how CTMN can be used, we introduce a set of representative and cutting-edge scenarios, such as Vehicular Ad-hoc Networks (VANETs), Power Line Communication networks and multiple overlapping Wireless Local Area Networks (WLANs). For each scenario, we describe the specific CTMN, obtain its stationary distribution and compute the throughput achieved by each node in the network. Taking the per-node throughput as reference, we discuss how the complex interactions between nodes using CSMA/CA have an impact on system performance.
Counting Triangulations and other Crossing-Free Structures Approximately
Venue: arXiv cs.CG 2014
Year: 2014

We consider the problem of counting straight-edge triangulations of a given set $P$ of $n$ points in the plane. Until very recently it was not known whether the exact number of triangulations of $P$ can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of $P$ can be computed in $O^{*}(2^{n})$ time, which is less than the lower bound of $Ω(2.43^{n})$ on the number of triangulations of any point set. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by $Λ$ the output of our algorithm, and by $c^{n}$ the exact number of triangulations of $P$, for some positive constant $c$, we prove that $c^{n}\leqΛ\leq c^{n}\cdot 2^{o(n)}$. This is the first algorithm that in sub-exponential time computes a $(1+o(1))$-approximation of the base of the number of triangulations, more precisely, $c\leqΛ^{\frac{1}{n}}\leq(1 + o(1))c$. Our algorithm can be adapted to approximately count other crossing-free structures on $P$, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees.
Sampling a Uniform Random Solution of a Quadratic Equation Modulo $p^k$
Venue: arXiv cs.DS 2014
Year: 2014

An $n$-ary integral quadratic form is a formal expression $Q(x_1,...,x_n)=\sum_{1\leq i,j\leq n}a_{ij}x_ix_j$ in $n$-variables $x_1,...,x_n$, where $a_{ij}=a_{ji} \in \mathbb{Z}$. We present a poly$(n,k, \log p, \log t)$ randomized algorithm that given a quadratic form $Q(x_1,...,x_n)$, a prime $p$, a positive integer $k$ and an integer $t$, samples a uniform solution of $Q(x_1,...,x_n)\equiv t \bmod{p^k}$.
Hyperprojective Hierarchy of QCB_0-spaces
Venue: arXiv cs.LO 2014
Year: 2014

We extend the Luzin hierarchy of qcb$_0$-spaces introduced in [ScS13] to all countable ordinals, obtaining in this way the hyperprojective hierarchy of qcb$_0$-spaces. We generalize all main results of [ScS13] to this larger hierarchy. In particular, we extend the Kleene-Kreisel continuous functionals of finite types to the continuous functionals of countable types and relate them to the new hierarchy. We show that the category of hyperprojective qcb$_0$-spaces has much better closure properties than the category of projective qcb$_0$-space. As a result, there are natural examples of spaces that are hyperprojective but not projective.
A Note on Randomized Element-wise Matrix Sparsification
Venue: arXiv cs.IT 2014
Year: 2014

Given a matrix A \in R^{m x n}, we present a randomized algorithm that sparsifies A by retaining some of its elements by sampling them according to a distribution that depends on both the square and the absolute value of the entries. We combine the ideas of [4, 1] and provide an elementary proof of the approximation accuracy of our algorithm following [4] without the truncation step.
Modelling the Self-similarity in Complex Networks Based on Coulomb's Law
Venue: arXiv cs.SI 2014
Year: 2014

Recently, self-similarity of complex networks have attracted much attention. Fractal dimension of complex network is an open issue. Hub repulsion plays an important role in fractal topologies. This paper models the repulsion among the nodes in the complex networks in calculation of the fractal dimension of the networks. The Coulomb's law is adopted to represent the repulse between two nodes of the network quantitatively. A new method to calculate the fractal dimension of complex networks is proposed. The Sierpinski triangle network and some real complex networks are investigated. The results are illustrated to show that the new model of self-similarity of complex networks is reasonable and efficient.
An Intensional Concurrent Faithful Encoding of Turing Machines
Venue: arXiv cs.FL 2014
Year: 2014

The benchmark for computation is typically given as Turing computability; the ability for a computation to be performed by a Turing Machine. Many languages exploit (indirect) encodings of Turing Machines to demonstrate their ability to support arbitrary computation. However, these encodings are usually by simulating the entire Turing Machine within the language, or by encoding a language that does an encoding or simulation itself. This second category is typical for process calculi that show an encoding of lambda-calculus (often with restrictions) that in turn simulates a Turing Machine. Such approaches lead to indirect encodings of Turing Machines that are complex, unclear, and only weakly equivalent after computation. This paper presents an approach to encoding Turing Machines into intensional process calculi that is faithful, reduction preserving, and structurally equivalent. The encoding is demonstrated in a simple asymmetric concurrent pattern calculus before generalised to simplify infinite terms, and to show encodings into Concurrent Pattern Calculus and Psi Calculi.
Weyl group orbit functions in image processing
Venue: arXiv cs.CV 2014
Year: 2014

We deal with the Fourier-like analysis of functions on discrete grids in two-dimensional simplexes using $C-$ and $E-$ Weyl group orbit functions. For these cases we present the convolution theorem. We provide an example of application of image processing using the $C-$ functions and the convolutions for spatial filtering of the treated image.
Labeling Schemes for Bounded Degree Graphs
Venue: arXiv cs.DM 2014
Year: 2014

We investigate adjacency labeling schemes for graphs of bounded degree $Δ= O(1)$. In particular, we present an optimal (up to an additive constant) $\log n + O(1)$ adjacency labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 10], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 02]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree $Δ$ with $(e+1)\sqrt{n} < Δ\leq n/5$.
Skybridge: 3-D Integrated Circuit Technology Alternative to CMOS
Venue: arXiv cs.ET 2014
Year: 2014

Continuous scaling of CMOS has been the major catalyst in miniaturization of integrated circuits (ICs) and crucial for global socio-economic progress. However, scaling to sub-20nm technologies is proving to be challenging as MOSFETs are reaching their fundamental limits and interconnection bottleneck is dominating IC operational power and performance. Migrating to 3-D, as a way to advance scaling, has eluded us due to inherent customization and manufacturing requirements in CMOS that are incompatible with 3-D organization. Partial attempts with die-die and layer-layer stacking have their own limitations. We propose a 3-D IC fabric technology, Skybridge[TM], which offers paradigm shift in technology scaling as well as design. We co-architect Skybridge's core aspects, from device to circuit style, connectivity, thermal management, and manufacturing pathway in a 3-D fabric-centric manner, building on a uniform 3-D template. Our extensive bottom-up simulations, accounting for detailed material system structures, manufacturing process, device, and circuit parasitics, carried through for several designs including a designed microprocessor, reveal a 30-60x density, 3.5x performance per watt benefits, and 10X reduction in interconnect lengths vs. scaled 16-nm CMOS. Fabric-level heat extraction features are shown to successfully manage IC thermal profiles in 3-D. Skybridge can provide continuous scaling of integrated circuits beyond CMOS in the 21st century.
Two Structural Results for Low Degree Polynomials and Applications
Venue: arXiv cs.CC 2014
Year: 2014

In this paper, two structural results concerning low degree polynomials over finite fields are given. The first states that over any finite field $\mathbb{F}$, for any polynomial $f$ on $n$ variables with degree $d \le \log(n)/10$, there exists a subspace of $\mathbb{F}^n$ with dimension $Ω(d \cdot n^{1/(d-1)})$ on which $f$ is constant. This result is shown to be tight. Stated differently, a degree $d$ polynomial cannot compute an affine disperser for dimension smaller than $Ω(d \cdot n^{1/(d-1)})$. Using a recursive argument, we obtain our second structural result, showing that any degree $d$ polynomial $f$ induces a partition of $F^n$ to affine subspaces of dimension $Ω(n^{1/(d-1)!})$, such that $f$ is constant on each part. We extend both structural results to more than one polynomial. We further prove an analog of the first structural result to sparse polynomials (with no restriction on the degree) and to functions that are close to low degree polynomials. We also consider the algorithmic aspect of the two structural results. Our structural results have various applications, two of which are: * Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over any finite field, any affine extractor is also an extractor for varieties with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over $F_2$. * Ben-Sasson and Kopparty [SIAM J. C 2012] proved that any degree 3 affine disperser over a prime field is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree.
Multi-objective Flower Algorithm for Optimization
Venue: arXiv cs.NE 2014
Year: 2014

Flower pollination algorithm is a new nature-inspired algorithm, based on the characteristics of flowering plants. In this paper, we extend this flower algorithm to solve multi-objective optimization problems in engineering. By using the weighted sum method with random weights, we show that the proposed multi-objective flower algorithm can accurately find the Pareto fronts for a set of test functions. We then solve a bi-objective disc brake design problem, which indeed converges quickly.