Abstract A private data query system (PDQS) enables data consumers to access privately owned data while compensating data owners for their privacy loss. The two main tasks of a PDQS include procurement, i.e., collecting data from multiple data owners with an appropriate pricing scheme, and querying, i.e., aggregating the collected dataset for a query output while preserving data owners’ privacy. Existing PDQS are designed for unconditional queries over single-attribute data. In this paper, we design PrivCQ, a new PDQS that supports conditional queries over multi-dimensional data. To accommodate heterogeneous attribute-level privacy preferences, we introduce a new privacy concept, multi-dimensional personalised local differential privacy (m-PLDP), which specifies privacy requirements across multiple sensitive attributes for each data owner. For procurement, we propose total purchased privacy maximisation (TPPM), a principle linking query accuracy to m-PLDP. For query, we propose two techniques, attribute fusion and aggregation conditioning, to process conditional queries over multi-dimensional sensitive data. We design three query mechanisms that achieve m-PLDP under different paradigms and empirically validate them on three real-world datasets.

With the frequent occurrences of natural disasters and the rising risk of malicious attacks, improving network survivability and guaranteeing connectivity in the presence of large-scale failures have emerged as a critical research challenge. Traditional studies on improving edge/node connectivity assume that failures occur at random and fail to capture the locality of large-scale failures. Although studies on region-based connectivity can address this limitation, they fail to consider how local failures affect the communication between certain key source-destination (SD) pairs. In this paper, we first extend the definition of region-based connectivity to include SD pairs. Given ℓ failure regions andkSD pairs, we study the problem of shielding edges with minimum cost to improve region-based connectivity between thekSD pairs. Second, we systematically analyze the computational complexity of the problem under different settings of ℓ,kand topologies of failure regions. Third, we design an ILP-based formulation to solve the general problem and propose two polynomial-time algorithms for two special cases based on the matroid technique and the biconnected component decomposition, respectively. Experimental results show that our algorithms are much faster than previously known algorithms.

Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principle of allocation rules for strategyproof network auctions is still missing. We show that, due to the absence of such a principle, even extensions to multi-unit network auctions with single-unit demand present unexpected difficulties, and all pioneering researches fail to be strategyproof. For the first time in this field, we identify two categories of monotone allocation rules on networks: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON). They encompass all existing allocation rules of network auctions as specific instances. For any given ID-MON or IP-MON allocation rule, we characterize the existence and sufficient conditions for the strategyproof payment rules, and show that among all such payment rules, the revenue-maximizing one exists and is computationally feasible. With these results, the obstacle of combinatorial network auction with single-minded bidders is now resolved.

We study automatic presentations of the structures (ℕ; S), (ℕ; E_S), (ℕ; ≤), and their expansions by a unary predicate U. Here S is the successor function, E_S is the undirected version of S, and ≤ is the natural order. We call these structures word structures. Our goal is three-fold. First, we study the isomorphism problem for automatic word structures by focusing on the following three problems. The first problem asks to design an algorithm that, given an automatic structure A, decides if A is isomorphic to (ℕ; S). The second asks to design an algorithm that, given two automatic presentations of (ℕ; S, U₁) and (ℕ; S, U₂), where U₁ and U₂ are unary predicates, decides if these structures are isomorphic. The third problem investigates if there is an algorithm that, given two automatic presentations of (ℕ; ≤, U₁) and (ℕ; ≤, U₂), decides whether U₁ ∩ U₂ ≠ ∅. We show that these problems are undecidable. Next, we study intrinsic regularity of the function S in the structure Path_ω = (ℕ; E_S). We build an automatic presentation of Path_ω in which S is not regular. This implies that S is not intrinsically regular in Path_ω. For U ⊆ ℕ, let d_U be the function that computes the distances between the consecutive elements of U. We build automatic presentations of (ℕ; ≤, U) where d_U can realise logarithmic, radical, intermediate, and exponential functions.

