OpenRaiser/Intern-Atlas huggingface dataset:
Signed graph embedding: when everybody can sit closer to friends than enemies
Venue: arXiv cs.DM 2014
Year: 2014

Signed graphs are graphs with signed edges. They are commonly used to represent positive and negative relationships in social networks. While balance theory and clusterizable graphs deal with signed graphs to represent social interactions, recent empirical studies have proved that they fail to reflect some current practices in real social networks. In this paper we address the issue of drawing signed graphs and capturing such social interactions. We relax the previous assumptions to define a drawing as a model in which every vertex has to be placed closer to its neighbors connected via a positive edge than its neighbors connected via a negative edge in the resulting space. Based on this definition, we address the problem of deciding whether a given signed graph has a drawing in a given $\ell$-dimensional Euclidean space. We present forbidden patterns for signed graphs that admit the introduced definition of drawing in the Euclidean plane and line. We then focus on the $1$-dimensional case, where we provide a polynomial time algorithm that decides if a given complete signed graph has a drawing, and constructs it when applicable.
An optimization algorithm inspired by the States of Matter that improves the balance between exploration and exploitation
Venue: arXiv cs.AI 2014
Year: 2014

The ability of an Evolutionary Algorithm (EA) to find a global optimal solution depends on its capacity to find a good rate between exploitation of found so far elements and exploration of the search space. Inspired by natural phenomena, researchers have developed many successful evolutionary algorithms which, at original versions, define operators that mimic the way nature solves complex problems, with no actual consideration of the exploration/exploitation balance. In this paper, a novel nature-inspired algorithm called the States of Matter Search (SMS) is introduced. The SMS algorithm is based on the simulation of the states of matter phenomenon. In SMS, individuals emulate molecules which interact to each other by using evolutionary operations which are based on the physical principles of the thermal-energy motion mechanism. The algorithm is devised by considering each state of matter at one different exploration/exploitation ratio. The evolutionary process is divided into three phases which emulate the three states of matter: gas, liquid and solid. In each state, molecules (individuals) exhibit different movement capacities. Beginning from the gas state (pure exploration), the algorithm modifies the intensities of exploration and exploitation until the solid state (pure exploitation) is reached. As a result, the approach can substantially improve the balance between exploration/exploitation, yet preserving the good search capabilities of an evolutionary approach.
The Impact of Disjunction on Reasoning under Existential Rules: Research Summary
Venue: arXiv cs.DB 2014
Year: 2014

Datalog+/- is a Datalog-based language family enhanced with existential quantification in rule heads, equalities and negative constraints. Query answering over databases with respect to a Datalog+/- theory is generally undecidable, however several syntactic restrictions have been proposed to remedy this fact. However, a useful and natural feature however is as of yet missing from Datalog+/-: The ability to express uncertain knowledge, or choices, using disjunction. It is the precise objective of the doctoral thesis herein discussed, to investigate the impact on the complexity of query answering, of adding disjunction to well-known decidable Datalog+/- fragments, namely guarded, sticky and weakly-acyclic Datalog+/- theories. For guarded theories with disjunction, we obtain a strong 2EXP lower bound in the combined complexity, even for very restricted formalisms like fixed sets of (disjunctive) inclusion dependencies. For sticky theories, the query answering problem becomes undecidable, even in the data complexity, and for weakly-acyclic query answering we see a reasonable and expected increase in complexity.
Approximate resilience, monotonicity, and the complexity of agnostic learning
Venue: arXiv cs.LG 2014
Year: 2014

