OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Graph Stream Algorithms in $o(n)$ Space
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we study graph problems in dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require $Ω(n)$ space, where $n$ is the number of vertices, existing works mainly focused on designing $\tilde{O}(n)$ space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e.g. $n$ is huge or the graph is sparse). In this work, we give single-pass algorithms beating this space barrier for two classes of problems. We present $o(n)$ space algorithms for estimating the number of connected components with additive error $\varepsilon n$ and $(1+\varepsilon)$-approximating the weight of minimum spanning tree, for any small constant $\varepsilon>0$. The latter improves previous $\tilde{O}(n)$ space algorithm given by Ahn et al. (SODA 2012) for connected graphs with bounded edge weights. We initiate the study of approximate graph property testing in the dynamic streaming model, where we want to distinguish graphs satisfying the property from graphs that are $\varepsilon$-far from having the property. We consider the problem of testing $k$-edge connectivity, $k$-vertex connectivity, cycle-freeness and bipartiteness (of planar graphs), for which, we provide algorithms using roughly $\tilde{O}(n^{1-\varepsilon})$ space, which is $o(n)$ for any constant $\varepsilon$. To complement our algorithms, we present $Ω(n^{1-O(\varepsilon)})$ space lower bounds for these problems, which show that such a dependence on $\varepsilon$ is necessary.
A Note on the Exact Schedulability Analysis for Segmented Self-Suspending Systems
Venue: arXiv cs.DS 2016
Year: 2016

This report considers a sporadic real-time task system with $n$ sporadic tasks on a uniprocessor platform, in which the lowest-priority task is a segmented self-suspension task and the other higher-priority tasks are ordinary sporadic real-time tasks. This report proves that the schedulability analysis for fixed-priority preemptive scheduling even with only one segmented self-suspending task as the lowest-priority task is $co{\cal NP}$-hard in the strong sense. Under fixed-priority preemptive scheduling, Nelissen et al. in ECRTS 2015 provided a mixed-integer linear programming (MILP) formulation to calculate an upper bound on the worst-case response time of the lowest-priority self-suspending task. This report provides a comprehensive support to explain several hidden properties that were not provided in their paper. We also provide an input task set to explain why the resulting solution of their MILP formulation can be quite far from the exact worst-case response time.
3D Keypoint Detection Based on Deep Neural Network with Sparse Autoencoder
Venue: arXiv cs.CV 2016
Year: 2016

Researchers have proposed various methods to extract 3D keypoints from the surface of 3D mesh models over the last decades, but most of them are based on geometric methods, which lack enough flexibility to meet the requirements for various applications. In this paper, we propose a new method on the basis of deep learning by formulating the 3D keypoint detection as a regression problem using deep neural network (DNN) with sparse autoencoder (SAE) as our regression model. Both local information and global information of a 3D mesh model in multi-scale space are fully utilized to detect whether a vertex is a keypoint or not. SAE can effectively extract the internal structure of these two kinds of information and formulate high-level features for them, which is beneficial to the regression model. Three SAEs are used to formulate the hidden layers of the DNN and then a logistic regression layer is trained to process the high-level features produced in the third SAE. Numerical experiments show that the proposed DNN based 3D keypoint detection algorithm outperforms current five state-of-the-art methods for various 3D mesh models.
On Leader Green Election
Venue: arXiv cs.DS 2016
Year: 2016

We investigate the number of survivors in the Leader Green Election (LGE) algorithm introduced by P. Jacquet, D. Milioris and P. Muhlethaler in 2013. Our method is based on the Rice method and gives quite precise formulas. We derive upper bounds on the number of survivors in this algorithm and we propose a proper use of LGE. Finally, we discuss one property of a general urns and balls problem and show a lower bound for a required number of rounds for a large class of distributed leader election protocols.
Random cluster dynamics for the Ising model is rapidly mixing
Venue: arXiv cs.DS 2016
Year: 2016

