OpenRaiser/Intern-Atlas huggingface dataset:
Optimal amortized regret in every interval
Venue: arXiv cs.LG 2013
Year: 2013

Consider the classical problem of predicting the next bit in a sequence of bits. A standard performance measure is {\em regret} (loss in payoff) with respect to a set of experts. For example if we measure performance with respect to two constant experts one that always predicts 0's and another that always predicts 1's it is well known that one can get regret $O(\sqrt T)$ with respect to the best expert by using, say, the weighted majority algorithm. But this algorithm does not provide performance guarantee in any interval. There are other algorithms that ensure regret $O(\sqrt {x \log T})$ in any interval of length $x$. In this paper we show a randomized algorithm that in an amortized sense gets a regret of $O(\sqrt x)$ for any interval when the sequence is partitioned into intervals arbitrarily. We empirically estimated the constant in the $O()$ for $T$ upto 2000 and found it to be small -- around 2.1. We also experimentally evaluate the efficacy of this algorithm in predicting high frequency stock data.
Identifying Participants in the Personal Genome Project by Name (A Re-identification Experiment)
Venue: arXiv cs.CY 2013
Year: 2013

We linked names and contact information to publicly available profiles in the Personal Genome Project. These profiles contain medical and genomic information, including details about medications, procedures and diseases, and demographic information, such as date of birth, gender, and postal code. By linking demographics to public records such as voter lists, and mining for names hidden in attached documents, we correctly identified 84 to 97 percent of the profiles for which we provided names. Our ability to learn their names is based on their demographics, not their DNA, thereby revisiting an old vulnerability that could be easily thwarted with minimal loss of research value. So, we propose technical remedies for people to learn about their demographics to make better decisions.
Computing higher homotopy groups is W[1]-hard
Venue: arXiv cs.CC 2013
Year: 2013

Recently it was shown that, for every fixed k>1, given a finite simply connected simplicial complex X, the kth homotopy group π_k(X) can be computed in time polynomial in the number n of simplices of X. We prove that this problem is W[1]-hard w.r.t. the parameter k even for X of dimension 4, and thus very unlikely to admit an algorithm with running time bound f(k)n^C for an absolute constant C. We also simplify, by about 20 pages, a 1989 proof by Anick that, with k part of input, the computation of the rank of π_k(X) is #P-hard.
On the Capacity of the Finite Field Counterparts of Wireless Interference Networks
Venue: arXiv cs.IT 2013
Year: 2013

This work explores how degrees of freedom (DoF) results from wireless networks can be translated into capacity results for their finite field counterparts that arise in network coding applications. The main insight is that scalar (SISO) finite field channels over $\mathbb{F}_{p^n}$ are analogous to n x n vector (MIMO) channels in the wireless setting, but with an important distinction -- there is additional structure due to finite field arithmetic which enforces commutativity of matrix multiplication and limits the channel diversity to n, making these channels similar to diagonal channels in the wireless setting. Within the limits imposed by the channel structure, the DoF optimal precoding solutions for wireless networks can be translated into capacity optimal solutions for their finite field counterparts. This is shown through the study of the 2-user X channel and the 3-user interference channel. Besides bringing the insights from wireless networks into network coding applications, the study of finite field networks over $\mathbb{F}_{p^n}$ also touches upon important open problems in wireless networks (finite SNR, finite diversity scenarios) through interesting parallels between p and SNR, and n and diversity.
Characterization of Planar Cubic Alternative curve
Venue: arXiv cs.GR 2013
Year: 2013

In this paper, we analyze the planar cubic Alternative curve to determine the conditions for convex, loops, cusps and inflection points. Thus cubic curve is represented by linear combination of three control points and basis function that consist of two shape parameters. By using algebraic manipulation, we can determine the constraint of shape parameters and sufficient conditions are derived which ensure that the curve is a strictly convex, loops, cusps and inflection point. We conclude the result in a shape diagram of parameters. The simplicity of this form makes characterization more intuitive and efficient to compute.
Verified AIG Algorithms in ACL2
Venue: arXiv cs.LO 2013
Year: 2013

And-Inverter Graphs (AIGs) are a popular way to represent Boolean functions (like circuits). AIG simplification algorithms can dramatically reduce an AIG, and play an important role in modern hardware verification tools like equivalence checkers. In practice, these tricky algorithms are implemented with optimized C or C++ routines with no guarantee of correctness. Meanwhile, many interactive theorem provers can now employ SAT or SMT solvers to automatically solve finite goals, but no theorem prover makes use of these advanced, AIG-based approaches. We have developed two ways to represent AIGs within the ACL2 theorem prover. One representation, Hons-AIGs, is especially convenient to use and reason about. The other, Aignet, is the opposite; it is styled after modern AIG packages and allows for efficient algorithms. We have implemented functions for converting between these representations, random vector simulation, conversion to CNF, etc., and developed reasoning strategies for verifying these algorithms. Aside from these contributions towards verifying AIG algorithms, this work has an immediate, practical benefit for ACL2 users who are using GL to bit-blast finite ACL2 theorems: they can now optionally trust an off-the-shelf SAT solver to carry out the proof, instead of using the built-in BDD package. Looking to the future, it is a first step toward implementing verified AIG simplification algorithms that might further improve GL performance.
Fuzzy Based Diagnostics System for Identifying Network Traffic Flow Anomalies
Venue: arXiv cs.NI 2013
Year: 2013

