Abstract:This is a special issue with special interest in computability and computational complexity with extensions to information and network analysis. It consists of seven invited submissions each of which is carefully reviewed. The paper entitled: The future of computer science by John E. Hopcroft, Sucheta Soundarajan, and Liaoruo Wang, surveys some important topics and paradigm shift in computer science with the new focus on large-scale data and network analysis. The paper entitled: Holographic reduction: A domain changed application and its partial converse theorems by Mingji Xia arises the new problem of the converse of Valiant's holographic reductions, and partially answers this question, which makes a significant contribution to the theory of holographic computation. The paper entitled: On strings with trivial Kolmogorov complexity by George Barmpalias studies the degree theoretic complexity of sets of strings with low algorithmic complexity, building a few fundamental results in the area of algorithmic randomness. The paper entitled: Color-Coding and its applications: A survey by Jianxin Wang, Qilong Feng, Jianer Chen, describes a comprehensive survey on this important topic of parameterized computation. The paper entitled: Rent-or-Buy network design problem and the Sample-Augment algorithm: A survey by Peng Zhang, gives a survey on approximation algorithms of the recently active topic of the rent or buy network design. The paper entitled: Kalimulin pairs of ** w-enumeration degrees by Ivan N. Soskov and Mariya I. Soskov studies the new phenomena of omega-enumeration degrees which is a natural extension of the classical enumeration degrees. The paper entitled: A toolkit for generating sentences from context-free grammars by Zhiwu Xu, Lixiao Zheng, and Haiming Chen, presents a toolkit for parsing context-free grammars and generating valid sentences. I would like to thank all authors for their contribution to this excellent issue, which reflects both our traditional research on computability and computational complexity and the extensions of the theory to information and networks. I am grateful to Prof. Ruqian Lu for inviting me to organize this special issue, and thank both Professor Ruqian Lu and the members of the Editorial Board of the International Journal of Software and Informatics for cooperation throughout the preparation of this special issue.

Abstract:Computer science is undergoing a fundamental change and is reshaping our understanding of the world. An important aspect of this change is the theory and applications dealing with the gathering and analyzing of large real-world data sets. In this paper, we introduce four research projects in which processing and interpreting large data sets is a central focus. Innovative ways of analyzing such data sets allow us to extract useful information that we would never have obtained from small or synthetic data sets, thus providing us with new insights into the real world.

Abstract:Holographic reductions between some Holant problems and some #CSP(Hd) problems are built, where Hd is some complex value binary function. By the complexity of these Holant problems, for each integer d >= 2, #CSP(Hd) is in P when each variable appears at most d times, while it is #P-hard when each variables appears at most d + 1 times. #CSP(Hd) counts weighted summation of graph homomorphisms from input graph G to graph Hd, and the maximum occurrence of variables is the maximum degree of G. We conjecture that the converse of holographic reduction holds for most of #Bi-restriction Constraint Satisfaction Problems, which can be regarded as a generalization of a known result about counting graph homomorphisms. It is shown that the converse of holographic reduction holds for some classes of problems.

Abstract:The Kolmogorov complexity of a string is the length of the shortest program that generates it. A binary string is said to have trivial Kolmogorov complexity if its complexity is at most the complexity of its length. Intuitively, such strings carry no more information than the information that is inevitably coded into their length (which is the same as the information coded into a sequence of 0s of the same length). We study the set of these trivial sequences from a computational perspective, and with respect to plain and prefix-free Kolmogorov complexity. This work parallels the well known study of the set of nonrandom strings (which was initiated by Kolmogorov and developed by Kummer, Muchnik, Stephan, Allender and others) and points to several directions for further research.

Abstract:Color-Coding is an important algorithmic technique in solving many NP-hard problems. In this paper, we give a survey on Color-Coding technique and its applications. We first give brief introduction on three Color-Coding methods: random Color-Coding, Color-Coding based on perfect hash function, and Color-Coding for n <= 2k. Then, applications of Color-Coding technique in various fields are presented, such as Bioinformatics, Networks, etc. Finally, we give future research topics of Color-Coding technique.

Abstract:The Rent-or-Buy Network Design problem is a fundamental connectivity-related network design problem. The problem captures the "economies of scale" property, which says that the per-unit cost of installing capacity on edges of the network decreases as more capacity is installed. The Sample-Augment algorithm is a simple but powerful randomized approximation algorithm that effectively deals with the Rent-or-Buy and related problems. In this paper we systematically survey the Rent-or-Buy problem and the Sample-Augment algorithm, as well as its two analysis techniques, i.e., the cost-sharing method and the core-detouring scheme.

Abstract:We study the notion of K-pairs in the local structure of the w-enumeration degrees. We introduce the notion of super almost zero sequences and investigate their structural properties.

Abstract:Producing sentences from a grammar, according to various criteria, is required in many applications. It is also a basic building block for grammar engineering. This paper presents a toolkit for context-free grammars, which mainly consists of several algorithms for sentence generation or enumeration and for coverage analysis for context-free grammars. The toolkit deals with general context-free grammars. Besides providing implementations of algorithms, the toolkit also provides a simple graphical user interface, through which the user can use the toolkit directly. The toolkit is implemented in Java and is available at http://lcs.ios.ac.cn/~zhiwu/toolkit.php. In the paper, the overview of the toolkit and the major algorithms implemented in the toolkit are presented, and experimental results and preliminary applications of the toolkit are also contained.