OpenRaiser/Intern-Atlas huggingface dataset:
Universal Memcomputing Machines
Venue: arXiv cs.NE 2014
Year: 2014

We introduce the notion of universal memcomputing machines (UMMs): a class of brain-inspired general-purpose computing machines based on systems with memory, whereby processing and storing of information occur on the same physical location. We analytically prove that the memory properties of UMMs endow them with universal computing power - they are Turing-complete -, intrinsic parallelism, functional polymorphism, and information overhead, namely their collective states can support exponential data compression directly in memory. We also demonstrate that a UMM has the same computational power as a non-deterministic Turing machine, namely it can solve NP--complete problems in polynomial time. However, by virtue of its information overhead, a UMM needs only an amount of memory cells (memprocessors) that grows polynomially with the problem size. As an example we provide the polynomial-time solution of the subset-sum problem and a simple hardware implementation of the same. Even though these results do not prove the statement NP=P within the Turing paradigm, the practical realization of these UMMs would represent a paradigm shift from present von Neumann architectures bringing us closer to brain-like neural computation.
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
Venue: arXiv cs.DS 2014
Year: 2014

We study the ATSP (Asymmetric Traveling Salesman Problem), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result pertains to the standard LP (linear programming) relaxation of ATSP, due to Dantzig, Fulkerson, and Johnson. For any fixed integer $t\geq 0$ and small $ε$, $0<ε\ll{1}$, there exists a digraph $G$ on $ν=ν(t,ε)=O(t/ε)$ vertices such that the integrality ratio for level~$t$ of the SA system starting with the standard LP on $G$ is $\ge 1+\frac{1-ε}{2t+3} \approx \frac43, \frac65, \frac87, \dots$. Thus, in terms of the input size, the result holds for any $t = 0,1,\dots,Θ(ν)$ levels. Our key contribution is to identify a structural property of digraphs that allows us to construct fractional feasible solutions for any level~$t$ of the SA system starting from the standard~LP. Our hard instances are simple and satisfy the structural property. There is a further relaxation of the standard LP called the balanced LP, and our methods simplify considerably when the starting LP for the SA system is the balanced~LP; in particular, the relevant structural property (of digraphs) simplifies such that it is satisfied by the digraphs given by the well-known construction of Charikar, Goemans and Karloff (CGK). Consequently, the CGK digraphs serve as hard instances, and we obtain an integrality ratio of $1 +\frac{1-ε}{t+1}$ for any level~$t$ of the SA system, where $0<ε\ll{1}$ and the number of vertices is $ν(t,ε)=O((t/ε)^{(t/ε)})$. Also, our results for the standard~LP extend to the Path-ATSP (find a min cost Hamiltonian dipath from a given source vertex to a given sink vertex).
Convex recovery of a structured signal from independent random linear measurements
Venue: arXiv cs.IT 2014
Year: 2014

This chapter develops a theoretical analysis of the convex programming method for recovering a structured signal from independent random linear measurements. This technique delivers bounds for the sampling complexity that are similar with recent results for standard Gaussian measurements, but the argument applies to a much wider class of measurement ensembles. To demonstrate the power of this approach, the paper presents a short analysis of phase retrieval by trace-norm minimization. The key technical tool is a framework, due to Mendelson and coauthors, for bounding a nonnegative empirical process.
On the Two-user Interference Channel with Lack of Knowledge of the Interference Codebook at one Receiver
Venue: arXiv cs.IT 2014
Year: 2014