This paper discusses the usage of network traffic properties in passive network monitoring which are used in recognizing and identifying anomaly.
Various Types of Aesthetic Curves
Venue: arXiv cs.GR 2013
Year: 2013

The research on developing planar curves to produce visually pleasing products (ranges from electric appliances to car body design) and indentifying/modifying planar curves for special purposes namely for railway design, highway design and robot trajectories have been progressing since 1970s. The pattern of research in this field of study has branched to five major groups namely curve synthesis, fairing process, improvement in control of natural spiral, construction of new type of planar curves and, natural spiral fitting & approximation techniques. The purpose of is this paper is to briefly review recent progresses in Computer Aided Geometric Design (CAGD) focusing on the topics states above.
IEEE 802.15.4 transceiver for the 868/915 MHz band using Software Defined Radio
Venue: arXiv cs.NI 2013
Year: 2013

This paper reports an implementation of the PHY specifications of the IEEE 802.15.4 standard for the frequency band 868 915 MHz on a Software Defined Radio (SDR) platform. This standard is defined for low power, low data rate and low cost wireless networks. These specifications are used by the Zigbee technology for various applications such as home automation, industry monitoring or medical surveillance. Several hardware PHY 868/915 MHz band IEEE 802.15.4 transceiver implementations have been already reported on ASIC and FPG [1] [2]. SDR offers one possibility to realize a transceiver with high flexibility and reconfigurability [3]. The whole transmitter and receiver chain has been defined in software using the GNU Radio software project [4] and the USRP (Universal Software Radio Peripheral) platform from Ettus Research [5]. Two new blocks have been added to the GNU Radio project, one for the Direct Sequence Spread Spectrum and the second for the reconstruction of the packets. The experimentations have been performed in a noisy environment and the PER, BER and SNR have been computed. The obtained results are coherent with what can be expected from the theory.
Fractal-Based Detection of Microcalcification Clusters in Digital Mammograms
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, a novel method for edge detection of microcalcification clusters in mammogram images is presented using the concept of Fractal Dimension and Hurst co-efficient that enables to locate the microcalcifications in the mammograms. This technique detects the edges accurately than the ones obtained by the conventional Sobel method. Generally, Sobel method detects the edges of the regions/objects in an image using the Fudge factor that assumes its value as 0.5, by default. In this proposed technique, the Fudge factor is suitably replaced with Hurst Co-efficient, which is computed as the difference of Fractal dimension and the topological dimension of a given input image. These two dimensions are image-dependent, and hence the respective Hurst co-efficient too varies with respect to images. Hence, the image-dependent Hurst co-efficient based Sobel method is proved to produce better results than the Fudge factor based Sobel method. The results of the proposed method substantiate the merit of the proposed technique.
Entropy, Optimization and Counting
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. Interest in such distributions arises due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and, more recently, approximation algorithms. A key difficulty in computing max-entropy distributions has been to show that they have polynomially-sized descriptions. We show that such descriptions exist under general conditions. Subsequently, we show how algorithms for (approximately) counting the underlying discrete set can be translated into efficient algorithms to (approximately) compute max-entropy distributions. In the reverse direction, we show how access to algorithms that compute max-entropy distributions can be used to count, which establishes an equivalence between counting and computing max-entropy distributions.
Unlinkable content playbacks in a multiparty DRM system
Venue: arXiv cs.CR 2013
Year: 2013