Regular games form a well-established class of games for analysis and synthesis of reactive systems. They include colored Muller games, McNaughton games, Muller games, Rabin games, and Streett games. These games are played on directed graphs G where Player 0 and Player 1 play by generating an infinite path ρ through the graph. The winner is determined by specifications put on the set X of vertices in ρ that occur infinitely often. These games are determined, enabling the partitioning of G into two sets Win₀ and Win₁ of winning positions for Player 0 and Player 1, respectively. Numerous algorithms exist that decide instances of regular games, e.g., Muller games, by computing Win₀ and Win₁. In this paper we aim to find general principles for designing uniform algorithms that decide all regular games. For this we utilize various recursive and dynamic programming algorithms that leverage standard notions such as subgames and traps. Importantly, we show that our techniques improve or match the performances of existing algorithms for many instances of regular games.

Recently there has been a large amount of research designing mechanisms for auction scenarios where the bidders are connected in a social network. Different from the existing studies in this field that focus on specific auction scenarios e.g. single-unit auction and multi-unit auction, this paper considers the following question: is it possible to design a scheme that, given a classical auction scenario and a mechanism M˜ suited for it, produces a mechanism in the network setting that preserves the key properties of M˜? To answer this question, we design meta-mechanisms that provide a uniform way of transforming mechanisms from classical models to mechanisms over networks and prove that the desirable properties are preserved by our meta-mechanisms. Our meta-mechanisms provide solutions to combinatorial auction scenarios in the network setting: (1) combinatorial auction with single-minded buyers and (2) combinatorial auction with general monotone valuation. To the best of our knowledge, this is the first work that designs combinatorial auctions over a social network.

The issue of fairness in AI arises from discriminatory practices in applications like job recommendations and risk assessments, emphasising the need for algorithms that do not discriminate based on group characteristics. This concern is also pertinent to auctions, commonly used for resource allocation, which necessitate fairness considerations. Our study examines auctions with groups distinguished by specific attributes, seeking to (1) define a fairness notion that ensures equitable treatment for all, (2) identify mechanisms that adhere to this fairness while preserving incentive compatibility, and (3) explore the balance between fairness and seller’s revenue. We introduce two fairness notions—group fairness and individual fairness—and propose two corresponding auction mechanisms: the Group Probability Mechanism, which meets group fairness and incentive criteria, and the Group Score Mechanism, which also encompasses individual fairness. Through experiments, we validate these mechanisms’ effectiveness in promoting fairness and examine their implications for seller revenue.

We aim to describe the isomorphism types of infinite structures in the language of first-order logic. This pursuit holds importance in logic in computer science, encompassing model theory, descriptional complexity, and the foundations of computability. We introduce the notion of quasi-axiomatizability aimed at describing the isomorphism types of structures. Our focus centers on two classes of algorithmically presented structures. The first is the class of structures for which the positive atomic diagrams are computably enumerable. We call these structures positive structures. The second is the class of structures for which the negative atomic diagrams are computably enumerable. We call these structures negative structures. We study quasi-axiomatizability of structures from these classes by ∃, ∀, ∃∀, and ∀∃-sentences in expansions of languages. Our work is a contribution to the interplay between expressive power of first-order logic, computability, and model theory.

The sealed-bid auction enables bidders to secretly send their bids to the auctioneer, which compares all bids and publishes the winning one on the bid-opening day. This type of auction is friendly for protecting the bid privacy, and sufficiently fair for all bidders if the auctioneer acts faithfully. Unfortunately, the auctioneer may not always be trustworthy. The auctioneer has the ability to deliberately leak any bid information to a part of bidders for raising the final winning price based on the investigation. Meanwhile, the auctioneer can appoint any bidder as the winner, as long as the bidder accepts a higher winning price than the current highest bid. Since bidders cannot obtain any bid information from others, to the best of our knowledge, it is difficult to prevent bid leakage from the auctioneer, and support bidders to verify the bid comparison results without disclosing the winning bid, simultaneously. To alleviate these problems, we first construct a homomorphic encryption(HE)-based bid comparison circuit. All bidders can directly compute a cipher of the winning bid by using this circuit; hence, the winning bid does not need to be exposed to all bidders. Then, we propose a blockchain-based sealed-bid scheme (BSS) by integrating the circuit with commitment and zero-knowledge proof. The auctioneer only obtains the commitments of bids before the bid-opening day, and he has to prove that the winner's bid is the same as the plaintext of the bidders' computed cipher. Thus, the auctioneer can neither leak the bid information nor publish a higher winning price during in the auction. Detailed performance analysis shows that the computational complexity of BSS is linear with the binary length of bids.

