<Emphasis Type="Italic">i</Emphasis>SIM: An integrated design method for commercializing service innovation

Service innovation is focused on customer value creation. At its core, customer centric service innovation is technology-enabled, human-centered, and process-oriented. To profit from such innovation, firms need an integrated cross-disciplinary, holistic method to design and commercialize service innovation. From diverse but interrelated strands of theories from service science, strategic management, organization science and information systems literatures, this article develops a new integrated design method, known as iSIM (integrated Service Innovation Method), for simultaneous service innovation and business model design for sustained customer value co-creation with the firm. Following design science research method, the article theoretically defines and integrates iSIM’s seven constitutive design process-elements: service strategy, customer type / value proposition, service concept, service system, customer experience, service architecture and monetization into a coherent and end-to-end aligned integrated design method. It explains how iSIM would be holistically and iteratively practiced by practitioners, and conceptually exemplifies its utility via telco and Amazon case studies using secondary data. Perspectives on iSIM from selected practitioners are discussed which confirm iSIM’s potential utility for their business. Managerial implications of implementing the iSIM and potential areas for further research are also discussed.     

Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments

We present barriers to provable security of two important cryptographic primitives, perfect non-interactive zero knowledge (NIZK) and non-interactive non-alleable commitments:

1. ○
   Black-box reductions cannot be used to demonstrate adaptive soundness (i.e., that soundness holds even if the statement to be proven is chosen as a function of the common reference string) of any statistical NIZK for NP based on any “standard” intractability assumptions.
    
2. ○
   Black-box reductions cannot be used to demonstrate non-malleability of non-interactive, or even 2-message, commitment schemes based on any “standard” intractability assumptions.
    

We emphasize that the above separations apply even if the construction of the considered primitives makes a non-black-box use of the underlying assumption.

As an independent contribution, we suggest a taxonomy of game-based intractability assumptions.     

<Emphasis Type="Italic">α</Emphasis>-Systems of differential inclusions and their unification

This paper introduces α-systems of differential inclusions on a bounded time interval [t₀, ?] and defines α-weakly invariant sets in [t₀, ?] × ?_n, where ?_n is a phase space of the differential inclusions. We study the problems connected with bringing the motions (trajectories) of the differential inclusions from an α-system to a given compact set M ? ?_n at the moment ? (the approach problems). The issues of extracting the solvability set W ? [t₀, ?] × ?ⁿ in the problem of bringing the motions of an α-system to M and the issues of calculating the maximal α-weakly invariant set W^c ? [t₀, ?] × ?ⁿ are also discussed. The notion of the quasi-Hamiltonian of an α-system (α-Hamiltonian) is proposed, which seems important for the problems of bringing the motions of the α-system to M.     

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things:

1. (1)
   We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O ^*(f(k)).
    
2. (2)
   The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
    

     

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings

Consider a random graph model where each possible edge e is present independently with some probability p _e . Given these probabilities, we want to build a large/heavy matching in the randomly generated graph. However, the only way we can find out whether an edge is present or not is to query it, and if the edge is indeed present in the graph, we are forced to add it to our matching. Further, each vertex i is allowed to be queried at most t _i times. How should we adaptively query the edges to maximize the expected weight of the matching? We consider several matching problems in this general framework (some of which arise in kidney exchanges and online dating, and others arise in modeling online advertisements); we give LP-rounding based constant-factor approximation algorithms for these problems. Our main results are the following:

• We give a 4 approximation for weighted stochastic matching on general graphs, and a 3 approximation on bipartite graphs. This answers an open question from Chen et al. (ICALP’09, LNCS, vol. 5555, pp. 266–278, [2009]).
• We introduce a generalization of the stochastic online matching problem (Feldman et al. in FOCS’09, pp. 117–126, [2009]) that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.

     

Quartic B-spline collocation method for fifth order boundary value problems