A function $f$ is $d$-resilient if all its Fourier coefficients of degree at most $d$ are zero, i.e., $f$ is uncorrelated with all low-degree parities. We study the notion of $\mathit{approximate}$ $\mathit{resilience}$ of Boolean functions, where we say that $f$ is $α$-approximately $d$-resilient if $f$ is $α$-close to a $[-1,1]$-valued $d$-resilient function in $\ell_1$ distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class $C$ over the uniform distribution. Roughly speaking, if all functions in a class $C$ are far from being $d$-resilient then $C$ can be learned agnostically in time $n^{O(d)}$ and conversely, if $C$ contains a function close to being $d$-resilient then agnostic learning of $C$ in the statistical query (SQ) framework of Kearns has complexity of at least $n^{Ω(d)}$. This characterization is based on the duality between $\ell_1$ approximation by degree-$d$ polynomials and approximate $d$-resilience that we establish. In particular, it implies that $\ell_1$ approximation by low-degree polynomials, known to be sufficient for agnostic learning over product distributions, is in fact necessary. Focusing on monotone Boolean functions, we exhibit the existence of near-optimal $α$-approximately $\widetildeΩ(α\sqrt{n})$-resilient monotone functions for all $α>0$. Prior to our work, it was conceivable even that every monotone function is $Ω(1)$-far from any $1$-resilient function. Furthermore, we construct simple, explicit monotone functions based on ${\sf Tribes}$ and ${\sf CycleRun}$ that are close to highly resilient functions. Our constructions are based on a fairly general resilience analysis and amplification. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas.
Secure Anonymous Broadcast
Venue: arXiv cs.DC 2014
Year: 2014

In anonymous broadcast, one or more parties want to anonymously send messages to all parties. This problem is increasingly important as a black-box in many privacy-preserving applications such as anonymous communication, distributed auctions, and multi-party computation. In this paper, we design decentralized protocols for anonymous broadcast that require each party to send (and compute) a polylogarithmic number of bits (and operations) per anonymous bit delivered with $O(\log n)$ rounds of communication. Our protocol is provably secure against traffic analysis, does not require any trusted party, and is completely load-balanced. The protocol tolerates up to $n/6$ statically-scheduled Byzantine parties that are controlled by a computationally unbounded adversary. Our main strategy for achieving scalability is to perform local communications (and computations) among a logarithmic number of parties. We provide simulation results to show that our protocol improves significantly over previous work. We finally show that using a common cryptographic tool in our protocol one can achieve practical results for anonymous broadcast.
A fast algorithm for computing the characteristic polynomial of the p-curvature
Venue: arXiv cs.SC 2014
Year: 2014

We discuss theoretical and algorithmic questions related to the $p$-curvature of differential operators in characteristic $p$. Given such an operator $L$, and denoting by $\Chi(L)$ the characteristic polynomial of its $p$-curvature, we first prove a new, alternative, description of $\Chi(L)$. This description turns out to be particularly well suited to the fast computation of $\Chi(L)$ when $p$ is large: based on it, we design a new algorithm for computing $\Chi(L)$, whose cost with respect to $p$ is $\softO(p^{0.5})$ operations in the ground field. This is remarkable since, prior to this work, the fastest algorithms for this task, and even for the subtask of deciding nilpotency of the $p$-curvature, had merely slightly subquadratic complexity $\softO(p^{1.79})$.
Common Problems in Delay-Based Congestion Control Algorithms: A Gallery of Solutions
Venue: arXiv cs.NI 2014
Year: 2014

Although delay-based congestion control protocols such as FAST promise to deliver better performance than traditional TCP Reno, they have not yet been widely incorporated to the Internet. Several factors have contributed to their lack of deployment. Probably, the main contributing factor is that they are not able to compete fairly against loss-based congestion control protocols. In fact, the transmission rate in equilibrium of delay-based approaches is always less than their fair share when they share the network with traditional TCP-Reno derivatives, that employ packet losses as their congestion signal. There are also other performance impairments caused by the sensitivity to errors in the measurement of the congestion signal (queuing delay) that reduce the efficiency and the intra-protocol fairness of the algorithms. In this paper we report, analyze and discuss some recent proposals in the literature to improve the dynamic behavior of delay-based congestion control algorithms, and FAST in particular. Coexistence of sources reacting differently to congestion, identifying congestion appearance in the reverse path and the persistent congestion problem are the issues specifically addressed.
Complexity of the robust weighted independent set problems on interval graphs
Venue: arXiv cs.DS 2014
Year: 2014