We present a solution to the problem of privacy invasion in a multiparty digital rights management scheme. (Roaming) users buy content licenses from a content provider and execute it at any nearby content distributor. Our approach, which does not need any trusted third party--in contrast to most related work on privacy-preserving DRM--is based on a re-encryption scheme that runs on any mobile Android device. Only a minor security-critical part needs to be performed on the device's smartcard which could, for instance, be a SIM card.
Local Graph Clustering Beyond Cheeger's Inequality
Venue: arXiv cs.DS 2013
Year: 2013

Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. All previously known such algorithms guarantee an output conductance of $\tilde{O}(\sqrt{ϕ(A)})$ when the target set $A$ has conductance $ϕ(A)\in[0,1]$. In this paper, we improve it to $$\tilde{O}\bigg( \min\Big\{\sqrt{ϕ(A)}, \frac{ϕ(A)}{\sqrt{\mathsf{Conn}(A)}} \Big\} \bigg)\enspace, $$ where the internal connectivity parameter $\mathsf{Conn}(A) \in [0,1]$ is defined as the reciprocal of the mixing time of the random walk over the induced subgraph on $A$. For instance, using $\mathsf{Conn}(A) = Ω(λ(A) / \log n)$ where $λ$ is the second eigenvalue of the Laplacian of the induced subgraph on $A$, our conductance guarantee can be as good as $\tilde{O}(ϕ(A)/\sqrt{λ(A)})$. This builds an interesting connection to the recent advance of the so-called improved Cheeger's Inequality [KKL+13], which says that global spectral algorithms can provide a conductance guarantee of $O(ϕ_{\mathsf{opt}}/\sqrt{λ_3})$ instead of $O(\sqrt{ϕ_{\mathsf{opt}}})$. In addition, we provide theoretical guarantee on the clustering accuracy (in terms of precision and recall) of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data. It is worth noting that, our analysis outperforms prior work when the cluster is well-connected. In fact, the better it is well-connected inside, the more significant improvement (both in terms of conductance and accuracy) we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering.
Perfectly normal type-2 fuzzy interpolation B-spline curve
Venue: arXiv cs.GR 2013
Year: 2013

In this paper, we proposed another new form of type-2 fuzzy data points(T2FDPs) that is perfectly normal type-2 data points(PNT2FDPs). These kinds of brand-new data were defined by using the existing type-2 fuzzy set theory(T2FST) and type-2 fuzzy number(T2FN) concept since we dealt with the problem of defining complex uncertainty data. Along with this restructuring, we included the fuzzification(alpha-cut operation), type-reduction and defuzzification processes against PNT2FDPs. In addition, we used interpolation B-soline curve function to demonstrate the PNT2FDPs.
A Community Based Algorithm for Large Scale Web Service Composition
Venue: arXiv cs.AI 2013
Year: 2013

Web service composition is the process of synthesizing a new composite service using a set of available Web services in order to satisfy a client request that cannot be treated by any available Web services. The Web services space is a dynamic environment characterized by a huge number of elements. Furthermore, many Web services are offering similar functionalities. In this paper we propose a model for Web service composition designed to address the scale effect and the redundancy issue. The Web services space is represented by a two-layered network architecture. A concrete similarity network layer organizes the Web services operations into communities of functionally similar operations. An abstract interaction network layer represents the composition relationships between the sets of communities. Composition synthesis is performed by a two-phased graph search algorithm. First, the interaction network is mined in order to discover abstract solutions to the request goal. Then, the abstract compositions are instantiated with concrete operations selected from the similarity network. This strategy allows an efficient exploration of the Web services space. Furthermore, operations grouped in a community can be easily substituted if necessary during the composition's synthesis's process.
Analyzing Web Services Networks: a WS-NEXT Application
Venue: arXiv cs.SE 2013
Year: 2013

Web services represent a system with a huge number of units and many various and complex interactions. Complex networks as a tool for modelling and analyzing natural environments seem to be well adapted to such a complex system. To describe a set of Web services we propose three Web services network models based on the notions of dependency, interaction and similarity. Using the WS-NEXT extractor we instantiate the models with a collection of Web services descriptions. We take advantage of complex network properties to provide an analyzis of the Web services networks. Those networks and the knowledge of their toplogical properties can be exploited for the discovery and composition processes.
Matrix Compression using the Nystroöm Method
Venue: arXiv cs.NA 2013
Year: 2013

The Nyström method is routinely used for out-of-sample extension of kernel matrices. We describe how this method can be applied to find the singular value decomposition (SVD) of general matrices and the eigenvalue decomposition (EVD) of square matrices. We take as an input a matrix $M\in \mathbb{R}^{m\times n}$, a user defined integer $s\leq min(m,n)$ and $A_M \in \mathbb{R}^{s\times s}$, a matrix sampled from the columns and rows of $M$. These are used to construct an approximate rank-$s$ SVD of $M$ in $O\left(s^2\left(m+n\right)\right)$ operations. If $M$ is square, the rank-$s$ EVD can be similarly constructed in $O\left(s^2 n\right)$ operations. Thus, the matrix $A_M$ is a compressed version of $M$. We discuss the choice of $A_M$ and propose an algorithm that selects a good initial sample for a pivoted version of $M$. The proposed algorithm performs well for general matrices and kernel matrices whose spectra exhibit fast decay.
Perceptron Mistake Bounds
Venue: arXiv cs.LG 2013
Year: 2013

We present a brief survey of existing mistake bounds and introduce novel bounds for the Perceptron or the kernel Perceptron algorithm. Our novel bounds generalize beyond standard margin-loss type bounds, allow for any convex and Lipschitz loss function, and admit a very simple proof.
Bio-imitaiton of Mexican migration routes to the USA with slime mould on 3D terrains
Venue: arXiv cs.ET 2013
Year: 2013