Given two sorted arrays \({A=(a_1,a_2,\ldots ,a_{n_1})}\) and \({B=(b_1,b_2,\ldots ,b_{n_2})}\), where their elements are drawn from a linear range in n and n = Max(n ₁, n ₂). The merging of two sorted arrays is one of the fundamental problems in computer science. The main contribution of this work is to give a new merging algorithm on a EREW PRAM. The algorithm is cost optimal, deterministic and simple. The algorithm uses \({\frac{n}{\log{n}}}\) processors and O(n) storage. We also give the conditions that make the algorithm run in a constant time on a EREW PRAM.     

A parallel pattern for iterative stencil + reduce

We advocate the Loop-of-stencil-reduce pattern as a means of simplifying the implementation of data-parallel programs on heterogeneous multi-core platforms. Loop-of-stencil-reduce is general enough to subsume map, reduce, map-reduce, stencil, stencil-reduce, and, crucially, their usage in a loop in both data-parallel and streaming applications, or a combination of both. The pattern makes it possible to deploy a single stencil computation kernel on different GPUs. We discuss the implementation of Loop-of-stencil-reduce in FastFlow, a framework for the implementation of applications based on the parallel patterns. Experiments are presented to illustrate the use of Loop-of-stencil-reduce in developing data-parallel kernels running on heterogeneous systems.     

A complete coalition logic of temporal knowledge for multi-agent systems

Coalition logic (CL) is one of the most influential logical formalisms for strategic abilities of multi-agent systems. CL can specify what a group of agents can achieve through choices of their actions, denoted by [C]? to state that a group of agents C can have a strategy to bring about ? by collective actions, no matter what the other agents do. However, CL lacks the temporal dimension and thus can not capture the dynamic aspects of a system. Therefore, CL can not formalize the evolvement of rational mental attitudes of the agents such as knowledge, which has been shown to be very useful in specifications and verifications of distributed systems, and has received substantial amount of studies. In this paper, we introduce coalition logic of temporal knowledge (CLTK), by incorporating a temporal logic of knowledge (Halpern and Vardi’s logic of CKL _n ) into CL to equip CL with the power to formalize how agents’ knowledge (individual or group knowledge) evolves over the time by coalitional forces and the temporal properties of strategic abilities as well. Furthermore, we provide an axiomatic system for CLTK and prove that it is sound and complete, along with the complexity of the satisfiability problem which is shown to be EXPTIME-complete.     

Tackling heterogeneous concept drift with the Self-Adjusting Memory (SAM)

Instance matching is the problem of determining whether two instances describe the same real-world entity or not. Instance matching plays a key role in data integration and data cleansing, especially for building a knowledge base. For example, we can regard each article in encyclopedias as an instance, and a group of articles which refers to the same real-world object as an entity. Therefore, articles about Washington should be distinguished and grouped into different entities such as Washington, D.C (the capital of the USA), George Washington (first president of the USA), Washington (a state of the USA), Washington (a village in West Sussex, England), Washington F.C. (a football club based in Washington, Tyne and Wear, England), Washington, D.C. (a novel). In this paper, we proposed a novel instance matching approach Active Instance Matching with Pairwise Constraints, which can bring the human into the loop of instance matching. The proposed approach can generate candidate pairs in advance to reduce the computational complexity, and then iteratively select the most informative pairs according to the uncertainty, influence, connectivity and diversity of pairs. We evaluated our approach one two publicly available datasets AMINER and WIDE-NUS and then applied our approach to the two large-scale real-world datasets, Baidu Baike and Hudong Baike, to build a Chinese knowledge base. The experiments and practice illustrate the effectiveness of our approach.     

Automatic hair extraction from 2D images

Automatic hair extraction from a given 2D image has been a challenging problem for a long time, especially when complex backgrounds and a wide variety of hairstyles are involved. This paper has made its contribution in the following three aspects. First, it proposes a novel framework that successfully combines the techniques of face detection, outlier-aware initial stroke placement and matting to extract the desired hair region from an input image. Second, it introduces an alpha space to facilitate the choice of matting parameters. Third, it defines a new comparison metric that is well suited for the alpha matte comparison. Our results show that, compared with the manually drawn trimaps for hair extraction, the proposed automatic algorithm can achieve about 86.2 % extraction accuracy.     