This paper deals with the max-min and min-max regret versions of the maximum weighted independent set problem on interval graphswith uncertain vertex weights. Both problems have been recently investigated by Nobibon and Leus (2014), who showed that they are NP-hard for two scenarios and strongly NP-hard if the number of scenarios is a part of the input. In this paper, new complexity and approximation results on the problems under consideration are provided, which extend the ones previously obtained. Namely, for the discrete scenario uncertainty representation it is proven that if the number of scenarios $K$ is a part of the input, then the max-min version of the problem is not at all approximable. On the other hand, its min-max regret version is approximable within $K$ and not approximable within $O(\log^{1-ε}K)$ for any $ε>0$ unless the problems in NP have quasi polynomial algorithms. Furthermore, for the interval uncertainty representation it is shown that the min-max regret version is NP-hard and approximable within 2.
Approximability of the robust representatives selection problem
Venue: arXiv cs.DS 2014
Year: 2014

In this paper new complexity and approximation results on the robust versions of the representatives selection problem, under the scenario uncertainty representation, are provided, which extend the results obtained in the recent papers by Dolgui and Kovalev (2012), and Deineko and Woeginger (2013). Namely, it is shown that if the number of scenarios is a part of input, then the min-max (regret) representatives selection problem is not approximable within a ratio of $O(\log^{1-ε}K)$ for any $ε>0$, where $K$ is the number of scenarios, unless the problems in NP have quasi-polynomial time algorithms. An approximation algorithm with an approximation ratio of $O(\log K/ \log \log K)$ for the min-max version of the problem is also provided.
Robust Fuzzy corner detector
Venue: arXiv cs.CV 2014
Year: 2014

Reliable corner detection is an important task in determining the shape of different regions within an image. Real-life image data are always imprecise due to inherent uncertainties that may arise from the imaging process such as defocusing, illumination changes, noise, etc. Therefore, the localization and detection of corners has become a difficult task to accomplish under such imperfect situations. On the other hand, Fuzzy systems are well known for their efficient handling of impreciseness and incompleteness, which make them inherently suitable for modelling corner properties by means of a rule-based fuzzy system. The paper presents a corner detection algorithm which employs such fuzzy reasoning. The robustness of the proposed algorithm is compared to well-known conventional corner detectors and its performance is also tested over a number of benchmark images to illustrate the efficiency of the algorithm under uncertainty.
Multiple pattern matching revisited
Venue: arXiv cs.DS 2014
Year: 2014

We consider the classical exact multiple string matching problem. Our solution is based on $q$-grams combined with pattern superimposition, bit-parallelism and alphabet size reduction. We discuss the pros and cons of the various alternatives of how to achieve best combination. Our method is closely related to previous work by (Salmela et al., 2006). The experimental results show that our method performs well on different alphabet sizes and that they scale to large pattern sets.
On Learning Where To Look
Venue: arXiv cs.CV 2014
Year: 2014

Current automatic vision systems face two major challenges: scalability and extreme variability of appearance. First, the computational time required to process an image typically scales linearly with the number of pixels in the image, therefore limiting the resolution of input images to thumbnail size. Second, variability in appearance and pose of the objects constitute a major hurdle for robust recognition and detection. In this work, we propose a model that makes baby steps towards addressing these challenges. We describe a learning based method that recognizes objects through a series of glimpses. This system performs an amount of computation that scales with the complexity of the input rather than its number of pixels. Moreover, the proposed method is potentially more robust to changes in appearance since its parameters are learned in a data driven manner. Preliminary experiments on a handwritten dataset of digits demonstrate the computational advantages of this approach.
How to Draw Graphs: Seeing and Redrafting Large Networks in Security and Biology
Venue: arXiv cs.HC 2014
Year: 2014