In multi-user information theory it is often assumed that every node in the network possesses all codebooks used in the network. This assumption may be impractical in distributed ad-hoc, cognitive or heterogeneous networks. This work considers the two-user Interference Channel with one Oblivious Receiver (IC-OR), i.e., one receiver lacks knowledge of the interfering cookbook while the other receiver knows both codebooks. The paper asks whether, and if so how much, the channel capacity of the IC-OR is reduced compared to that of the classical IC where both receivers know all codebooks. A novel outer bound is derived and shown to be achievable to within a gap for the class of injective semi-deterministic IC-ORs; the gap is shown to be zero for injective fully deterministic IC-ORs. For the linear deterministic IC-OR that models the Gaussian noise channel at high SNR, non i.i.d. Bernoulli(1/2) input bits are shown to achieve points not achievable by i.i.d. Bernoulli(1/2) input bits used in the same achievability scheme. For the real-valued Gaussian IC-OR the gap is shown to be at most 1/2 bit per channel use, even though the set of optimal input distributions for the derived outer bound could not be determined. Towards understanding the Gaussian IC-OR, an achievability strategy is evaluated in which the input alphabets at the non-oblivious transmitter are a mixture of discrete and Gaussian random variables, where the cardinality of the discrete part is appropriately chosen as a function of the channel parameters. Surprisingly, as the oblivious receiver intuitively should not be able to 'jointly decode' the intended and interfering messages (whose codebook is unavailable), it is shown that with this choice of input, the capacity region of the symmetric Gaussian IC-OR is to within 3.34 bits (per channel use per user) of an outer bound for the classical Gaussian IC with full codebook knowledge.
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Venue: arXiv cs.DS 2014
Year: 2014

Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Unlike the well-understood case of MIS in graphs, for the hypergraph problem, our knowledge is quite limited despite considerable work. It is known that the problem is in \emph{RNC} when the edges of the hypergraph have constant size. For general hypergraphs with $n$ vertices and $m$ edges, the fastest previously known algorithm works in time $O(\sqrt{n})$ with $\text{poly}(m,n)$ processors. In this paper we give an EREW PRAM algorithm that works in time $n^{o(1)}$ with $\text{poly}(m,n)$ processors on general hypergraphs satisfying $m \leq n^{\frac{\log^{(2)}n}{8(\log^{(3)}n)^2}}$, where $\log^{(2)}n = \log\log n$ and $\log^{(3)}n = \log\log\log n$. Our algorithm is based on a sampling idea that reduces the dimension of the hypergraph and employs the algorithm for constant dimension hypergraphs as a subroutine.
Analysis of Degrees of Freedom of Wideband Random Multipath Fields Observed Over Time and Space Windows
Venue: arXiv cs.IT 2014
Year: 2014

In multipath systems, available degrees of freedom can be considered as a key performance indicator, since the channel capacity grows linearly with the available degrees of freedom. However, a fundamental question arises: given a size limitation on the observable region, what is the intrinsic number of degrees of freedom available in a wideband random multipath wavefield observed over a finite time interval? In this paper, we focus on answering this question by modelling the wavefield as a sum of orthogonal waveforms or spatial orders. We show that for each spatial order, (i) the observable wavefield is band limited within an effective bandwidth rather than the given bandwidth and (ii) the observation time varies from the given observation time. These findings show the strong coupling between space and time as well as space and bandwidth. In effect, for spatially diverse multipath wavefields, the classical degrees of freedom result of "time-bandwidth" product does not directly extend to "time-space-bandwidth" product.
Self-Healing Computation
Venue: arXiv cs.DC 2014
Year: 2014

In the problem of reliable multiparty computation (RC), there are $n$ parties, each with an individual input, and the parties want to jointly compute a function $f$ over $n$ inputs. The problem is complicated by the fact that an omniscient adversary controls a hidden fraction of the parties. We describe a self-healing algorithm for this problem. In particular, for a fixed function $f$, with $n$ parties and $m$ gates, we describe how to perform RC repeatedly as the inputs to $f$ change. Our algorithm maintains the following properties, even when an adversary controls up to $t \leq (\frac{1}{4} - ε) n$ parties, for any constant $ε>0$. First, our algorithm performs each reliable computation with the following amortized resource costs: $O(m + n \log n)$ messages, $O(m + n \log n)$ computational operations, and $O(\ell)$ latency, where $\ell$ is the depth of the circuit that computes $f$. Second, the expected total number of corruptions is $O(t (\log^{*} m)^2)$, after which the adversarially controlled parties are effectively quarantined so that they cause no more corruptions.
Semantically Guided Evolution of $\mathcal{SHI}$ ABoxes
Venue: arXiv cs.LO 2014
Year: 2014