In the context of consortium blockchain, consensus protocols set permission mechanisms to maintain a relatively fixed group of participants. They can easily use distributed consistent algorithms for achieving deterministic and efficient consensus and generate incessant blocks as the ledger. However, most of the existing consensus protocols do not sufficiently leverage the chain structure of blocks, and therefore leaving room for performance improvement. In this paper, we first propose a Hashchain-based Consensus Acceleration (HCA) protocol. The HCA protocol enables a leader to generate blocks that contain a quorum of votes on the previous block, and allow voters to re-vote for accelerating the block generation to Byzantine Fault Tolerance (BFT) consensus protocols. Then, we present a rolling-based leader selection (RLS) scheme to further optimize the HCA protocol. In the RLS scheme, the leader is changed in a round-robin fashion. Finally, theoretical analysis proves the safety, liveness and responsiveness of the optimized HCA protocol, while experimental evaluation shows that the optimized HCA protocol outperforms the existing BFT consensus protocols, from the viewpoint of efficiency.

Non-intrusive load monitoring (NILM) aims to decompose aggregated electrical usage signal into appliance-specific power consumption and it amounts to a classical example of blind source separation tasks. Leveraging recent progress on deep learning techniques, we design a new neural NILM model {\em Multi-State Dual CNN} (MSDC). Different from previous models, MSDC explicitly extracts information about the appliance's multiple states and state transitions, which in turn regulates the prediction of signals for appliances. More specifically, we employ a dual-CNN architecture: one CNN for outputting state distributions and the other for predicting the power of each state. A new technique is invented that utilizes conditional random fields (CRF) to capture state transitions. Experiments on two real-world datasets REDD and UK-DALE demonstrate that our model significantly outperform state-of-the-art models while having good generalization capacity, achieving 6%-10% MAE gain and 33%-51% SAE gain to unseen appliances.

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.

This paper presents a novel perspective on the relationship between decentralization, a prevalent characteristic of multi-agent systems, and centralization, which involves imposing central control to achieve system-level objectives. Specifically, within the context of a networked opinion dynamic model, we introduce and discuss a framework for centralization. In this framework, a decentralized network consists of autonomous agents and a dynamic, unknown social structure. Centralization involves appointing specific agents in the network as access units, responsible for providing information and exerting influence within their local environments. We focus on centralization for the DeGroot model of opinion dynamics, aiming to achieve opinion convergence with the minimum number of access units. To accomplish this, we demonstrate that selecting access units to form a dominating set is crucial. Moreover, we propose algorithms based on a new local algorithmic framework called prowling to facilitate this process. Through systematic experiments conducted on both real-world and synthetic networks, we validate our algorithm and show its superiority over benchmark methods.

Diffusion auction is an emerging business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. We focus on designing mechanisms for multi-unit diffusion auctions. Despite numerous attempts at this problem, existing mechanisms either fail to be incentive compatible (IC) or achieve only an unsatisfactory level of social welfare (SW). Here, we propose a novel graph exploration technique to realise multi-item diffusion auction. This technique ensures that potential competition among buyers stay “localised” so as to facilitate truthful bidding. Using this technique, we design multi-unit diffusion auction mechanisms MUDAN and MUDAN-m. Both mechanisms satisfy, among other properties, IC and 1/m-weak efficiency. We also show that they achieve optimal social welfare for the class of rewardless diffusion auctions. While MUDAN addresses the bottleneck case when each buyer demands only a single item, MUDAN-m handles the more general, multi-demand setting. We further demonstrate that these mechanisms achieve near-optimal social welfare through experiments.

With the growth of networks, promoting products through social networks has become an important problem. For auctions in social networks, items are needed to be sold to agents in a network, where each agent can bid and also diffuse the sale information to her neighbors. Thus, the agents’ social relations are intervened with their bids in the auctions. In network auctions, the classical VCG mechanism fails to retain key properties. In order to better understand network auctions, in this paper, we characterize network auctions for the single-unit setting with respect to weak budget balance, individual rationality, incentive compatibility, efficiency, and other properties. For example, we present sufficient conditions for mechanisms to be efficient and (weakly) incentive compatible. With the help of these properties and new concepts such as rewards, participation rewards, and so on, we show how to design efficient mechanisms to satisfy incentive compatibility as much as possible, and incentive compatibility mechanisms to maximize the revenue. Our results provide insights into understanding auctions in social networks.