Knowledge State Algorithms

We introduce the novel concept of knowledge states. The knowledge state approach can be used to construct competitive randomized online algorithms and study the trade-off between competitiveness and memory. Many well-known algorithms can be viewed as knowledge state algorithms. A knowledge state consists of a distribution of states for the algorithm, together with a work function which approximates the conditional obligations of the adversary. When a knowledge state algorithm receives a request, it then calculates one or more “subsequent” knowledge states, together with a probability of transition to each. The algorithm uses randomization to select one of those subsequents to be the new knowledge state. We apply this method to randomized k-paging. The optimal minimum competitiveness of any randomized online algorithm for the k-paging problem is the kth harmonic number, \(H_{k}=\sum^{k}_{i=1}\frac{1}{i}\). Existing algorithms which achieve that optimal competitiveness must keep bookmarks, i.e., memory of the names of pages not in the cache. An H _k -competitive randomized algorithm for that problem which uses O(k) bookmarks is presented, settling an open question by Borodin and El-Yaniv. In the special cases where k=2 and k=3, solutions are given using only one and two bookmarks, respectively.     

Guaranteed strategies for escaping encirclement

This paper considers a conflict situation on the plane as follows. A fast evader E has to break out the encirclement of slow pursuers P _{j1,...,j n} = {P _j1,..., P _jn }, n ≥ 3, with a miss distance not smaller than r ≥ 0. First, we estimate the minimum guaranteed miss distance from E to a pursuer P _a , a ∈ {j ₁,..., j _n }, when the former moves along a given straight line. Then the obtained results are used to calculate the guaranteed estimates to a group of two pursuers P _b,c = {P _b , P _c }, b, c ∈ {j ₁,..., j _n }, b ≠ c, when E maneuvers by crossing the rectilinear segment P _b P _c , and the state passes to the domain of the game space where E applies a strategy under which the miss distance to any of the pursuers is not decreased. In addition, we describe an approach to the games with a group of pursuers P _{j1,... jn} , n ≥ 3, in which E seeks to break out the encirclement by passing between two pursuers P _b and P _c , entering the domain of the game space where E can increase the miss distance to all pursuers by straight motion. By comparing the guaranteed miss distances with r for all alternatives b, c ∈ {j ₁,..., j _n }, b ≠ c, and a ? {b, c}, it is possible to choose the best alternative and also to extract the histories of the game in which the designed evasion strategies guarantee a safe break out from the encirclement.     

Organization of self-diagnosis of the discrete multicomponent systems a structure like bipartite quasicomplete graphs

Organization of an efficient self-diagnosis of the multicomponent computer and communication systems of diverse structures always attracted attention of the researchers and engineers. A method to solve these problems is presented in the paper by way of the example of a system whose structure is modeled by a uniform ordinary bipartite graph of diameter d = 3, any degree s > 1, and any number n of vertices, where n = s(s ? 1) + 1. The method requires checking of (s ? 1)³ graph loops of length eight each, which is smaller than the number s ²(s ? 1) + s of checks of single graph edges.     

A Priori knowledge based secure payload estimation

Many contemporary steganographic schemes aim to embed fixed-length secret message in the cover while minimizing the stego distortion. However, in some cases, the secret message sender requires to embed a variable-length secret payload within his expected stego security. This kind of problem is named as secure payload estimation (SPE). In this paper, we propose a practical SPE approach for individual cover. The stego security metric we adopt here is the detection error rate of steganalyzer (P _E ). Our method is based on a priori knowledge functions, which are two kinds of functions to be determined before the estimation. The first function is the relation function of detection error rate and stego distortion (P _E ? D function). The second function reflects the relationship between stego distortion and payload rate (D ? α) of the chosen cover. The P _E ? D is the general knowledge, which is calculated from image library. On the other hand, D ? α is for specific cover, which is needed to be determined on site. The estimating procedure is as follows: firstly, the sender solves the distortion D under his expected P _E via P _E ? D, and then calculates the corresponding secure payload α via D ? α of the cover. For on-site operations, the most time-consuming part is calculating D ? α function for cover image, which costs 1 time of STC coding. Besides this, the rest on-site operations are solving single-variable formulas, which can be easily tackled. Our approach is an efficient and practical solution for SPE problem.     