This paper presents a method for the evolution of SHI ABoxes which is based on a compilation technique of the knowledge base. For this the ABox is regarded as an interpretation of the TBox which is close to a model. It is shown, that the ABox can be used for a semantically guided transformation resulting in an equisatisfiable knowledge base. We use the result of this transformation to efficiently delete assertions from the ABox. Furthermore, insertion of assertions as well as repair of inconsistent ABoxes is addressed. For the computation of the necessary actions for deletion, insertion and repair, the E-KRHyper theorem prover is used.
Quantization and Compressive Sensing
Venue: arXiv cs.IT 2014
Year: 2014

Quantization is an essential step in digitizing signals, and, therefore, an indispensable component of any modern acquisition system. This book chapter explores the interaction of quantization and compressive sensing and examines practical quantization strategies for compressive acquisition systems. Specifically, we first provide a brief overview of quantization and examine fundamental performance bounds applicable to any quantization approach. Next, we consider several forms of scalar quantizers, namely uniform, non-uniform, and 1-bit. We provide performance bounds and fundamental analysis, as well as practical quantizer designs and reconstruction algorithms that account for quantization. Furthermore, we provide an overview of Sigma-Delta ($ΣΔ$) quantization in the compressed sensing context, and also discuss implementation issues, recovery algorithms and performance bounds. As we demonstrate, proper accounting for quantization and careful quantizer design has significant impact in the performance of a compressive acquisition system.
Nuclear Norm based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes
Venue: arXiv cs.CV 2014
Year: 2014

Recently regression analysis becomes a popular tool for face recognition. The existing regression methods all use the one-dimensional pixel-based error model, which characterizes the representation error pixel by pixel individually and thus neglects the whole structure of the error image. We observe that occlusion and illumination changes generally lead to a low-rank error image. To make use of this low-rank structural information, this paper presents a two-dimensional image matrix based error model, i.e. matrix regression, for face representation and classification. Our model uses the minimal nuclear norm of representation error image as a criterion, and the alternating direction method of multipliers method to calculate the regression coefficients. Compared with the current regression methods, the proposed Nuclear Norm based Matrix Regression (NMR) model is more robust for alleviating the effect of illumination, and more intuitive and powerful for removing the structural noise caused by occlusion. We experiment using four popular face image databases, the Extended Yale B database, the AR database, the Multi-PIE and the FRGC database. Experimental results demonstrate the performance advantage of NMR over the state-of-the-art regression based face recognition methods.
Human Pose Estimation from RGB Input Using Synthetic Training Data
Venue: arXiv cs.CV 2014
Year: 2014

We address the problem of estimating the pose of humans using RGB image input. More specifically, we are using a random forest classifier to classify pixels into joint-based body part categories, much similar to the famous Kinect pose estimator [11], [12]. However, we are using pure RGB input, i.e. no depth. Since the random forest requires a large number of training examples, we are using computer graphics generated, synthetic training data. In addition, we assume that we have access to a large number of real images with bounding box labels, extracted for example by a pedestrian detector or a tracking system. We propose a new objective function for random forest training that uses the weakly labeled data from the target domain to encourage the learner to select features that generalize from the synthetic source domain to the real target domain. We demonstrate on a publicly available dataset [6] that the proposed objective function yields a classifier that significantly outperforms a baseline classifier trained using the standard entropy objective [10].
Classic Lagrangian may not be applicable to the traveling salesman problem
Venue: arXiv cs.DS 2014
Year: 2014