The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving Müller games. Müller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. The first contribution of this paper is our proof that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. The second contribution is that we non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem. Finally, based on the techniques developed, we recast Horn’s polynomial time algorithm that solves explicitly given Müller games and provide the first correctness proof of the algorithm. Our algorithms are more efficient than that of Horn’s algorithm. Our solution for connectivity games is used as a subroutine in the algorithm.

Diffusion auction refers to an emerging paradigm of online marketplace where an auctioneer utilises a social network to attract potential buyers. Diffusion auction poses significant privacy risks. From the auction outcome, it is possible to infer hidden, and potentially sensitive, preferences of buyers. To mitigate such risks, we initiate the study of differential privacy (DP) in diffusion auction mechanisms. DP is a well-established notion of privacy that protects a system against inference attacks. Achieving DP in diffusion auctions is non-trivial as the well-designed auction rules are required to incentivise the buyers to truthfully report their neighbourhood. We study the single-unit case and design two differentially private diffusion mechanisms (DPDMs): recursive DPDM and layered DPDM. We prove that these mechanisms guarantee differential privacy, incentive compatibility and individual rationality for both valuations and neighbourhood. We then empirically compare their performance on real and synthetic datasets.

We study multi-unit auctions in social networks, where each buyer has a fixed budget and can spread the sale information to the network neighbors. We design a mechanism encouraging buyers to report their valuations truthfully and spread the sale information. Our design uses the idea of the clinching mechanism to decide the transaction price and can be viewed as a network version of the mechanism. Most of the previous clinching mechanisms search for the transaction prices by increasing the current price. Our mechanism directly computes the transaction prices in polynomial time. Furthermore, the mechanism applies a technique to iteratively activate new buyers in the network. This ensures utility preservations of the buyers and benefits the seller. We prove key properties of our mechanism, such as no-positive-transfers, individual rationality, incentive compatibility, non-wastefulness and social welfare preservation.

As networks and their inter-connectivity grow and become complex, failures in the networks impact society and industries more than ever. In these networks the notion of connectedness is the key to understanding and reasoning about these failures. Traditional studies in improving edge/node connectivity assume that failures occur at random. However, in many scenarios (such as earthquakes, hurricanes, and human-designed attacks on networks) failures are not random, and most traditional methods do not always work. To address this limitation, we consider region-based connectivity to capture the local nature of failures under the geographical failure model, where failures may happen only on edges in a sub-network (region) and we want to shield some edges in regions to protect the connectivity. There may be several regions and in different regions the failures occur independently. Firstly, we establish the NP-hardness of the problem for regions, answering a question proposed in previous papers. Secondly, we propose a polynomial-time algorithm for the special case of two regions based on the matroid techniques. Furthermore, we design an ILP-based algorithm to solve the problem for regions. Experimental results on random and real networks show that our algorithms are much faster than previously known algorithms.

Listing dense subgraphs in large graphs plays a key task in varieties of network analysis applications like community detection. Clique, as the densest model, has been widely investigated. However, in practice, communities rarely form as cliques for various reasons, e.g., data noise. Therefore, k-plex, – graph with each vertex adjacent to all but at most k vertices, is introduced as a relaxed version of clique. Often, to better simulate cohesive communities, an emphasis is placed on connected k-plexes with small k. In this paper, we continue the research line of listing all maximal k-plexes and maximal k-plexes of prescribed size. Our first contribution is algorithm ListPlex that lists all maximal k-plexes in O*(γD) time for each constant k, where γ is a value related to k but strictly smaller than 2, and D is the degeneracy of the graph that is far less than the vertex number n in real-word graphs. Compared to the trivial bound of 2n, the improvement is significant, and our bound is better than all previously known results. In practice, we further use several techniques to accelerate listing k-plexes of a given size, such as structural-based prune rules, cache-efficient data structures, and parallel techniques. All these together result in a very practical algorithm. Empirical results show that our approach outperforms the state-of-the-art solutions by up to orders of magnitude.