<Emphasis Type="Italic">I</Emphasis><Subscript>DDT</Subscript>: Fundamentals and test generation

It is the time to explore the fundamentals ofI _DDT testing when extensive work has been done forI _DDT testing since it was proposed. This paper precisely defines the concept of average transient current (I _DDT) of CMOS digital ICs, and experimentally analyzes the feasibility ofI _DDT test generation at gate level. Based on the SPICE simulation results, the paper suggests a formula to calculateI _DDT by means of counting only logical up-transitions, which enablesI _DDT test generation at logic level. The Bayesian optimization algorithm is utilized forI _DDT test generation. Experimental results show that about 25% stuck-open faults are withI _DDT test generation. 2.5, and likely to beI _DDT testable. It is also found that mostI _DDT testable faults are located near the primary inputs of a circuit under test.I _DDT test generation does not require fault sensitization procedure compared with stuck-at fault test generation. Furthermore, some redundant stuck-at faults can be detected by usingI _DDT testing.     

Design of optimal and robust control with <Emphasis Type="Italic">H</Emphasis> <Subscript>∞</Subscript>/<Emphasis Type="Italic">γ</Emphasis> <Subscript>0</Subscript> performance criterion

For a double-input single-output system, this paper defines a disturbance attenuation level (called H_∞/γ₀ norm) as the maximum-value L₂ norm of the output under an unknown disturbance with a bounded L₂ norm supplied to the first input and an impulsive disturbance in the form of the product of an unknown vector and the delta function supplied the second input, where the squared L₂ norm of the former disturbance plus the quadratic form of the impulsive disturbance vector does not exceed 1. Weight matrix choice in the H_∞/γ₀ norm yields a trade-off between the attenuation level of the L₂ disturbance and the attenuation level of the impulsive disturbance in corresponding channels. For the uncertain systems with dynamic or parametric uncertainty in the feedback loop, a robust H_∞/γ₀ norm is introduced that includes the robust H_∞ and γ₀ norms as special cases. All these characteristics or their upper bounds in the uncertain system are expressed via solutions of linear matrix inequalities. This gives a uniform approach for designing optimal and robust control laws with the H_∞/γ₀, H_∞ and γ₀ performance criteria.     

Incompressible Functions,Relative-Error Extractors,and the Power of Nondeterministic Reductions

A circuit C compresses a function \({f : \{0,1\}^n\rightarrow \{0,1\}^m}\) if given an input \({x\in \{0,1\}^n}\), the circuit C can shrink x to a shorter ?-bit string x′ such that later, a computationally unbounded solver D will be able to compute f(x) based on x′. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size \({s=n^c}\). Motivated by cryptographic applications, we focus on average-case \({(\ell,\epsilon)}\) incompressibility, which guarantees that on a random input \({x\in \{0,1\}^n}\), for every size s circuit \({C:\{0,1\}^n\rightarrow \{0,1\}^{\ell}}\) and any unbounded solver D, the success probability \({\Pr_x[D(C(x))=f(x)]}\) is upper-bounded by \({2^{-m}+\epsilon}\). While this notion of incompressibility appeared in several works (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work, we present the following results:

1. (1)
   Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) which is incompressible by size n ^c circuits with communication \({\ell=(1-o(1)) \cdot n}\) and error \({\epsilon=n^{-c}}\). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14).
    
2. (2)
   We show that it is possible to achieve negligible error parameter \({\epsilon=n^{-\omega(1)}}\) for nonboolean functions. Specifically, assuming that E is hard for exponential size \({\Sigma_3}\)-circuits, we construct a nonboolean function \({f:\{0,1\}^n\rightarrow \{0,1\}^m}\) which is incompressible by size n ^c circuits with \({\ell=\Omega(n)}\) and extremely small \({\epsilon=n^{-c} \cdot 2^{-m}}\). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest.
    
