OpenRaiser/Intern-Atlas huggingface dataset:
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four
Venue: arXiv cs.CC 2015
Year: 2015

The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size $ω\gg \log{(n)}$ added to an \Erdos-\Renyi graph $G \sim G(n,\frac{1}{2})$, have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size $ω= Ω(\sqrt{n})$. By contrast, information theoretically, one can recover planted cliques so long as $ω\gg \log{(n)}$. In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson (MPW, 2015) and Deshpande and Montanari (DM,2015). Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless $ω\gg \sqrt n poly \log n$, improving upon the bound $ω\gg n^{1/3}$ due to DM. A similar result was obtained independently by Raghavendra and Schramm (2015). 2. For $2 < d = o(\sqrt{\log{(n)}})$, degree $2d$ SoS does not recover the planted clique unless $ω\gg n^{1/(d + 1)} /(2^d poly \log n)$, improving upon the bound due to MPW. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works MPW,DM and Feige and Krauthgamer (2003) by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev (2001). An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by "correcting" the certificate of previous works.
Estimation of Space-Time Varying Parameters Using a Diffusion LMS Algorithm
Venue: arXiv cs.SY 2015
Year: 2015

We study the problem of distributed adaptive estimation over networks where nodes cooperate to estimate physical parameters that can vary over both space and time domains. We use a set of basis functions to characterize the space-varying nature of the parameters and propose a diffusion least mean-squares (LMS) strategy to recover these parameters from successive time measurements. We analyze the stability and convergence of the proposed algorithm, and derive closed-form expressions to predict its learning behavior and steady-state performance in terms of mean-square error. We find that in the estimation of the space-varying parameters using distributed approaches, the covariance matrix of the regression data at each node becomes rank-deficient. Our analysis reveals that the proposed algorithm can overcome this difficulty to a large extent by benefiting from the network stochastic matrices that are used to combine exchanged information between nodes. We provide computer experiments to illustrate and support the theoretical findings.
Optimizing Phylogenetic Supertrees Using Answer Set Programming
Venue: arXiv cs.CE 2015
Year: 2015

The supertree construction problem is about combining several phylogenetic trees with possibly conflicting information into a single tree that has all the leaves of the source trees as its leaves and the relationships between the leaves are as consistent with the source trees as possible. This leads to an optimization problem that is computationally challenging and typically heuristic methods, such as matrix representation with parsimony (MRP), are used. In this paper we consider the use of answer set programming to solve the supertree construction problem in terms of two alternative encodings. The first is based on an existing encoding of trees using substructures known as quartets, while the other novel encoding captures the relationships present in trees through direct projections. We use these encodings to compute a genus-level supertree for the family of cats (Felidae). Furthermore, we compare our results to recent supertrees obtained by the MRP method.
Toward automatic verification of quantum cryptographic protocols
Venue: arXiv cs.CR 2015
Year: 2015

Several quantum process algebras have been proposed and successfully applied in verification of quantum cryptographic protocols. All of the bisimulations proposed so far for quantum processes in these process algebras are state-based, implying that they only compare individual quantum states, but not a combination of them. This paper remedies this problem by introducing a novel notion of distribution-based bisimulation for quantum processes. We further propose an approximate version of this bisimulation that enables us to prove more sophisticated security properties of quantum protocols which cannot be verified using the previous bisimulations. In particular, we prove that the quantum key distribution protocol BB84 is sound and (asymptotically) secure against the intercept-resend attacks by showing that the BB84 protocol, when executed with such an attacker concurrently, is approximately bisimilar to an ideal protocol, whose soundness and security are obviously guaranteed, with at most an exponentially decreasing gap.
Watson-Crick Quantum Finite Automata
Venue: arXiv cs.FL 2015
Year: 2015

1-way quantum finite automata are deterministic and reversible in nature, which greatly reduces its accepting property. In fact the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. In this paper we replace the tape head of 1-way quantum finite automata with DNA double strand and name the model Watson-Crick quantum finite automata. The non-injective complementarity relation of Watson-Crick automata introduces non-determinism in the quantum model. We show that this introduction of non-determinism increases the computational power of 1-way Quantum finite automata significantly. We establish that Watson-Crick quantum finite automata can accept all regular languages and that it also accepts some languages not accepted by any multihead deterministic finite automata. Exploiting the superposition property of quantum finite automata we show that Watson-Crick quantum finite automata accept the language L=ww where w belongs to {a,b}*.
Reversible Watson-Crick Automata
Venue: arXiv cs.FL 2015
Year: 2015