The quality of covert communications is determined by the choice of communication channels and the design of data embedding schemes. Recently, the Bitcoin system is prevalent as a covert communication channel. The consensus mechanism requires participants to spread their found valid blocks under an adjustable difficulty, which provides a stable periodic broadcast channel. Moreover, senders and receivers are difficult to be traced, because the Bitcoin system is pseudonymous. However, since the historical data in the ledger cannot be removed from the Bitcoin system, the openness and the persistent storage of the ledger in the Bitcoin system post new challenges when designing data embedding schemes. More concreteness, most traditional data embedding schemes either design by heuristic or empirical algorithms or use a fixed field to embed data in the transactions. Therefore, the covert data can be recognized once the algorithm is leaked or the pattern is explored. In this article, we first propose a hash chain-based covert data embedding (HC-CDE) scheme. The embedded transactions are difficult to be discovered. We further propose an elliptic curve Diffie–Hellman chain-based covert data embedding (ECDHC-CDE) scheme to enhance the security of the HC-CDE scheme. Experimental analysis on the Bitcoin Testnet verifies the security and the efficiency of the proposed schemes.

Bitcoin first proposed the Nakamoto consensus that applies proof of work into the blockchain structure to build a trustless append-only ledger. The Nakamoto consensus solves the distributed consistency problem in the public network but wastes too much computing power. Instead of consuming computing resources, many improved consensus schemes address this problem by leveraging miners’ storage resources. However, these schemes fail to let miners store data constantly and usually rely on a dealer to assign data, which is hard to build a reliable decentralized storage system. In this article, we first design a variant consensus algorithm named Proof of Continuous Work (PoCW) with a storage-related incentive mechanism. Miners can accumulate mining advantage by continuously submitting proofs of storage. Then, we present a hash ring-based data allocation algorithm using the blockchain’s state. Combined with both of them, we build a reliable blockchain-based storage system without relying on any third parties. The theoretical analysis and simulation results demonstrate that the proposed system has higher reliability than those existing systems, and we also give practical suggestions about system parameters. Finally, we discuss additional benefits that our system brings.

Abstract The aim of this paper is to shed light on our understanding of large scale properties of infinite strings. We say that one string $\alpha $ has weaker large scale geometry than that of $\beta $ if there is color preserving bi-Lipschitz map from $\alpha $ into $\beta $ with small distortion. This definition allows us to define a partially ordered set of large scale geometries on the classes of all infinite strings. This partial order compares large scale geometries of infinite strings. As such, it presents an algebraic tool for classification of global patterns. We study properties of this partial order. We prove, for instance, that this partial order has a greatest element and also possess infinite chains and antichains. We also investigate the sets of large scale geometries of strings accepted by finite state machines such as Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This connects the work with the complexity theory. We also prove that the quasi-isometry problem is a $\Sigma _2^0$ -complete set, thus providing a bridge with computability theory. Finally, we build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness.

It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct values (a.k.a. colors or priorities)---is proven to be in the class of fixed parameter tractable problems when parameterized over $m$. Both results improve known bounds, from runtime $n^{O(\sqrt{n})}$ to $O(n^{\log(m)+6})$ and from an XP algorithm with runtime $O(n^{\Theta(m)})$ for fixed parameter $m$ to a fixed parameter tractable algorithm with runtime $O(n^5+2^{m\log(m)+6m})$. As an application, it is proven that colored Muller games with $n$ nodes and $m$ colors can be decided in time $O((m^m \cdot n)^5)$; it is also shown that this bound cannot be improved to $2^{o(m \cdot \log(m))} \cdot n^{O(1)}$ in the case that the exponential time hypothesis is true. Further investigations deal with memoryless Muller games and multidimensional parity games.

Users enjoy the convenience of watching videos on smart devices. However, video watching records can be exposed without users’ knowledge and be exploited to infer private information. In this paper, we design and implement a new side-channel attack system, namedvideo aficionado, which can identify video watching information without violating any access control policies on Android. Our system only needs to collect power consumption data of a video playing app, which does not require explicit user permission. The collected data is sent to a remote server, where noise is cleaned and identified by a multi-layer perceptron (MLP) trained classifier. We evaluate our proposed system through a set of carefully designed experiments. Experimental results demonstrate that our system can make an identification with 74.5 percent accuracy on average for each 20-second power measurement segment out of 3918 segments collected from 20 videos. To the best of our knowledge, video aficionado is the first real-time power consumption-based video identification system on smart devices.