Plasmodium of Physarum polycephalum is a large single cell visible by unaided eye. It shows sophisticated behavioural traits in foraging for nutrients and developing an optimal transport network of protoplasmic tubes spanning sources of nutrients. When placed in an environment with distributed sources of nutrients the cell 'computes' an optimal graph spanning the nutrients by growing a network of protoplasmic tubes. P. polycephalum imitates development of man-made transport networks of a country when configuration of nutrients represents major urban areas. We employ this feature of the slime mould to imitate mexican migration to USA. The Mexican migration to USA is the World's largest migration system. We bio-physically imitate the migration using slime mould P. polycephalum. In laboratory experiments with 3D Nylon terrains of USA we imitated development of migratory routes from Mexico-USA border to ten urban areas with high concentration of Mexican migrants. From results of laboratory experiments we extracted topologies of migratory routes, and highlighted a role of elevations in shaping the human movement networks.
A Markovian Model for Assessing the Consistency of Vehicular Storage Systems
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we evaluate the suitability of the vehicular devices for supporting data storage and distribution applications. Vehicular storage systems have recently emerged as means for making the information related to the vehicular environment available to vehicular users. Information could either be collected by sensors mounted onboard vehicles or coming from the surrounding environment. Modeling a vehicular data storage and distribution system requires the introduction of a number of parameters, such as the vehicle concentration and transmission range, the value of which may determine the suitability or unsuitability of the vehicular environment for establishing a communication infrastructure with the desired quality. In this paper we show how to solve this problem by resorting to a Markovian model and some results achieved through its application.
Filter Design with Secrecy Constraints: The MIMO Gaussian Wiretap Channel
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the problem of filter design with secrecy constraints, where two legitimate parties (Alice and Bob) communicate in the presence of an eavesdropper (Eve), over a Gaussian multiple-input-multiple-output (MIMO) wiretap channel. This problem involves designing, subject to a power constraint, the transmit and the receive filters which minimize the mean-squared error (MSE) between the legitimate parties whilst assuring that the eavesdropper MSE remains above a certain threshold. We consider a general MIMO Gaussian wiretap scenario, where the legitimate receiver uses a linear Zero-Forcing (ZF) filter and the eavesdropper receiver uses either a ZF or an optimal linear Wiener filter. We provide a characterization of the optimal filter designs by demonstrating the convexity of the optimization problems. We also provide generalizations of the filter designs from the scenario where the channel state is known to all the parties to the scenario where there is uncertainty in the channel state. A set of numerical results illustrates the performance of the novel filter designs, including the robustness to channel modeling errors. In particular, we assess the efficacy of the designs in guaranteeing not only a certain MSE level at the eavesdropper, but also in limiting the error probability at the eavesdropper. We also assess the impact of the filter designs on the achievable secrecy rates. The penalty induced by the fact that the eavesdropper may use the optimal non-linear receive filter rather than the optimal linear one is also explored in the paper.
Deep Learning of Representations: Looking Forward
Venue: arXiv cs.LG 2013
Year: 2013

Deep learning research aims at discovering learning algorithms that discover multiple levels of distributed representations, with higher levels representing more abstract concepts. Although the study of deep learning has already led to impressive theoretical results, learning algorithms and breakthrough experiments, several challenges lie ahead. This paper proposes to examine some of these challenges, centering on the questions of scaling deep learning algorithms to much larger models and datasets, reducing optimization difficulties due to ill-conditioning or local minima, designing more efficient and powerful inference and sampling procedures, and learning to disentangle the factors of variation underlying the observed data. It also proposes a few forward-looking research directions aimed at overcoming these challenges.
Complexity Theory for Operators in Analysis
Venue: arXiv cs.CC 2013
Year: 2013

We propose an extension of the framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that can be represented only through approximation. The key idea is to use (a certain class of) string functions as names representing these objects. These are more expressive than infinite sequences, which served as names in prior work that formulated complexity in more restricted settings. An advantage of using string functions is that we can define their "size" in the way inspired by higher-type complexity theory. This enables us to talk about computation on string functions whose time or space is bounded polynomially in the input size, giving rise to more general analogues of the classes P, NP, and PSPACE. We also define NP- and PSPACE-completeness under suitable many-one reductions. Because our framework separates machine computation and semantics, it can be applied to problems on sets of interest in analysis once we specify a suitable representation (encoding). As prototype applications, we consider the complexity of functions (operators) on real numbers, real sets, and real functions. For example, the task of numerical algorithms for solving a certain class of differential equations is naturally viewed as an operator taking real functions to real functions. As there was no complexity theory for operators, previous results only stated how complex the solution can be. We now reformulate them and show that the operator itself is polynomial-space complete.