Watson-Crick automata are finite automata working on double strands. Extensive research work has already been done on non-deterministic Watson-Crick automata and on deterministic Watson-Crick automata. In this paper, we introduce a new model of Watson-Crick automata which is reversible in nature named reversible Watson-Crick automata and explore its computational power. We show even though the model is reversible and one way it accepts all regular languages and also analyze the state complexity of the above stated model with respect to non-deterministic block automata and non-deterministic finite automata and establish its superiority. We further explore the relation of the reversible model with twin-shuffle language and recursively enumerable languages.
Tracking A Dynamic Sparse Channel Via Differential Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers the problem of tracking a dynamic sparse channel in a broadband wireless communication system. A probabilistic signal model is firstly proposed to describe the special features of temporal correlations of dynamic sparse channels: path delays change slowly over time, while path gains evolve faster. Based on such temporal correlations, we then propose the differential orthogonal matching pursuit (D-OMP) algorithm to track a dynamic sparse channel in a sequential way by updating the small channel variation over time. Compared with other channel tracking algorithms, simulation results demonstrate that the proposed D-OMP algorithm can track dynamic sparse channels faster with improved accuracy.
Structured Sparsity: Discrete and Convex approaches
Venue: arXiv cs.IT 2015
Year: 2015

Compressive sensing (CS) exploits sparsity to recover sparse or compressible signals from dimensionality reducing, non-adaptive sensing mechanisms. Sparsity is also used to enhance interpretability in machine learning and statistics applications: While the ambient dimension is vast in modern data analysis problems, the relevant information therein typically resides in a much lower dimensional space. However, many solutions proposed nowadays do not leverage the true underlying structure. Recent results in CS extend the simple sparsity idea to more sophisticated {\em structured} sparsity models, which describe the interdependency between the nonzero components of a signal, allowing to increase the interpretability of the results and lead to better recovery performance. In order to better understand the impact of structured sparsity, in this chapter we analyze the connections between the discrete models and their convex relaxations, highlighting their relative advantages. We start with the general group sparse model and then elaborate on two important special cases: the dispersive and the hierarchical models. For each, we present the models in their discrete nature, discuss how to solve the ensuing discrete problems and then describe convex relaxations. We also consider more general structures as defined by set functions and present their convex proxies. Further, we discuss efficient optimization solutions for structured sparsity problems and illustrate structured sparsity in action via three applications.
Linear Inverse Problems with Norm and Sparsity Constraints
Venue: arXiv cs.IT 2015
Year: 2015

We describe two nonconventional algorithms for linear regression, called GAME and CLASH. The salient characteristics of these approaches is that they exploit the convex $\ell_1$-ball and non-convex $\ell_0$-sparsity constraints jointly in sparse recovery. To establish the theoretical approximation guarantees of GAME and CLASH, we cover an interesting range of topics from game theory, convex and combinatorial optimization. We illustrate that these approaches lead to improved theoretical guarantees and empirical performance beyond convex and non-convex solvers alone.
Dual-normal Logic Programs - the Forgotten Class
Venue: arXiv cs.CC 2015
Year: 2015

Disjunctive Answer Set Programming is a powerful declarative programming paradigm with complexity beyond NP. Identifying classes of programs for which the consistency problem is in NP is of interest from the theoretical standpoint and can potentially lead to improvements in the design of answer set programming solvers. One of such classes consists of dual-normal programs, where the number of positive body atoms in proper rules is at most one. Unlike other classes of programs, dual-normal programs have received little attention so far. In this paper we study this class. We relate dual-normal programs to propositional theories and to normal programs by presenting several inter-translations. With the translation from dual-normal to normal programs at hand, we introduce the novel class of body-cycle free programs, which are in many respects dual to head-cycle free programs. We establish the expressive power of dual-normal programs in terms of SE- and UE-models, and compare them to normal programs. We also discuss the complexity of deciding whether dual-normal programs are strongly and uniformly equivalent.
Notes About a More Aware Dependency Parser
Venue: arXiv cs.CL 2015
Year: 2015