We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at $q=2$ is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.
On Optimal Offline Time Sharing Policy for Energy Harvesting Underlay Cognitive Radio
Venue: arXiv cs.IT 2016
Year: 2016

RF energy harvesting can be used to power communication devices so that perpetual operation of such devices can be ensured. We consider a RF energy harvesting underlay cognitive radio system operating in slotted fashion. The primary user (PU) is equipped with a reliable power source and transmits with a constant power in all the slots. However, the secondary user (SU) harvests energy from primary's transmission and simultaneously transmits it's own data such that interference at the primary receiver (PR) remains below an acceptable threshold. At the secondary transmitter (ST), each time slot is divided into two phases: energy harvesting (EH) phase and information transfer (IT) phase. We formulated the problem of maximizing the achievable secondary sum rate under primary receiver's protection criteria as a convex optimization problem and obtained the optimal time sharing between EH and IT phase, and optimal secondary transmit power under offline setting. The optimal offline scheme is then compared with an online myopic policy, where the optimal time sharing between EH and IT phase, and optimal secondary transmit power are obtained based on instantaneous channel gains only.
Common-Description Learning: A Framework for Learning Algorithms and Generating Subproblems from Few Examples
Venue: arXiv cs.AI 2016
Year: 2016

Current learning algorithms face many difficulties in learning simple patterns and using them to learn more complex ones. They also require more examples than humans do to learn the same pattern, assuming no prior knowledge. In this paper, a new learning framework is introduced that is called common-description learning (CDL). This framework has been tested on 32 small multi-task datasets, and the results show that it was able to learn complex algorithms from a few number of examples. The final model is perfectly interpretable and its depth depends on the question. What is meant by depth here is that whenever needed, the model learns to break down the problem into simpler subproblems and solves them using previously learned models. Finally, we explain the capabilities of our framework in discovering complex relations in data and how it can help in improving language understanding in machines.
A vector-contraction inequality for Rademacher complexities
Venue: arXiv cs.LG 2016
Year: 2016

The contraction inequality for Rademacher averages is extended to Lipschitz functions with vector-valued domains, and it is also shown that in the bounding expression the Rademacher variables can be replaced by arbitrary iid symmetric and sub-gaussian variables. Example applications are given for multi-category learning, K-means clustering and learning-to-learn.
Uncertain Wiretap Channels and Secure Estimation
Venue: arXiv cs.SY 2016
Year: 2016

Uncertain wiretap channels are introduced. Their zero-error secrecy capacity is defined. If the sensor-estimator channel is perfect, it is also calculated. Further properties are discussed. The problem of estimating a dynamical system with nonstochastic disturbances is studied where the sensor is connected to the estimator and an eavesdropper via an uncertain wiretap channel. The estimator should obtain a uniformly bounded estimation error whereas the eavesdropper's error should tend to infinity. It is proved that the system can be estimated securely if the zero-error capacity of the sensor-estimator channel is strictly larger than the logarithm of the system's unstable pole and the zero-error secrecy capacity of the uncertain wiretap channel is positive.
Edge Caching for Coverage and Capacity-aided Heterogeneous Networks
Venue: arXiv cs.IT 2016
Year: 2016

A two-tier heterogeneous cellular network (HCN) with intra-tier and inter-tier dependence is studied. The macro cell deployment follows a Poisson point process (PPP) and two different clustered point processes are used to model the cache-enabled small cells. Under this model, we derive approximate expressions in terms of finite integrals for the average delivery rate considering inter-tier and intra-tier dependence. On top of the fact that cache size drastically improves the performance of small cells in terms of average delivery rate, we show that rate splitting of limited-backhaul induces non-linear performance variations, and therefore has to be adjusted for rate fairness among users of different tiers.
Adaptive Modulation in Network-coded Two-way Relay Channel: A Supermodular Game Approach
Venue: arXiv cs.IT 2016
Year: 2016