In this short note, the dual problem for the traveling salesman problem is constructed through the classic Lagrangian. The existence of optimality conditions is expressed as a corresponding inverse problem. A general 4-cities instance is given, and the numerical experiment shows that the classic Lagrangian may not be applicable to the traveling salesman problem.
Comparative Study of the Function Overloading and Function Overriding Using C++
Venue: arXiv cs.PL 2014
Year: 2014

In the Object-Oriented Programming Systems (OOPS), these two concepts namely function overloading and function overriding are a bit confusing to the programmers. In this article this confusion is tried to be removed. Both of these are the concepts which come under the polymorphism (poly means many and morph mean forms). In the article the comparison is done in between them. For the new programmers and the learners, it is important to understand them. The function overloading [1] is achieved at the time of the compile and the function overriding is achieved at the run time. The function overriding always takes place in inheritance, but the function overloading can also take place without inheritance.
General upper bounds for well-behaving goodness measures on dependency rules
Venue: arXiv cs.DB 2014
Year: 2014

In the search for statistical dependency rules, a crucial task is to restrict the search space by estimating upper bounds for the goodness of yet undiscovered rules. In this paper, we show that all well-behaving goodness measures achieve their maximal values in the same points. Therefore, the same generic search strategy can be applied with any of these measures. The notion of well-behaving measures is based on the classical axioms for any proper goodness measures, and extended to negative dependencies, as well. As an example, we show that several commonly used goodness measures are well-behaving.
How Community Feedback Shapes User Behavior
Venue: arXiv cs.SI 2014
Year: 2014

Social media systems rely on user feedback and rating mechanisms for personalization, ranking, and content filtering. However, when users evaluate content contributed by fellow users (e.g., by liking a post or voting on a comment), these evaluations create complex social feedback effects. This paper investigates how ratings on a piece of content affect its author's future behavior. By studying four large comment-based news communities, we find that negative feedback leads to significant behavioral changes that are detrimental to the community. Not only do authors of negatively-evaluated content contribute more, but also their future posts are of lower quality, and are perceived by the community as such. Moreover, these authors are more likely to subsequently evaluate their fellow users negatively, percolating these effects through the community. In contrast, positive feedback does not carry similar effects, and neither encourages rewarded authors to write more, nor improves the quality of their posts. Interestingly, the authors that receive no feedback are most likely to leave a community. Furthermore, a structural analysis of the voter network reveals that evaluations polarize the community the most when positive and negative votes are equally split.
An Exploration of the Role of Principal Inertia Components in Information Theory
Venue: arXiv cs.IT 2014
Year: 2014

The principal inertia components of the joint distribution of two random variables $X$ and $Y$ are inherently connected to how an observation of $Y$ is statistically related to a hidden variable $X$. In this paper, we explore this connection within an information theoretic framework. We show that, under certain symmetry conditions, the principal inertia components play an important role in estimating one-bit functions of $X$, namely $f(X)$, given an observation of $Y$. In particular, the principal inertia components bear an interpretation as filter coefficients in the linear transformation of $p_{f(X)|X}$ into $p_{f(X)|Y}$. This interpretation naturally leads to the conjecture that the mutual information between $f(X)$ and $Y$ is maximized when all the principal inertia components have equal value. We also study the role of the principal inertia components in the Markov chain $B\rightarrow X\rightarrow Y\rightarrow \widehat{B}$, where $B$ and $\widehat{B}$ are binary random variables. We illustrate our results for the setting where $X$ and $Y$ are binary strings and $Y$ is the result of sending $X$ through an additive noise binary channel.
A Novel Approach to Finding Near-Cliques: The Triangle-Densest Subgraph Problem
Venue: arXiv cs.DS 2014
Year: 2014