In this paper I explain the reasons that led me to research and conceive a novel technology for dependency parsing, mixing together the strengths of data-driven transition-based and constraint-based approaches. In particular I highlight the problem to infer the reliability of the results of a data-driven transition-based parser, which is extremely important for high-level processes that expect to use correct parsing results. I then briefly introduce a number of notes about a new parser model I'm working on, capable to proceed with the analysis in a "more aware" way, with a more "robust" concept of robustness.
Security Issues in Data Warehouse
Venue: arXiv cs.CR 2015
Year: 2015

Data Warehouse provides storage for huge amounts of historical data from heterogeneous operational sources in the form of multidimensional views, thus supplying sensitive and useful information which help decision-makers to improve the organizations business processes. A data warehouse environment must ensure that data collected and stored in one big repository are not vulnerable. A review of security approaches specifically for data warehouse environment and issues concerning each type of security approach have been provided in this paper.
A Review of Network Traffic Analysis and Prediction Techniques
Venue: arXiv cs.NI 2015
Year: 2015

Analysis and prediction of network traffic has applications in wide comprehensive set of areas and has newly attracted significant number of studies. Different kinds of experiments are conducted and summarized to identify various problems in existing computer network applications. Network traffic analysis and prediction is a proactive approach to ensure secure, reliable and qualitative network communication. Various techniques are proposed and experimented for analyzing network traffic including neural network based techniques to data mining techniques. Similarly, various Linear and non-linear models are proposed for network traffic prediction. Several interesting combinations of network analysis and prediction techniques are implemented to attain efficient and effective results. This paper presents a survey on various such network analysis and traffic prediction techniques. The uniqueness and rules of previous studies are investigated. Moreover, various accomplished areas of analysis and prediction of network traffic have been summed.
Revisiting Robustness in Priced Timed Games
Venue: arXiv cs.LO 2015
Year: 2015

Priced timed games are optimal-cost reachability games played between two players---the controller and the environment---by moving a token along the edges of infinite graphs of configurations of priced timed automata. The goal of the controller is to reach a given set of target locations as cheaply as possible, while the goal of the environment is the opposite. Priced timed games are known to be undecidable for timed automata with $3$ or more clocks, while they are known to be decidable for automata with $1$ clock. In an attempt to recover decidability for priced timed games Bouyer, Markey, and Sankur studied robust priced timed games where the environment has the power to slightly perturb delays proposed by the controller. Unfortunately, however, they showed that the natural problem of deciding the existence of optimal limit-strategy---optimal strategy of the controller where the perturbations tend to vanish in the limit---is undecidable with $10$ or more clocks. In this paper we revisit this problem and improve our understanding of the decidability of these games. We show that the limit-strategy problem is already undecidable for a subclass of robust priced timed games with $5$ or more clocks. On a positive side, we show the decidability of the existence of almost optimal strategies for the same subclass of one-clock robust priced timed games by adapting a classical construction by Bouyer at al. for one-clock priced timed games.
A Perspective on Future Research Directions in Information Theory
Venue: arXiv cs.IT 2015
Year: 2015

Information theory is rapidly approaching its 70th birthday. What are promising future directions for research in information theory? Where will information theory be having the most impact in 10-20 years? What new and emerging areas are ripe for the most impact, of the sort that information theory has had on the telecommunications industry over the last 60 years? How should the IEEE Information Theory Society promote high-risk new research directions and broaden the reach of information theory, while continuing to be true to its ideals and insisting on the intellectual rigor that makes its breakthroughs so powerful? These are some of the questions that an ad hoc committee (composed of the present authors) explored over the past two years. We have discussed and debated these questions, and solicited detailed inputs from experts in fields including genomics, biology, economics, and neuroscience. This report is the result of these discussions.
Faster Worst Case Deterministic Dynamic Connectivity
Venue: arXiv cs.DS 2015
Year: 2015

We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time $O\left(\sqrt{\frac{n(\log\log n)^2}{\log n}}\right)$ and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (STOC 1983) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM 1997), which had update time $O(\sqrt{n})$. All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.
Buzz: An Extensible Programming Language for Self-Organizing Heterogeneous Robot Swarms
Venue: arXiv cs.RO 2015
Year: 2015

We present Buzz, a novel programming language for heterogeneous robot swarms. Buzz advocates a compositional approach, offering primitives to define swarm behaviors both from the perspective of the single robot and of the overall swarm. Single-robot primitives include robot-specific instructions and manipulation of neighborhood data. Swarm-based primitives allow for the dynamic management of robot teams, and for sharing information globally across the swarm. Self-organization stems from the completely decentralized mechanisms upon which the Buzz run-time platform is based. The language can be extended to add new primitives (thus supporting heterogeneous robot swarms), and its run-time platform is designed to be laid on top of other frameworks, such as Robot Operating System. We showcase the capabilities of Buzz by providing code examples, and analyze scalability and robustness of the run-time platform through realistic simulated experiments with representative swarm algorithms.
Practical Selection of SVM Supervised Parameters with Different Feature Representations for Vowel Recognition
Venue: arXiv cs.CL 2015
Year: 2015