We study the adaptive modulation (AM) problem in a network-coded two-way relay channel (NC-TWRC), where each of the two users controls its own bit rate in the $m$-ary quadrature amplitude modulation ($m$-QAM) to minimize the transmission error rate and enhance the spectral efficiency. We show that there exists a strategic complementarity, one user tends to transmit while the other decides to do so in order to enhance the overall spectral efficiency, which is beyond the scope of the conventional single-agent AM scheduling method. We propose a two-player game model parameterized by the signal-to-noise ratios (SNRs) of two user-to-user channels and prove that it is a supermodular game where there always exist the extremal pure strategy Nash equilibria (PSNEs), the largest and smallest PSNEs. We show by simulation results that the extremal PSNEs incur a similar bit error rate (BER) as the conventional single-agent AM scheme, but significantly improve the spectral efficiency in the NC-TWRC system. The study also reveals the Pareto order of the extremal PSNEs: The largest and smallest PSNEs are Pareto worst and best PSNEs, respectively. Finally, we derive the sufficient conditions for the extremal PSNEs to be symmetric and monotonic in channel SNRs. We also discuss how to utilize the symmetry and monotonicity to relieve the complexity in the PSNE learning process.
Some Insights into the Geometry and Training of Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

Neural networks have been successfully used for classification tasks in a rapidly growing number of practical applications. Despite their popularity and widespread use, there are still many aspects of training and classification that are not well understood. In this paper we aim to provide some new insights into training and classification by analyzing neural networks from a feature-space perspective. We review and explain the formation of decision regions and study some of their combinatorial aspects. We place a particular emphasis on the connections between the neural network weight and bias terms and properties of decision boundaries and other regions that exhibit varying levels of classification confidence. We show how the error backpropagates in these regions and emphasize the important role they have in the formation of gradients. These findings expose the connections between scaling of the weight parameters and the density of the training samples. This sheds more light on the vanishing gradient problem, explains the need for regularization, and suggests an approach for subsampling training data to improve performance.
Parameter estimation for linear control valve with hysteresis
Venue: arXiv cs.SY 2016
Year: 2016

The problem of estimating parameters of linear control valve with hysteresis is considered. The hysteretic behavior of control valve is formulated as a switched linear model. An indicator vector, which shows the switching epochs of switched linear model, is explored by subspace decomposition on measurements. With the help of indicator vector, the noisy measurements are classified into separate groups, each corresponding to up-stroke and down-stroke of control valve respectively. The least squares technique is adopted to estimate the parameters of control valve. It is shown that the proposed technique exactly estimates the parameters and switching epochs in absence of noise and exhibits dominant advantage in noisy case.
Formal Analysis of Vulnerabilities of Web Applications Based on SQL Injection (Extended Version)
Venue: arXiv cs.CR 2016
Year: 2016

We present a formal approach that exploits attacks related to SQL Injection (SQLi) searching for security flaws in a web application. We give a formal representation of web applications and databases, and show that our formalization effectively exploits SQLi attacks. We implemented our approach in a prototype tool called SQLfast and we show its efficiency on real-world case studies, including the discovery of an attack on Joomla! that no other tool can find.
The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
Venue: arXiv cs.FL 2016
Year: 2016

A non-deterministic recursion scheme recognizes a language of finite trees. This very expressive model can simulate, among others, higher-order pushdown automata with collapse. We show decidability of the diagonal problem for schemes. This result has several interesting consequences. In particular, it gives an algorithm that computes the downward closure of languages of words recognized by schemes. In turn, this has immediate application to separability problems and reachability analysis of concurrent systems.
Hybrid Spectrum Access for mmWave Networks
Venue: arXiv cs.NI 2016
Year: 2016