Many graph mining applications rely on detecting subgraphs which are near-cliques. There exists a dichotomy between the results in the existing work related to this problem: on the one hand the densest subgraph problem (DSP) which maximizes the average degree over all subgraphs is solvable in polynomial time but for many networks fails to find subgraphs which are near-cliques. On the other hand, formulations that are geared towards finding near-cliques are NP-hard and frequently inapproximable due to connections with the Maximum Clique problem. In this work, we propose a formulation which combines the best of both worlds: it is solvable in polynomial time and finds near-cliques when the DSP fails. Surprisingly, our formulation is a simple variation of the DSP. Specifically, we define the triangle densest subgraph problem (TDSP): given $G(V,E)$, find a subset of vertices $S^*$ such that $τ(S^*)=\max_{S \subseteq V} \frac{t(S)}{|S|}$, where $t(S)$ is the number of triangles induced by the set $S$. We provide various exact and approximation algorithms which the solve the TDSP efficiently. Furthermore, we show how our algorithms adapt to the more general problem of maximizing the $k$-clique average density. Finally, we provide empirical evidence that the TDSP should be used whenever the output of the DSP fails to output a near-clique.
Events and Controversies: Influences of a Shocking News Event on Information Seeking
Venue: arXiv cs.IR 2014
Year: 2014

It has been suggested that online search and retrieval contributes to the intellectual isolation of users within their preexisting ideologies, where people's prior views are strengthened and alternative viewpoints are infrequently encountered. This so-called "filter bubble" phenomenon has been called out as especially detrimental when it comes to dialog among people on controversial, emotionally charged topics, such as the labeling of genetically modified food, the right to bear arms, the death penalty, and online privacy. We seek to identify and study information-seeking behavior and access to alternative versus reinforcing viewpoints following shocking, emotional, and large-scale news events. We choose for a case study to analyze search and browsing on gun control/rights, a strongly polarizing topic for both citizens and leaders of the United States. We study the period of time preceding and following a mass shooting to understand how its occurrence, follow-on discussions, and debate may have been linked to changes in the patterns of searching and browsing. We employ information-theoretic measures to quantify the diversity of Web domains of interest to users and understand the browsing patterns of users. We use these measures to characterize the influence of news events on these web search and browsing patterns.
Mostly Sunny: A Forecast of Tomorrow's Power Index Research
Venue: arXiv cs.GT 2014
Year: 2014

Power index research has been a very active field in the last decades. Will this continue or are all the important questions solved? We argue that there are still many opportunities to conduct useful research with and on power indices. Positive and normative questions keep calling for theoretical and empirical attention. Technical and technological improvements are likely to boost applicability.
ACO-ESSVHOA - Ant Colony Optimization based Multi-Criteria Decision Making for Efficient Signal Selection in Mobile Vertical Handoff
Venue: arXiv cs.NI 2014
Year: 2014

The process of Vertical handoff has become one of the major components of today's wireless environment due to the availability of the vast variety of signals. The decision for a handoff should be performed catering to the needs of the current transmission that is being carried out. Our paper describes a modified Ant Colony Optimization based handoff mechanism, that considers multiple criteria in its decision making process rather than a single parameter (pheromone intensity). In general, ACO considers the pheromone intensity and the evaporation rates as the parameters for selecting a route. In this paper, we describe a mechanism that determines the evaporation rates of each path connected to the source using various criteria, which in turn reflects on the pheromone levels present in the path and hence the probability of selecting that route. Experiments show that our process exhibits better convergence rates, hence better usability.
Initial Comparison of Linguistic Networks Measures for Parallel Texts
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents preliminary results of Croatian syllable networks analysis. Syllable network is a network in which nodes are syllables and links between them are constructed according to their connections within words. In this paper we analyze networks of syllables generated from texts collected from the Croatian Wikipedia and Blogs. As a main tool we use complex network analysis methods which provide mechanisms that can reveal new patterns in a language structure. We aim to show that syllable networks have much higher clustering coefficient in comparison to Erdös-Renyi random networks. The results indicate that Croatian syllable networks exhibit certain properties of a small world networks. Furthermore, we compared Croatian syllable networks with Portuguese and Chinese syllable networks and we showed that they have similar properties.