Norm emergence is a process where agents in a multi-agent system establish self-enforcing conformity through repeated interactions. When such interactions are confined to a social topology, several self-reinforcing substructures (SRS) may emerge within the population. This prevents a formation of a global norm. We propose incremental social instruments (ISI) to dissolve these SRSs by creating ties between agents. Establishing ties requires some effort and cost. Hence, it is worth to design methods that build a small number of ties yet dissolve the SRSs. By using the notion of information entropy, we propose an indicator called the BA-ratio that measures the current SRSs. We find that by building ties with minimal BA-ratio, our ISI is effective in facilitating the global norm emergence. We explain this through our experiments and theoretical results. Furthermore, we propose the small-degree principle in minimising the BA-ratio that helps us to design efficient ISI algorithms for finding the optimal ties. Experiments on both synthetic and real-world network topologies demonstrate that our adaptive ISI is efficient at dissolving SRS.

In this paper we study the class EqP of automatic equivalence structures of the form ?=(D, E) where the domain D is a regular language of polynomial growth and E is an equivalence relation on D. Our goal is to investigate the following two foundational problems (in the theory of automatic structures) aimed for the class EqP. The first is to find algebraic characterizations of structures from EqP, and the second is to investigate the isomorphism problem for the class EqP. We provide full solutions to these two problems. First, we produce a characterization of structures from EqP through multivariate polynomials. Second, we present two contrasting results. On the one hand, we prove that the isomorphism problem for structures from the class EqP is undecidable. On the other hand, we prove that the isomorphism problem is decidable for structures from EqP with domains of quadratic growth.

WiFi access points are sources of considerable security risks as the wireless signals have the potential to leak important private information such as passwords. This article examines the security issues posed by point-of-sale (POS) terminals which are widely used in WiFi-covered environments, such as restaurants, banks, and libraries. In particular, we envisage an attack model on passwords entered on POS terminals. We put forward the WiPOS, a password inference system based on wireless signals. Specifically, the WiPOS is a device-free system that uses two commercial off-the-shelf (COTS) devices to collect WiFi signals. Implementing a new keystroke segmentation algorithm and adopting support vector machine (SVM) classifiers with global alignment kernel (GAK), the WiPOS achieves improvement on both keystroke recognition and password prediction. The experimental results show that the WiPOS can achieve more than 73% accuracy for 6-digit password with the top 100 candidates. This article calls the community to take a closer look at the risks posed by the current ubiquitous WiFi devices.

Designing systems that make accurate forecasts based on time dependent data is always a challenging and significant task. In this regard, a number of statistics and neural network-based models have been proposed for analyzing and forecasting time series datasets. In this paper, we propose a novel machine learning model for handling and predicting multivariate time series data. In our proposed model we focus on supervised learning technique in which (1) some features of time series dataset exhibit periodic behaviour and (2) time t is considered as an input feature. Due to periodic nature of multivariate time series datasets, our model is a simple neural network where the inputs to the single output source are assumed to be in the form A sin(Bt + C)x as opposed to the standard form inputs Ax + B. We train our proposed model on various datasets and compare our model's performance with standard well-known models used in forecasting multivariate time series datasets. Our results show that our proposed model often outperforms other exiting models in terms of prediction accuracy. Moreover, our results show that the proposed model can handle time series data with missing values and also input data-values that are non-equidistant. We hope that the proposed model will be useful in fostering future research on designing accurate forecasting algorithms.

This paper introduces and studies a notion of \emph{algorithmic randomness} for subgroups of rationals. Given a randomly generated additive subgroup $(G,+)$ of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of $(G,+)$; second, what learnability properties can one extract from $G$ and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of $(G,+)$ coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for $G$ with respect to any generating sequence for $G$ is not even semi-decidable, one can build a generating sequence $β$ such that the word problem for $G$ with respect to $β$ is co-recursively enumerable (assuming that the set of generators of $G$ is limit-recursive). In regard to the second question, it is proven that there is a generating sequence $β$ for $G$ such that every non-trivial finitely generated subgroup of $G$ is recursively enumerable and the class of all such subgroups of $G$ is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of $G$ is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of $G$ cannot be syntactically identified in the limit with respect to any generating sequence for $G$. The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.