While spectrum at millimeter wave (mmWave) frequencies is less scarce than at traditional frequencies below 6 GHz, still it is not unlimited, in particular if we consider the requirements from other services using the same band and the need to license mmWave bands to multiple mobile operators. Therefore, an efficient spectrum access scheme is critical to harvest the maximum benefit from emerging mmWave technologies. In this paper, motivated by previous results where spectrum pooling was proved to be more feasible at high mmWave frequencies, we study the performance of a hybrid spectrum scheme where exclusive access is used at frequencies in the 20/30 GHz range while spectrum pooling/unlicensed spectrum is used at frequencies around 70 GHz. Our preliminary results show that hybrid spectrum access is a promising approach for mmWave networks, and motivate further studies to achieve a more complete understanding of both technical and non technical implications.
An Enhanced Harmony Search Method for Bangla Handwritten Character Recognition Using Region Sampling
Venue: arXiv cs.CV 2016
Year: 2016

Identification of minimum number of local regions of a handwritten character image, containing well-defined discriminating features which are sufficient for a minimal but complete description of the character is a challenging task. A new region selection technique based on the idea of an enhanced Harmony Search methodology has been proposed here. The powerful framework of Harmony Search has been utilized to search the region space and detect only the most informative regions for correctly recognizing the handwritten character. The proposed method has been tested on handwritten samples of Bangla Basic, Compound and mixed (Basic and Compound characters) characters separately with SVM based classifier using a longest run based feature-set obtained from the image subregions formed by a CG based quad-tree partitioning approach. Applying this methodology on the above mentioned three types of datasets, respectively 43.75%, 12.5% and 37.5% gains have been achieved in terms of region reduction and 2.3%, 0.6% and 1.2% gains have been achieved in terms of recognition accuracy. The results show a sizeable reduction in the minimal number of descriptive regions as well a significant increase in recognition accuracy for all the datasets using the proposed technique. Thus the time and cost related to feature extraction is decreased without dampening the corresponding recognition accuracy.
Munchausen Iteration
Venue: arXiv cs.SC 2016
Year: 2016

We present a method for solving polynomial equations over idempotent omega-continuous semirings. The idea is to iterate over the semiring of functions rather than the semiring of interest, and only evaluate when needed. The key operation is substitution. In the initial step, we compute a linear completion of the system of equations that exhaustively inserts the equations into one another. With functions as approximants, the following steps insert the current approximant into itself. Since the iteration improves its precision by substitution rather than computation we named it Munchausen, after the fictional baron that pulled himself out of a swamp by his own hair. The first result shows that an evaluation of the n-th Munchausen approximant coincides with the 2^n-th Newton approximant. Second, we show how to compute linear completions with standard techniques from automata theory. In particular, we are not bound to (but can use) the notion of differentials prominent in Newton iteration.
An Electric Vehicle Charging Management Scheme Based on Publish/Subscribe Communication Framework
Venue: arXiv cs.NI 2016
Year: 2016

Motivated by alleviating CO$_2$ pollution, Electric Vehicle (EV) based applications have recently received wide interests from both commercial and research communities by using electric energy instead of traditional fuel energy. Although EVs are inherently with limited travelling distance, such limitation could be overcome by deploying public Charging Stations (CSs) to recharge EVs battery during their journeys. In this paper we propose a novel communication framework for on-the-move EV charging scenario, based on the Publish/Subscribe (P/S) mechanism for disseminating necessary CS information to EVs, in order for them to make optimized decisions on where to charge. A core part of our communication framework is the utilization of Road Side Units (RSUs) to bridge the information flow from CSs to EVs, which has been regarded as a type of cost-efficient communication infrastructure. Under this design, we introduce two complementary communication modes of signalling protocols, namely Push and Pull Modes, in order to enable the required information dissemination operation. Both analysis and simulation show the advantage of Pull Mode, in which the information is cached at RSUs to support asynchronous communication. We further propose a remote reservation service based on the Pull Mode, such that the CS-selection decision making can utilize the knowledge of EVs' charging reservation, as published from EVs through RSUs to CSs. Results show that both the performance at CS and EV sides are further improved based on using this anticipated information.
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
Venue: arXiv cs.IT 2016
Year: 2016