A graph is a mathematical object consisting of a set of vertices and a set of edges connecting vertices. Graphs can be drawn on paper in various ways, but until recently all published methods of drawing graphs have had undesirable properties: (i) for graphs which are not plane embeddable, intersections between the lines representing edges appear at points which are not vertices, creating the appearance of vertices where none exist, (ii) vertex labels can be placed inside vertex symbols, but there is no consistent, logical, and visually clean place to put edge labels, and (iii) representations of large graphs are visually dense and difficult to interpret. This paper describes a new cartographic method of drawing graphs which solves all of these problems, and has other advantages as well. Complements, comparisons and contrasts of graphs are usually better shown cartographically than in node-link form.
On Varieties of Automata Enriched with an Algebraic Structure (Extended Abstract)
Venue: arXiv cs.FL 2014
Year: 2014

Eilenberg correspondence, based on the concept of syntactic monoids, relates varieties of regular languages with pseudovarieties of finite monoids. Various modifications of this correspondence related more general classes of regular languages with classes of more complex algebraic objects. Such generalized varieties also have natural counterparts formed by classes of finite automata equipped with a certain additional algebraic structure. In this survey, we overview several variants of such varieties of enriched automata.
Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
Venue: arXiv cs.FL 2014
Year: 2014

We develop a formal perspective on how regular expression matching works in Java, a popular representative of the category of regex-directed matching engines. In particular, we define an automata model which captures all the aspects needed to study such matching engines in a formal way. Based on this, we propose two types of static analysis, which take a regular expression and tell whether there exists a family of strings which makes Java-style matching run in exponential time.
Non-termination using Regular Languages
Venue: arXiv cs.LO 2014
Year: 2014

We describe a method for proving non-looping non-termination, that is, of term rewriting systems that do not admit looping reductions. As certificates of non-termination, we employ regular (tree) automata.
NLCertify: A Tool for Formal Nonlinear Optimization
Venue: arXiv cs.MS 2014
Year: 2014

NLCertify is a software package for handling formal certification of nonlinear inequalities involving transcendental multivariate functions. The tool exploits sparse semialgebraic optimization techniques with approximation methods for transcendental functions, as well as formal features. Given a box and a transcendental multivariate function as input, NLCertify provides OCaml libraries that produce nonnegativity certificates for the function over the box, which can be ultimately proved correct inside the Coq proof assistant.
Indoor Navigation on Google Maps and Indoor Localization Using RSS Fingerprinting
Venue: arXiv cs.NI 2014
Year: 2014

Contrasting to advances in street/outdoor navigation, wall mounted maps and signs continue to be the primary reference indoor navigation in hospitals, malls, museums, etc. The proliferation of mobile devices and the growing demand for location aware systems that filter information based on currently device location have led to an increase in research and product development in this field. An attempt has been made to provide solution for indoor navigation on Google maps and to provide location of a user in a building using Wi-Fi signal strength on android Smartphone.
Bitcoin Cooperative Proof-of-Stake
Venue: arXiv cs.CY 2014
Year: 2014

A hard-fork reconfiguration of the peer to peer Bitcoin network is described that substitutes tamper-evident logs and proof-of-stake consensus for proof-of-work consensus. The block creation rewards and transaction fees are reallocated to establish and staff a secure financial data network capable of handling the world's transactions with subsecond response time. The new system pays dividends to stake-offering bitcoin holders. In contrast to Satoshi Nakamoto's mesh network consisting of competing peers, this system uses an enterprise class network that is efficient, robust, and scalable, consisting of cooperating peers. The network backbone nodes host trustless nomadic agents. Thousands of distributed full nodes are paid to replicate a singleton blockchain built upon every 10 minutes by a nomadic mint agent whose actions are verified by its peers. This arrangement enables immediate acknowledgment to an issuing node that its transaction has been accepted. Less effort means that subsidized transaction costs will be lower. Network reconfiguration enables the processing of numerous microtransactions. Stake-weighted distributed consensus is achieved when necessary with less than one-half arbitrarily faulty nodes. Important invariants of the Satoshi Social Contract between core developers and users are maintained: The reward schedule, the blockchain format, the fixed number of bitcoins, and the decentralized, trustless protocol are untouched. The system remains a global distributed database, with additions to the database by consent of the majority, based on a set of transparent rules they follow.
Nonlinear POMDPs for Active State Tracking with Sensing Costs
Venue: arXiv cs.SY 2014
Year: 2014