We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding of global patterns that occur on infinite strings. We utilise methods of geometric group theory. Our emphasis is on large scale geometries. Two infinite strings have the same large scale geometry if there are colour preserving bi-Lipschitz maps with distortions between the strings. Call these maps quasi-isometries. Introduction of large scale geometries poses several questions. The first question asks to study the partial order induced by quasi-isometries. This partial order compares large scale geometries; as such it presents an algebraic tool for classification of global patterns. We prove there is a greatest large scale geometry and infinitely many minimal large scale geometries. The second question is related to understanding the quasi-isometric maps on various classes of strings. The third question investigates the sets of large scale geometries of strings accepted by computational models, e.g. Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This links large scale geometries with automata theory. The fourth question studies the complexity of the quasi-isometry problem. We show the problem is Σ30-complete thus providing a bridge with computability theory. Finally, the fifth question asks to build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings thus connecting the topic with algorithmic randomness.

It is shown that the parity game can be solved in quasipolynomial time. The parameterised parity game - with n nodes and m distinct values (aka colours or priorities) - is proven to be in the class of fixed parameter tractable (FPT) problems when parameterised over m. Both results improve known bounds, from runtime nO(√n) to O(nlog(m)+6) and from an XP-algorithm with runtime O(nΘ(m)) for fixed parameter m to an FPT-algorithm with runtime O(n5)+g(m), for some function g depending on m only. As an application it is proven that coloured Muller games with n nodes and m colours can be decided in time O((mm · n)5); it is also shown that this bound cannot be improved to O((2m · n)c), for any c, unless FPT = W[1].

An operation f: An → A on the domain A of an algebra A is definable if there exists a first order logic formula Φ(x, y) with parameters from A such that for all ā ∈ An and b ∈ A we have f (ā) = b iff A ⊨ Φ (ā, b). The goal of this paper is to study definability of operations by quantifier-free formulas on countable infinite algebras from computability and model-theoretic definability points of view.

