OpenRaiser/Intern-Atlas huggingface dataset:
Near-Optimal Distributed Maximum Flow
Venue: arXiv cs.DS 2015
Year: 2015

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tildeΩ(D+ \sqrt{n})$ round complexity lower bound. The development of the algorithm contains two results of independent interest: (i) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of an $n^{o(1)}$-congestion approximator consisting of the cuts induced by $O(\log n)$ virtual trees. The distributed representation of the cut approximator allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.
A Computer-Based Method to Improve the Spelling of Children with Dyslexia
Venue: arXiv cs.HC 2015
Year: 2015

In this paper we present a method which aims to improve the spelling of children with dyslexia through playful and targeted exercises. In contrast to previous approaches, our method does not use correct words or positive examples to follow, but presents the child a misspelled word as an exercise to solve. We created these training exercises on the basis of the linguistic knowledge extracted from the errors found in texts written by children with dyslexia. To test the effectiveness of this method in Spanish, we integrated the exercises in a game for iPad, DysEggxia (Piruletras in Spanish), and carried out a within-subject experiment. During eight weeks, 48 children played either DysEggxia or Word Search, which is another word game. We conducted tests and questionnaires at the beginning of the study, after four weeks when the games were switched, and at the end of the study. The children who played DysEggxia for four weeks in a row had significantly less writing errors in the tests that after playing Word Search for the same time. This provides evidence that error-based exercises presented in a tablet help children with dyslexia improve their spelling skills.
A Unified Fading Model Using Infinitely Divisible Distributions
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes to unify fading distributions by modeling the magnitude-squared of the instantaneous channel gain as an infinitely divisible random variable. A random variable is said to be infinitely divisible, if it can be written as a sum of $n \geq 1$ independent and identically distributed random variables, for each $n$. Infinitely divisible random variables have many interesting mathematical properties, which can be applied in the performance analysis of wireless systems. It is shown that the proposed unification subsumes several unifications of fading distributions previously proposed in the wireless communications literature. In fact, almost every distribution used to model multipath, shadowing and composite multipath/shadowing is shown to be included in the class of infinitely divisible random variables.
Analyzing Organizational Routines in Online Knowledge Collaborations: A Case for Sequence Analysis in CSCW
Venue: arXiv cs.SI 2015
Year: 2015

Research into socio-technical systems like Wikipedia has overlooked important structural patterns in the coordination of distributed work. This paper argues for a conceptual reorientation towards sequences as a fundamental unit of analysis for understanding work routines in online knowledge collaboration. We outline a research agenda for researchers in computer-supported cooperative work (CSCW) to understand the relationships, patterns, antecedents, and consequences of sequential behavior using methods already developed in fields like bio-informatics. Using a data set of 37,515 revisions from 16,616 unique editors to 96 Wikipedia articles as a case study, we analyze the prevalence and significance of different sequences of editing patterns. We illustrate the mixed method potential of sequence approaches by interpreting the frequent patterns as general classes of behavioral motifs. We conclude by discussing the methodological opportunities for using sequence analysis for expanding existing approaches to analyzing and theorizing about co-production routines in online knowledge collaboration.
Passenger Flow Predictions at Sydney International Airport: A Data-Driven Queuing Approach
Venue: arXiv cs.OH 2015
Year: 2015

Time spent in processing zones at an airport are an important part of the passenger's airport experience. It undercuts the time spent in the rest of the airport, and therefore the revenue that could be generated from shopping and dining. It can also result in passengers missing flights and connections, which has significant operational repercussions. Inadequate staffing levels are often to blame for large congestion at an airport. In this paper, we present a stochastic simulation that estimates the operational uncertainty in passenger processing at immigration. Congestion and delays are estimated on arrivals and departures based on scheduled flight departures and arrivals. We demonstrate the use of cellular tracking data in refining the model, and an approach to controlling congestion by adjusting staffing levels.
Executable Behaviour and the π-Calculus (extended abstract)
Venue: arXiv cs.LO 2015
Year: 2015

Reactive Turing machines extend classical Turing machines with a facility to model observable interactive behaviour. We call a behaviour executable if, and only if, it is behaviourally equivalent to the behaviour of a reactive Turing machine. In this paper, we study the relationship between executable behaviour and behaviour that can be specified in the pi-calculus. We establish that all executable behaviour can be specified in the pi-calculus up to divergence-preserving branching bisimilarity. The converse, however, is not true due to (intended) limitations of the model of reactive Turing machines. That is, the pi-calculus allows the specification of behaviour that is not executable up to divergence-preserving branching bisimilarity. Motivated by an intuitive understanding of executability, we then consider a restriction on the operational semantics of the pi-calculus that does associate with every pi-term executable behaviour, at least up to the version of branching bisimilarity that does not require the preservation of divergence.
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Venue: arXiv cs.DS 2015
Year: 2015

We improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set $K\subset \mathbb{R}^n$ contained in a box of radius $R$, we show how to either find a point in $K$ or prove that $K$ does not contain a ball of radius $ε$ using an expected $O(n\log(nR/ε))$ oracle evaluations and additional time $O(n^3\log^{O(1)}(nR/ε))$. This matches the oracle complexity and improves upon the $O(n^{ω+1}\log(nR/ε))$ additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya for the current matrix multiplication constant $ω<2.373$ when $R/ε=n^{O(1)}$. Using a mix of standard reductions and new techniques, our algorithm yields improved runtimes for solving classic problems in continuous and combinatorial optimization: Submodular Minimization: Our weakly and strongly polynomial time algorithms have runtimes of $O(n^2\log nM\cdot\text{EO}+n^3\log^{O(1)}nM)$ and $O(n^3\log^2 n\cdot\text{EO}+n^4\log^{O(1)}n)$, improving upon the previous best of $O((n^4\text{EO}+n^5)\log M)$ and $O(n^5\text{EO}+n^6)$. Matroid Intersection: Our runtimes are $O(nrT_{\text{rank}}\log n\log (nM) +n^3\log^{O(1)}(nM))$ and $O(n^2\log (nM) T_{\text{ind}}+n^3 \log^{O(1)} (nM))$, achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle. Submodular Flow: Our runtime is $O(n^2\log nCU\cdot\text{EO}+n^3\log^{O(1)}nCU)$, improving upon the previous bests from 15 years ago roughly by a factor of $O(n^4)$. Semidefinite Programming: Our runtime is $\tilde{O}(n(n^2+m^ω+S))$, improving upon the previous best of $\tilde{O}(n(n^ω+m^ω+S))$ for the regime where the number of nonzeros $S$ is small.
Histogram of gradients of Time-Frequency Representations for Audio scene detection
Venue: arXiv cs.SD 2015
Year: 2015

This paper addresses the problem of audio scenes classification and contributes to the state of the art by proposing a novel feature. We build this feature by considering histogram of gradients (HOG) of time-frequency representation of an audio scene. Contrarily to classical audio features like MFCC, we make the hypothesis that histogram of gradients are able to encode some relevant informations in a time-frequency {representation:} namely, the local direction of variation (in time and frequency) of the signal spectral power. In addition, in order to gain more invariance and robustness, histogram of gradients are locally pooled. We have evaluated the relevance of {the novel feature} by comparing its performances with state-of-the-art competitors, on several datasets, including a novel one that we provide, as part of our contribution. This dataset, that we make publicly available, involves $19$ classes and contains about $900$ minutes of audio scene recording. We thus believe that it may be the next standard dataset for evaluating audio scene classification algorithms. Our comparison results clearly show that our HOG-based features outperform its competitors
Diving Deep into Sentiment: Understanding Fine-tuned CNNs for Visual Sentiment Prediction
Venue: arXiv cs.MM 2015
Year: 2015

Visual media are powerful means of expressing emotions and sentiments. The constant generation of new content in social networks highlights the need of automated visual sentiment analysis tools. While Convolutional Neural Networks (CNNs) have established a new state-of-the-art in several vision problems, their application to the task of sentiment analysis is mostly unexplored and there are few studies regarding how to design CNNs for this purpose. In this work, we study the suitability of fine-tuning a CNN for visual sentiment prediction as well as explore performance boosting techniques within this deep learning setting. Finally, we provide a deep-dive analysis into a benchmark, state-of-the-art network architecture to gain insight about how to design patterns for CNNs on the task of visual sentiment prediction.
Finite Length Analysis of Caching-Aided Coded Multicasting
Venue: arXiv cs.IT 2015
Year: 2015