Two sets $A, B \subseteq \{0, 1\}^n$ form a Uniquely Decodable Code Pair (UDCP) if every pair $a \in A$, $b \in B$ yields a distinct sum $a+b$, where the addition is over $\mathbb{Z}^n$. We show that every UDCP $A, B$, with $|A| = 2^{(1-ε)n}$ and $|B| = 2^{βn}$, satisfies $β\leq 0.4228 +\sqrtε$. For sufficiently small $ε$, this bound significantly improves previous bounds by Urbanke and Li~[Information Theory Workshop '98] and Ordentlich and Shayevitz~[2014, arXiv:1412.8415], which upper bound $β$ by $0.4921$ and $0.4798$, respectively, as $ε$ approaches $0$.
Compositional Sentence Representation from Character within Large Context Text
Venue: arXiv cs.CL 2016
Year: 2016

This paper describes a Hierarchical Composition Recurrent Network (HCRN) consisting of a 3-level hierarchy of compositional models: character, word and sentence. This model is designed to overcome two problems of representing a sentence on the basis of a constituent word sequence. The first is a data-sparsity problem in word embedding, and the other is a no usage of inter-sentence dependency. In the HCRN, word representations are built from characters, thus resolving the data-sparsity problem, and inter-sentence dependency is embedded into sentence representation at the level of sentence composition. We adopt a hierarchy-wise learning scheme in order to alleviate the optimization difficulties of learning deep hierarchical recurrent network in end-to-end fashion. The HCRN was quantitatively and qualitatively evaluated on a dialogue act classification task. Especially, sentence representations with an inter-sentence dependency are able to capture both implicit and explicit semantics of sentence, significantly improving performance. In the end, the HCRN achieved state-of-the-art performance with a test error rate of 22.7% for dialogue act classification on the SWBD-DAMSL database.
Quantifying the changing role of past publications
Venue: arXiv cs.DL 2016
Year: 2016

Our current societies increasingly rely on electronic repositories of collective knowledge. An archetype of these databases is the Web of Science (WoS) that stores scientific publications. In contrast to several other forms of knowledge -- e.g., Wikipedia articles -- a scientific paper does not change after its "birth". Nonetheless, from the moment a paper is published it exists within the evolving web of other papers, thus, its actual meaning to the reader changes. To track how scientific ideas (represented by groups of scientific papers) appear and evolve, we apply a novel combination of algorithms explicitly allowing for papers to change their groups. We (i) identify the overlapping clusters of the undirected yearly co-citation networks of the WoS (1975-2008) and (ii) match these yearly clusters (groups) to form group timelines. After visualizing the longest lived groups of the entire data set we assign topic labels to the groups. We find that in the entire Web of Science multidisciplinarity is clearly over-represented among cutting edge ideas. In addition, we provide detailed examples for papers that (i) change their topic labels and (ii) move between groups.
Comparison of Optimization Methods in Optical Flow Estimation
Venue: arXiv cs.CV 2016
Year: 2016

Optical flow estimation is a widely known problem in computer vision introduced by Gibson, J.J(1950) to describe the visual perception of human by stimulus objects. Estimation of optical flow model can be achieved by solving for the motion vectors from region of interest in the the different timeline. In this paper, we assumed slightly uniform change of velocity between two nearby frames, and solve the optical flow problem by traditional method, Lucas-Kanade(1981). This method performs minimization of errors between template and target frame warped back onto the template. Solving minimization steps requires optimization methods which have diverse convergence rate and error. We explored first and second order optimization methods, and compare their results with Gauss-Newton method in Lucas-Kanade. We generated 105 videos with 10,500 frames by synthetic objects, and 10 videos with 1,000 frames from real world footage. Our experimental results could be used as tuning parameters for Lucas-Kanade method.