Abstract Let E be a computably enumerable (c.e.) equivalence relation on the set ω of natural numbers. We say that the quotient set $\omega /E$ (or equivalently, the relation E ) realizes a linearly ordered set ${\cal L}$ if there exists a c.e. relation ⊴ respecting E such that the induced structure ( $\omega /E$ ; ⊴) is isomorphic to ${\cal L}$ . Thus, one can consider the class of all linearly ordered sets that are realized by $\omega /E$ ; formally, ${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$ . In this paper we study the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E . One can also define the following pre-order $ \le _{lo} $ on the class of all c.e. equivalence relations: $E_1 \le _{lo} E_2 $ if every linear order realized by E 1 is also realized by E 2 . Following the tradition of computability theory, the lo -degrees are the classes of equivalence relations induced by the pre-order $ \le _{lo} $ . We study the partially ordered set of lo -degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the lo -degrees.

Most recommender systems proposed for service computing do not address the attacks on service rating systems. This paper proposed a service rating system that is capable of countering malicious manipulations. The system predicts how customers rate services based on the ratings given by the similar users of the customers and the trustworthy experienced users. The proposed scheme uses the collaborative filtering technique and a game theory-based approach in choosing users for rating prediction. Compared with existing schemes, the proposed scheme is more effective in countering malicious manipulations.

The concept of cloud computing is changing the way that many industries conduct their businesses. In some industries, distributed resources are clustered together to form a cloud of services. Clients can establish business relationship with the service providers in a service cloud. In practice, businesses would like to build long term and stable business relationship with their business partners. In game theory, it is well known that, to build a stable relationship, both partners must benefit from the relationship. This paper proposed a game theoretic approach to solve the service selection problem. The scheme builds a custom reach ability game according to the business workflows and the business preferences of the client and the service provider. If a solution can be found in the game, it means (a) the functional requirements of the client is satisfied by the service provider, and (b) the business preferences of the client and the service provider can both be satisfied. That is, the client and the service provider can form a stable business relationship.

This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Büchi games played on trees with back-edges in time O(min{r·m, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees with back-edges can be solved in time O(l + m).

Abstract We construct a computable ℵ0-categorical structure whose first order theory is computably equivalent to the true first order theory of arithmetic.

This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over the unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognises the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.

We study the classes of Büchi and Rabin automatic structures. For Büchi (Rabin) automatic structures their domains consist of infinite strings (trees), and the basic relations, including the equality relation, and graphs of operations are recognized by Büchi (Rabin) automata. A Büchi (Rabin) automatic structure is injective if different infinite strings (trees) represent different elements of the structure. The first part of the paper is devoted to understanding the automata-theoretic content of the well-known Löwenheim-Skolem theorem in model theory. We provide automata-theoretic versions of Löwenheim-Skolem theorem for Rabin and Büchi automatic structures. In the second part, we address the following two well-known open problems in the theory of automatic structures: Does every Büchi automatic structure have an injective Büchi presentation? Does every Rabin automatic structure have an injective Rabin presentation? We provide examples of Büchi structures without injective Büchi and Rabin presentations. To answer these questions we introduce Borel structures and usesome of the basic properties of Borel sets and isomorphisms. Finally, in the last part of the paper we study the isomorphism problem for Büchi automatic structures.

Abstract In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ0-categorical saturated structure with a unique computable isomor-phism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of an ℵ1-categorical but not ℵ0-categorical saturated -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an ℵ1-categorical but not ℵ0-categorical theory whose only non-computable model is the prime one.

We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by synchronised automata. Our first topic concerns characterising classes of automatic structures. We supply a characterisation of the automatic Boolean algebras, and it is proven that the free Abelian group of infinite rank, as well as certain Fraisse limits, do not have automatic presentations. In particular, the countably infinite random graph and the random partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. Our second topic is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is \Sigma_1^1-complete.

We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor--Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular, we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.

This paper studies the existence of automatic presentations for various algebraic structures. The automatic Boolean algebras are characterised, and it is proven that the free Abelian group of infinite rank and many Fraisse limits do not have automatic presentations. In particular, the countably infinite random graph and the universal partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. The second topic of the paper is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is /spl Sigma//sub 1//sup 1/-complete.

We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are versions of Cantor-Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular, we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.

Abstract Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.

We study the class of countable structures which can be presented by synchronous finite automata. We reduce the problem of existence of an automatic presentation of a structure to that for a graph. We exhibit a series of properties of automatic equivalence structures, linearly ordered sets and permutation structures. These serve as a first step in producing practical descriptions of some automatic structures or illuminating the complexity of doing so for others.

Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts. The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [13].) The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other, with just structures. If one begins with theories, then a natural version of effectiveness is to consider decidable theories (i.e., ones with a decidable (equivalently, computable or recursive) set of theorems). When one moves to models and wants them to be effective, one might start with the requirement that the model (of any theory) have a decidable theory (i.e., Th ( ), the set of sentences true in , is decidable). Typically, however, one wants to be able to talk about the elements of the model as well as its theory in the given language. Thus one naturally considers the model as a structure for the language expanded by adding a constant ai, for each element ai of . Of course, one requires that the mapping from the constants to the corresponding elements of be effective (computable). We are thus lead to the following basic definition: A structure or model is decidable if there is a computable enumeration ai of A, the domain of , such that Th( , ai,) is decidable. (Of course, ai, is interpreted as ai, for each i Є ω.)

In this paper we introduce effectiveness into model theory of intuitionistic logic. The main result shows that any computable theory T of intuitionistic predicate logic has a Kripke model with decidable forcing such that for any sentence φ, φ is forced in the model if and only if φ is intuitionistically deducible from T.

This paper shows how the notion of randomness defines, in a natural way, an algebra. It turns out that the algebra is computably enumerable and finitely generated. The paper investigates algebraic and effective properties of this algebra.

The spectrum of a relation R on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between A and any other computable structure B. The relation R is intrinsically computably enumerable (c.e.) if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of the minimum element (if it exists) of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family.

We introduce effectiveness considerations into model theory of intuitionistic logic. We investigate effectiveness of completeness (by Kripke) results for intermediate logics such as intuitionistic logic, classical logic, constant domain logic, directed frames logic, and Dummett's logic.