In this work, we study a noiseless broadcast link serving $K$ users whose requests arise from a library of $N$ files. Every user is equipped with a cache of size $M$ files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches, it requires at most $N/M$ file transmissions for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file $F$ scales to infinity. In this work, we initiate the finite-length analysis of random caching schemes when the number of packets $F$ is a function of the system parameters $M,N,K$. Specifically, we show that existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of $2$ if the number of packets is sub-exponential. Further, for any clique cover based coded delivery and a large class of random caching schemes, that includes the existing ones, we show that the number of packets required to get a multiplicative gain of $\frac{4}{3}g$ is at least $O((N/M)^g)$. We exhibit a random placement and an efficient clique cover based coded delivery scheme that approximately achieves this lower bound. We also provide tight concentration results that show that the average (over the random caching involved) number of transmissions concentrates very well requiring only polynomial number of packets in the rest of the parameters.
On the Limits of Predictability in Real-World Radio Spectrum State Dynamics: From Entropy Theory to 5G Spectrum Sharing
Venue: arXiv cs.NI 2015
Year: 2015

A range of applications in cognitive radio networks, from adaptive spectrum sensing to predictive spectrum mobility and dynamic spectrum access, depend on our ability to foresee the state evolution of radio spectrum, raising a fundamental question: To what degree is radio spectrum state (RSS) predictable? In this paper, we explore the fundamental limits of predictability in RSS dynamics by studying the RSS evolution patterns in spectrum bands of several popular services, including TV bands, ISM bands, and Cellular bands, etc. From an information theory perspective, we introduce a methodology of using statistical entropy measures and Fano inequality to quantify the degree of predictability underlying real-world spectrum measurements. Despite the apparent randomness, we find a remarkable predictability, as large as 90%, in the real-world RSS dynamics over a number of spectrum bands for all popular services. Furthermore, we discuss the potential applications of prediction-based spectrum sharing in 5G wireless communications.
POLYANA - A tool for the calculation of molecular radial distribution functions based on Molecular Dynamics trajectories
Venue: arXiv cs.MS 2015
Year: 2015

We present an application for the calculation of radial distribution functions for molecular centres of mass, based on trajectories generated by molecular simulation methods (Molecular Dynamics, Monte Carlo). When designing this application, the emphasis was placed on ease of use as well as ease of further development. In its current version, the program can read trajectories generated by the well-known DL_POLY package, but it can be easily extended to treat other formats. It is also very easy to 'hack' the program so it can compute intermolecular radial distribution functions for groups of interaction sites rather than whole molecules.
WalkieLokie: Relative Positioning for Augmented Reality Using a Dummy Acoustic Speaker
Venue: arXiv cs.CY 2015
Year: 2015

We propose and implement a novel relative positioning system, WalkieLokie, to enable more kinds of Augmented Reality applications, e.g., virtual shopping guide, virtual business card sharing. WalkieLokie calculates the distance and direction between an inquiring user and the corresponding target. It only requires a dummy speaker binding to the target and broadcasting inaudible acoustic signals. Then the user walking around can obtain the position using a smart device. The key insight is that when a user walks, the distance between the smart device and the speaker changes; and the pattern of displacement (variance of distance) corresponds to the relative position. We use a second-order phase locked loop to track the displacement and further estimate the position. To enhance the accuracy and robustness of our strategy, we propose a synchronization mechanism to synthesize all estimation results from different timeslots. We show that the mean error of ranging and direction estimation is 0.63m and 2.46 degrees respectively, which is accurate even in case of virtual business card sharing. Furthermore, in the shopping mall where the environment is quite severe, we still achieve high accuracy of positioning one dummy speaker, and the mean position error is 1.28m.
Constructing bent functions and bent idempotents of any possible algebraic degrees
Venue: arXiv cs.IT 2015
Year: 2015

Bent functions as optimal combinatorial objects are difficult to characterize and construct. In the literature, bent idempotents are a special class of bent functions and few constructions have been presented, which are restricted by the degree of finite fields and have algebraic degree no more than 4. In this paper, several new infinite families of bent functions are obtained by adding the the algebraic combination of linear functions to some known bent functions and their duals are calculated. These bent functions contain some previous work on infinite families of bent functions by Mesnager \cite{M2014} and Xu et al. \cite{XCX2015}. Further, infinite families of bent idempotents of any possible algebraic degree are constructed from any quadratic bent idempotent. To our knowledge, it is the first univariate representation construction of infinite families of bent idempotents over $\mathbb{F}_{2^{2m}}$ of algebraic degree between 2 and $m$, which solves the open problem on bent idempotents proposed by Carlet \cite{C2014}. And an infinite family of anti-self-dual bent functions are obtained. The sum of three anti-self-dual bent functions in such a family is also anti-self-dual bent and belongs to this family. This solves the open problem proposed by Mesnager \cite{M2014}.
Morphometry-Based Longitudinal Neurodegeneration Simulation with MR Imaging
Venue: arXiv cs.CV 2015
Year: 2015