3. (3)
   We show that the task of constructing an incompressible boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) with negligible error parameter \({\epsilon}\) cannot be achieved by “existing proof techniques”. Namely, nondeterministic reductions (or even \({\Sigma_i}\) reductions) cannot get \({\epsilon=n^{-\omega(1)}}\) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospect, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (STOC 08).
    

     

A closed asynchronous dynamic model of cellular learning automata and its application to peer-to-peer networks

Cellular Learning Automata (CLAs) are hybrid models obtained from combination of Cellular Automata (CAs) and Learning Automata (LAs). These models can be either open or closed. In closed CLAs, the states of neighboring cells of each cell called local environment affect on the action selection process of the LA of that cell whereas in open CLAs, each cell, in addition to its local environment has an exclusive environment which is observed by the cell only and the global environment which can be observed by all the cells in CLA. In dynamic models of CLAs, one of their aspects such as structure, local rule or neighborhood radius may change during the evolution of the CLA. CLAs can also be classified as synchronous CLAs or asynchronous CLAs. In a synchronous CLA, all LAs in different cells are activated synchronously whereas in an asynchronous CLA, the LAs in different cells are activated asynchronously. In this paper, a new closed asynchronous dynamic model of CLA whose structure and the number of LAs in each cell may vary with time has been introduced. To show the potential of the proposed model, a landmark clustering algorithm for solving topology mismatch problem in unstructured peer-to-peer networks has been proposed. To evaluate the proposed algorithm, computer simulations have been conducted and then the results are compared with the results obtained for two existing algorithms for solving topology mismatch problem. It has been shown that the proposed algorithm is superior to the existing algorithms with respect to communication delay and average round-trip time between peers within clusters.     

Finding Coefficients of the Full Array of Motion-Independent <Emphasis Type="Italic">N</Emphasis>-Body Potentials of Metric Gravity from Gravity’s Exterior and Interior Effacement Algebra

In the author’s previous publications, a recursive linear algebraic method was introduced for obtaining (without gravitational radiation) the full potential expansions for the gravitational metric field components and the Lagrangian for a general N-body system. Two apparent properties of gravity— Exterior Effacement and Interior Effacement—were defined and fully enforced to obtain the recursive algebra, especially for the motion-independent potential expansions of the general N-body situation. The linear algebraic equations of this method determine the potential coefficients at any order n of the expansions in terms of the lower-order coefficients. Then, enforcing Exterior and Interior Effacement on a selecedt few potential series of the full motion-independent potential expansions, the complete exterior metric field for a single, spherically-symmetric mass source was obtained, producing the Schwarzschild metric field of general relativity. In this fourth paper of this series, the complete spatial metric’s motion-independent potentials for N bodies are obtained using enforcement of Interior Effacement and knowledge of the Schwarzschild potentials. From the full spatial metric, the complete set of temporal metric potentials and Lagrangian potentials in the motion-independent case can then be found by transfer equations among the coefficients κ(n, α) → λ(n, ε) → ξ(n, α) with κ(n, α), λ(n, ε), ξ(n, α) being the numerical coefficients in the spatial metric, the Lagrangian, and the temporal metric potential expansions, respectively.     

Dependence of Critical Parameters of 2D Ising Model on Lattice Size

For the 2D Ising model, we analyzed dependences of thermodynamic characteristics on number of spins by means of computer simulations. We compared experimental data obtained using the Fisher-Kasteleyn algorithm on a square lattice with N = l × l spins and the asymptotic Onsager solution (N → ∞). We derived empirical expressions for critical parameters as functions of N and generalized the Onsager solution on the case of a finite-size lattice. Our analytical expressions for the free energy and its derivatives (the internal energy, the energy dispersion and the heat capacity) describe accurately the results of computer simulations. We showed that when N increased the heat capacity in the critical point increased as lnN. We specified restrictions on the accuracy of the critical temperature due to finite size of our system. Also in the finite-dimensional case, we obtained expressions describing temperature dependences of the magnetization and the correlation length. They are in a good qualitative agreement with the results of computer simulations by means of the dynamic Metropolis Monte Carlo method.