Active state tracking is needed in object classification, target tracking, medical diagnosis and estimation of sparse signals among other various applications. Herein, active state tracking of a discrete-time, finite-state Markov chain is considered. Noisy Gaussian observations are dynamically collected by exerting appropriate control over their information content, while incurring a related sensing cost. The objective is to devise sensing strategies to optimize the trade-off between tracking performance and sensing cost. A recently proposed Kalman-like estimator \cite{ZoisTSP14} is employed for state tracking. The associated mean-squared error and a generic sensing cost metric are then used in a partially observable Markov decision process formulation, and the optimal sensing strategy is derived via a dynamic programming recursion. The resulting recursion proves to be non-linear, challenging control policy design. Properties of the related cost functions are derived and sufficient conditions are provided regarding the structure of the optimal control policy enabling characterization of when passive state tracking is optimal. To overcome the associated computational burden of the optimal sensing strategy, two lower complexity strategies are proposed, which exploit the aforementioned properties. The performance of the proposed strategies is illustrated in a wireless body sensing application, where cost savings as high as $60\%$ are demonstrated for a $4\%$ detection error with respect to a static equal allocation sensing strategy.
Realms: A Structure for Consolidating Knowledge about Mathematical Theories
Venue: arXiv cs.MS 2014
Year: 2014

Since there are different ways of axiomatizing and developing a mathematical theory, knowledge about a such a theory may reside in many places and in many forms within a library of formalized mathematics. We introduce the notion of a realm as a structure for consolidating knowledge about a mathematical theory. A realm contains several axiomatizations of a theory that are separately developed. Views interconnect these developments and establish that the axiomatizations are equivalent in the sense of being mutually interpretable. A realm also contains an external interface that is convenient for users of the library who want to apply the concepts and facts of the theory without delving into the details of how the concepts and facts were developed. We illustrate the utility of realms through a series of examples. We also give an outline of the mechanisms that are needed to create and maintain realms.
Bounds of fast decodability of space time block codes, skew-Hermitian matrices, and Azumaya algebras
Venue: arXiv cs.IT 2014
Year: 2014

We study fast lattice decodability of space-time block codes for $n$ transmit and receive antennas, written very generally as a linear combination $\sum_{i=1}^{2l} s_i A_i$, where the $s_i$ are real information symbols and the $A_i$ are $n\times n$ $\mathbb R$-linearly independent complex valued matrices. We show that the mutual orthogonality condition $A_iA_j^* + A_jA_i^*=0$ for distinct basis matrices is not only sufficient but also necessary for fast decodability. We build on this to show that for full-rate ($l = n^2$) transmission, the decoding complexity can be no better than $|S|^{n^2+1}$, where $|S|$ is the size of the effective real signal constellation. We also show that for full-rate transmission, $g$-group decodability, as defined in [1], is impossible for any $g \ge 2$. We then use the theory of Azumaya algebras to derive bounds on the maximum number of groups into which the basis matrices can be partitioned so that the matrices in different groups are mutually orthogonal---a key measure of fast decodability. We show that in general, this maximum number is of the order of only the $2$-adic value of $n$. In the case where the matrices $A_i$ arise from a division algebra, which is most desirable for diversity, we show that the maximum number of groups is only $4$. As a result, the decoding complexity for this case is no better than $|S|^{\lceil l/2 \rceil}$ for any rate $l$.