It is known that the classification performance of Support Vector Machine (SVM) can be conveniently affected by the different parameters of the kernel tricks and the regularization parameter, C. Thus, in this article, we propose a study in order to find the suitable kernel with which SVM may achieve good generalization performance as well as the parameters to use. We need to analyze the behavior of the SVM classifier when these parameters take very small or very large values. The study is conducted for a multi-class vowel recognition using the TIMIT corpus. Furthermore, for the experiments, we used different feature representations such as MFCC and PLP. Finally, a comparative study was done to point out the impact of the choice of the parameters, kernel trick and feature representations on the performance of the SVM classifier
Taming Primary Key Violations to Query Large Inconsistent Data
Venue: arXiv cs.AI 2015
Year: 2015

Consistent query answering over a database that violates primary key constraints is a classical hard problem in database research that has been traditionally dealt with logic programming. However, the applicability of existing logic-based solutions is restricted to data sets of moderate size. This paper presents a novel decomposition and pruning strategy that reduces, in polynomial time, the problem of computing the consistent answer to a conjunctive query over a database subject to primary key constraints to a collection of smaller problems of the same sort that can be solved independently. The new strategy is naturally modeled and implemented using Answer Set Programming (ASP). An experiment run on benchmarks from the database world prove the effectiveness and efficiency of our ASP-based approach also on large data sets. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.
Robots and humans as co-workers?
Venue: arXiv cs.HC 2015
Year: 2015

The design of work organisation systems with automated equipment is facing new challenges and the emergence of new concepts. The social aspects that are related with new concepts on the complex work environments (CWE) are becoming more relevant for that design. The work with autonomous systems implies options in the design of workplaces. Especially that happens in such complex environments. The concepts of "agents", "co-working" or "human-centred technical systems" reveal new dimensions related to human-computer interaction (HCI). With an increase in the number and complexity of those human-technology interfaces, the capacities of human intervention can become limited, originating further problems. The case of robotics is used to exemplify the issues related with automation in working environments and the emergence of new HCI approaches that would include social implications. We conclude that studies on technology assessment of industrial robotics and autonomous agents on manufacturing environment should also focus on the human involvement strategies in organisations. A needed participatory strategy implies a new approach to workplaces design. This means that the research focus must be on the relation between technology and social dimensions not as separate entities, but integrated in the design of an interaction system.
Optimal Selfish Mining Strategies in Bitcoin
Venue: arXiv cs.CR 2015
Year: 2015

Bitcoin is a decentralized crypto-currency, and an accompanying protocol, created in 2008. Bitcoin nodes continuously generate and propagate blocks---collections of newly approved transactions that are added to Bitcoin's ledger. Block creation requires nodes to invest computational resources, but also carries a reward in the form of bitcoins that are paid to the creator. While the protocol requires nodes to quickly distribute newly created blocks, strong nodes can in fact gain higher payoffs by withholding blocks they create and selectively postponing their publication. The existence of such selfish mining attacks was first reported by Eyal and Sirer, who have demonstrated a specific deviation from the standard protocol (a strategy that we name SM1). In this paper we extend the underlying model for selfish mining attacks, and provide an algorithm to find $ε$-optimal policies for attackers within the model, as well as tight upper bounds on the revenue of optimal policies. As a consequence, we are able to provide lower bounds on the computational power an attacker needs in order to benefit from selfish mining. We find that the profit threshold -- the minimal fraction of resources required for a profitable attack -- is strictly lower than the one induced by the SM1 scheme. Indeed, the policies given by our algorithm dominate SM1, by better regulating attack-withdrawals. Using our algorithm, we show that Eyal and Sirer's suggested countermeasure to selfish mining is slightly less effective than previously conjectured. Next, we gain insight into selfish mining in the presence of communication delays, and show that, under a model that accounts for delays, the profit threshold vanishes, and even small attackers have incentive to occasionally deviate from the protocol. We conclude with observations regarding the combined power of selfish mining and double spending attacks.