We present a longitudinal MR simulation framework which simulates the future neurodegenerative progression by outputting the predicted follow-up MR image and the voxel-based morphometry (VBM) map. This framework expects the patients to have at least 2 historical MR images available. The longitudinal and cross-sectional VBM maps are extracted to measure the affinity between the target subject and the template subjects collected for simulation. Then the follow-up simulation is performed by resampling the latest available target MR image with a weighted sum of non-linear transformations derived from the best-matched templates. The leave-one-out strategy was used to compare different simulation methods. Compared to the state-of-the-art voxel-based method, our proposed morphometry-based simulation achieves better accuracy in most cases.
Optimization of an Adaptive Frequency-Hopping Network
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes a methodology for optimizing a frequency-hopping network that uses continuous-phase frequency-shift keying and adaptive capacity-approaching channel coding. The optimization takes into account the spatial distribution of the interfering mobiles, Nakagami fading, and lognormal shadowing. It includes the effects of both co-channel interference and adjacent-channel interference, which arises due to spectral-splatter effects. The average network performance depends on the choice of the modulation index, the number of frequency-hopping channels, and the fractional in-band power, which are assumed to be fixed network parameters. The performance of a given transmission depends on the code rate, which is adapted in response to the interference to meet a constraint on outage probability. The optimization proceeds by choosing a set of fixed network parameters, drawing the interferers from the spatial distribution, and determining the maximum rate that satisfies the outage constraint. The process is repeated for a large number of network realizations, and the fixed network parameters that maximize the area spectral efficiency are identified.
Optimizing MDS Codes for Caching at the Edge
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we investigate the problem of optimal MDS-encoded cache placement at the wireless edge to minimize the backhaul rate in heterogeneous networks. We derive the backhaul rate performance of any caching scheme based on file splitting and MDS encoding and we formulate the optimal caching scheme as a convex optimization problem. We then thoroughly investigate the performance of this optimal scheme for an important heterogeneous network scenario. We compare it to several other caching strategies and we analyze the influence of the system parameters, such as the popularity and size of the library files and the capabilities of the small-cell base stations, on the overall performance of our optimal caching strategy. Our results show that the careful placement of MDS-encoded content in caches at the wireless edge leads to a significant decrease of the load of the network backhaul and hence to a considerable performance enhancement of the network.
Shapes From Pixels
Venue: arXiv cs.IT 2015
Year: 2015

Continuous-domain visual signals are usually captured as discrete (digital) images. This operation is not invertible in general, in the sense that the continuous-domain signal cannot be exactly reconstructed based on the discrete image, unless it satisfies certain constraints (\emph{e.g.}, bandlimitedness). In this paper, we study the problem of recovering shape images with smooth boundaries from a set of samples. Thus, the reconstructed image is constrained to regenerate the same samples (consistency), as well as forming a shape (bilevel) image. We initially formulate the reconstruction technique by minimizing the shape perimeter over the set of consistent binary shapes. Next, we relax the non-convex shape constraint to transform the problem into minimizing the total variation over consistent non-negative-valued images. We also introduce a requirement (called reducibility) that guarantees equivalence between the two problems. We illustrate that the reducibility property effectively sets a requirement on the minimum sampling density. One can draw analogy between the reducibility property and the so-called restricted isometry property (RIP) in compressed sensing which establishes the equivalence of the $\ell_0$ minimization with the relaxed $\ell_1$ minimization. We also evaluate the performance of the relaxed alternative in various numerical experiments.
A sum form functional equation on a closed domain and its role in information theory
Venue: arXiv cs.IT 2015
Year: 2015

This paper is devoted to finding the general solutions of the functional equation $\sumin \sumjm h(p_iq_j)=\sumin h(p_i)+\sumjm k_j(q_j)+λ\sumin h(p_i)\sumjm k_j(q_j)$ valid for all complete probability distributions $(p_1,\ldots,p_n)$, $(q_1,\ldots,q_m)$, $0\le p_i\le 1$, $0\le q_j\le 1$, $i=1,\ldots,n$; $j=1,\ldots,m$, $\sumin p_i=1$, $\sumjm q_j=1$; $n\ge 3$, $m\ge 3$ fixed integers; $λ\in\RR$, $λ\neq 0$ and the mappings $h:I\to\RR$, $k_j:I\to\RR$, $j=1,\ldots,m$; $I=[0,1]$, $\RR$ denoting the set of all real numbers. A special case of the above functional equation was treated earlier by L. Losonczi and Gy. Maksa.