We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O(n) attempts. In contrast to this positive result for strings, we find that, in any Kolmogorov numbering, no enumerator of nontrivial size can generate a list containing the minimal index of a given partial-computable function. One cannot even achieve a laconic enumerator for nearly-minimal indices of partial-computable functions.

A set is called r-closed left-r.e. iff every set r-reducible to it is also a left-r.e. set. It is shown that some but not all left-r.e. cohesive sets are many-one closed left-r.e. sets. Ascending reductions are many-one reductions via an ascending function; left-r.e. cohesive sets are also ascending closed left-r.e. sets. Furthermore, it is shown that there is a weakly 1-generic many-one closed left-r.e. set. We also consider initial segment complexity of closed left-r.e. sets. We show that initial segment complexity of ascending closed left-r.e. sets is of sublinear order. Furthermore, this is near optimal as for any non-decreasing unbounded recursive function g, there are ascending closed left-r.e. sets A whose plain complexity satisfies C(A(0)A(1)...A(n)) ≥ n/g(n) for all but finitely many n. The initial segment complexity of a conjunctively (or disjunctively) closed left-r.e. set satisfies, for all ε>0, for all but finitely many n, C(A(0)A(1)...A(n)) ≤ (2+ε) log(n).

The Kučera-Gács theorem is a landmark result in algorithmic randomness asserting that every real is computable from a Martin-Löf random real. If the computation of the first n bits of a sequence requires n+g(n) bits of the random oracle, we say that g is the redundancy of the computation. We establish a lower bound by exhibiting a real X such that the redundancy g of any computation of X from a Martin-Löf random oracle satisfies Σ_n 2^-g(n) < ∞. We also show that every real which is generalized non-low₂ computes a real with the above property. Our results both use and develop the theory of effective betting strategies with restricted wagers.

An index e in a numbering of partial-recursive functions is called minimal if every lesser index computes a different function from e. Since the 1960's it has been known that, in any reasonable programming language, no effective procedure determines whether or not a given index is minimal. We investigate whether the task of determining minimal indices can be solved in an approximate sense. Our first question, regarding the set of minimal indices, is whether there exists an algorithm which can correctly label 1 out of k indices as either minimal or non-minimal. Our second question, regarding the function which computes minimal indices, is whether one can compute a short list of candidate indices which includes a minimal index for a given program. We give negative answers to both questions for the important case of numberings with linearly bounded translators.

We investigate Mark Titchener's T-complexity, an algorithm which measures the information content of finite strings. After introducing the T-complexity algorithm, we turn our attention to a particular class of “simple” finite strings. By exploiting special properties of simple strings, we obtain a fast algorithm to compute the maximum T-complexity among strings of a given length, and our estimates of these maxima show that T-complexity differs asymptotically from Kolmogorov complexity. Finally, we examine how closely de Bruijn sequences resemble strings with high T-complexity.

Is it possible to find a shortest description for a binary string? The well-known answer is “no, Kolmogorov complexity is not computable.” Faced with this barrier, one might instead seek a short list of candidates which includes a laconic description. Remarkably such approximations exist. This paper presents an efficient algorithm which generates a polynomial-size list containing an optimal description for a given input string. Along the way, we employ expander graphs and randomness dispersers to obtain an Explicit Online Matching Theorem for bipartite graphs and a refinement of Muchnik's Conditional Complexity Theorem.

我们说一个自然数的性质P可以成为自己的一员，指的是所有左递归集有一个编码使得满足性质P的指标集也具有性质P。 例如，Martin-Lof随机性质就可以变成自己的一员。 在此，我们刻画所有可以成为自己一员的单元集性质。我们接着研究，有限同余情况下，左递归集所组成的类在包含关系下的结构。这种结构不仅有极大元而且有极小元。相比而言，相应的递归集所组成的类只有极大元没有极小元。 而且，我们构造左递归集的极大元和极小元的方法与经典的Friedberg关于递归类的极大元的方法有很大不同。最后，本文研究极大和极小左递归集的性质是否可以变成自己的一员。

We determine the constructive dimension of points in random translates of the Cantor set. The Cantor set “cancels randomness” in the sense that some of its members, when added to Martin-Löf random reals, identify a point with lower constructive dimension than the random itself. In particular, we find the Hausdorff dimension of the set of points in a Cantor set translate with a given constructive dimension.

Under the assumption that wagers remain integer-valued, as would happen in most casinos, we identify the following bizarre situation: there exists a sequence of coin flips X such that some effective gambler manages to accumulate arbitrary wealth by betting on X, however any such gambler goes bankrupt whenever he tries to take his winnings outside the casino.

A real number which equals the probability that a universal prefix-free machine halts when its input bits are determined by tosses of a fair coin is known as an Omega number. We present a new characterization of Omega numbers: a real in the unit interval is an Omega number if and only if it is the weight of the strings that some universal prefix-free machine compresses by at least a certain constant number of bits. For any universal prefix-free machine U, any a, and any sufficiently large b, the weight of the strings that U compresses by at least a bits but not by b bits is again an Omega number. In fact, we can characterize the Omega numbers by finite intervals of compressibility as well.

We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-Löf, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-Löf randoms and Kurtz non-randoms) have left-r.e. numberings, there is no canonical, or acceptable, left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals.

The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree by identifying an acceptable set of domain-random strings within each degree.

Casinos operate by generating sequences of outcomes which appear unpredictable, or random, to effective gamblers. We investigate relative notions of randomness for gamblers whose wagers are restricted to a finite set. Some sequences which appear unpredictable to gamblers using wager amounts in one set permit unbounded profits for gamblers using different wager values. In particular, we show that for non-empty finite sets A and B, every A-valued random is B-valued random if and only if there exists a k ≥ 0 such that B ⊆ A⋅k.

In the theory of algorithmic randomness, one of the central notions is that of computable randomness. An infinite binary sequence X is computably random if no recursive martingale (strategy) can win an infinite amount of money by betting on the values of the bits of X. In the classical model, the martingales considered are real-valued, that is, the bets made by the martingale can be arbitrary real numbers. In this paper, we investigate a more restricted model, where only integer-valued martingales are considered, and we study the class of random sequences induced by this model.

This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN^* of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN^* is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree.

We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that minimal index sets are immune, and we show that they are also immune against high levels of the arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not simply a refinement of arithmetic complexity. Of particular note here are the fact that there are three minimal index sets located in Π₃ - Σ₃ with distinct levels of immunity and that certain immunity properties depend on the choice of underlying acceptable numbering. We show that minimal index sets are never hyperimmune, however they can be immune against the arithmetic sets. Lastly, we investigate Turing degrees for sets of random strings defined with respect to Bagchi's size-function s.

We study generalizations of shortest programs as they pertain to Schaefer's MIN^* problem. We identify sets of m-minimal and T-minimal indices and characterize their truth-table and Turing degrees. In particular, we show MIN^m ⊕ ∅′′ ≡_T ∅′′′, MIN^T(n) ⊕ ∅⁽ⁿ⁺²⁾ ≡_T ∅⁽ⁿ⁺⁴⁾, and that there exists a Kolmogorov numbering ψ satisfying both MIN^m_ψ ≡_tt ∅′′′ and MIN^T(n)_ψ ≡_T ∅⁽ⁿ⁺⁴⁾. This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, fR, is 2-c.e. but not co-2-c.e. Some open problems are left for the reader.

Bitcoin and Ethereum, whose miners arguably collectively comprise the most powerful computational resource in the history of mankind, offer no more power for processing and verifying transactions than a typical smart phone. The system described herein bypasses this bottleneck and brings scalable computation to Ethereum. Our new system consists of a financial incentive layer atop a dispute resolution layer where the latter takes form of a versatile “verification game.” In addition to secure outsourced computation, immediate applications include decentralized mining pools whose operator is an Ethereum smart contract, a cryptocurrency with scalable transaction throughput, and a trustless means for transferring currency between disjoint cryptocurrency systems.

The present paper introduces a practical protocol for provably secure, outsourced computation. Our protocol minimizes overhead for verification by requiring solutions to withstand an interactive game between a prover and challenger. For optimization problems, the best or nearly best of all submitted solutions is expected to be accepted by this approach. Financial incentives and deposits are used in order to overcome the problem of fake participants.

Cryptocurrencies such as Bitcoin and Ethereum are operated by a handful of mining pools. Nearly 95% of Bitcoin's and 80% of Ethereum's mining power resides with less than ten and six mining pools respectively. Although miners benefit from low payout variance in pooled mining, centralized mining pools require members to trust that pool operators will remunerate them fairly. Furthermore, centralized pools pose the risk of transaction censorship from pool operators, and open up possibilities for collusion between pools for perpetrating severe attacks.

In this work, we propose SmartPool, a novel protocol design for a decentralized mining pool. Our protocol shows how one can leverage smart contracts, autonomous blockchain programs, to decentralize cryptocurrency mining. SmartPool gives transaction selection control back to miners while yielding low-variance payouts. SmartPool incurs mining fees lower than centralized mining pools and is designed to scale to a large number of miners. We implemented and deployed a robust SmartPool implementation on the Ethereum and Ethereum Classic networks. To date, our deployed pools have handled a peak hashrate of 30 GHs from Ethereum miners, resulting in 105 blocks, costing miners a mere 0.6% of block rewards in transaction fees.

Despite their incentive structure flaws, mining pools account for more than 95% of Bitcoin's computation power. This paper introduces an attack against mining pools in which a malicious party pays pool members to withhold their solutions from their pool operator. We show that an adversary with a tiny amount of computing power and capital can execute this attack. Smart contracts enforce the malicious party's payments, and therefore miners need neither trust the attacker's intentions nor his ability to pay. Assuming pool members are rational, an adversary with a single mining ASIC can, in theory, destroy all big mining pools without losing any money (and even make some profit).

Bitcoin and hundreds of other cryptocurrencies employ a consensus protocol called Nakamoto consensus which rewards miners for maintaining a public blockchain. In this paper, we study the security of this protocol with respect to rational miners and show how a minority of the computation power can incentivize the rest of the network to accept a blockchain of the minority's choice. By deviating from the mining protocol, a mining pool which controls at least 38.2% of the network's total computational power can, with modest financial capacity, gain mining advantage over honest mining. Such an attack creates a longer valid blockchain by forking the honest blockchain, and the attacker's blockchain need not disrupt any “legitimate” non-mining transactions present on the honest blockchain. By subverting the consensus protocol, the attacking pool can double-spend money or simply create a blockchain that pays mining rewards to the attacker's pool. We show that our attacks are easy to encode in any Nakamoto-consensus-based cryptocurrency which supports a scripting language that is sufficiently expressive to encode its own mining puzzles.

Cryptocurrencies like Bitcoin and the more recent Ethereum system use contract scripts to support applications beyond simple cash transactions. We analyze the extent to which these systems can correctly enforce scripts whose execution requires nontrivial computation effort. Practical attacks may lead to an ill-fated choice, which we call the verifier's dilemma, in which rational miners are well-incentivized to accept unvalidated blockchains. On the positive side, however, we find that one can implement a certain class of applications while avoiding the catastrophic scenario of unvalidated blockchains. To illustrate this point, we introduce an outsourced computation protocol which offers proper incentives for achieving correct computational results in puzzles where the time required to verify a solution is not too large. We realize this protocol securely in Ethereum.

System administrators employ network monitors, such as traffic analyzers, network intrusion prevention systems, and firewalls, to protect the network's hosts from remote adversaries. The problem is that vulnerabilities are caused primarily by errors in the host software and/or configuration, but modern hosts are too complex for system administrators to understand, limiting monitoring to known attacks. Researchers have proposed automated methods to compute network monitor placements, but these methods also fail to model attack paths within hosts and/or fail to scale beyond tens of hosts. In this paper, we propose a method to compute network monitor placements that leverages commonality in available access control policies across hosts to compute network monitor placement for large-scale systems. We introduce an equivalence property, called flow equivalence, which reduces the size of the placement problem to be proportional to the number of unique host configurations. This process enables us to solve mediation placement problems for thousands of hosts with access control policies containing of thousands of rules in seconds (less than 125 for a network of 9500 hosts). Our method enables administrators to place network monitors in large-scale networks automatically, leveraging the actual host configuration, to detect and prevent network-borne threats.

For given sets A, B and Z of natural numbers where the members of Z are z₀, z₁, ... in ascending order, one says that A is selected from B by Z if A(i) = B(z_i) for all i. Furthermore, say that A is selected from B if A is selected from B by some recursively enumerable set, and that A is selected from B in n steps iff there are sets E₀,E₁,...,E_n such that E₀ = A, E_n = B, and E_i is selected from E_i+1 for each i < n. The following results on selections are obtained in the present paper. A set is ω-r.e. if and only if it can be selected from a recursive set in finitely many steps if and only if it can be selected from a recursive set in two steps. There is some Martin-Löf random set from which any ω-r.e. set can be selected in at most two steps, whereas no recursive set can be selected from a Martin-Löf random set in one step. Moreover, all sets selected from Chaitin's Ω in finitely many steps are Martin-Löf random.

System administrators frequently use Intrusion Detection and Prevention Systems (IDPS) and host security mechanisms, such as firewalls and mandatory access control, to protect their hosts from remote adversaries. The usual techniques for placing network monitoring and intrusion prevention apparatuses in the network do not account for host flows and fail to defend against vulnerabilities resulting from minor modifications to host configurations. Therefore, despite widespread use of these methods, the task of security remains largely reactive. In this paper, we propose an approach to automate a minimal mediation placement for network and host flows. We use Intrusion Prevention System (IPS) as a replacement for certain host mediations. Due to the large number of flows at the host level, we summarize information flows at the composite network level, using a conservative estimate of the host mediation. Our summary technique reduces the number of relevant network nodes in our example network by 80% and improves mediation placement speed by 87.5%. In this way, we effectively and efficiently compute network-wide defense placement for comprehensive security enforcement.

Modern distributed systems combine several off-the-shelf components including operating systems, virtualization infrastructure, and packages with custom application code (e.g., web applications). While several commodity systems now enhance security with mandatory access control (MAC) enforcement, current implementations fail to account for all possible security threats. Indeed they rely on adversaries to identify security vulnerabilities rather than proactively protecting against them. This manuscript introduces a new, automated method for transforming commodity MAC policies into data integrity safeguards which satisfy an approximation of the classical Clark-Wilson integrity model. We find that on a virtualized SELinux host running web applications, adding 27 entry point mediators suffices to mediate the threats of remote adversaries and that we need at most 20 integrity verification procedures to achieve complete information flow integrity.

See journal version.

See journal version.

See journal version.

See journal version.

In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Although our numerical results are only for codes of very modest length, they suggest that these code families exhibit an interesting property. Namely, all minimal pseudo-codewords that are not multiples of a minimal codeword have an AWGNC pseudo-weight that is strictly larger than the minimum Hamming weight of the code. This observation has positive consequences not only for LP decoding but also for iterative decoding.

Data interactions frequently lack provenance due to external dependencies. Indeed, a chasm exists between the visibility of what one computes locally and the more opaque work of others. We investigate this issue within the context of transparent computation wherein a machine which deviates from its prescribed protocol triggers a smoking gun witnessing its erratic behavior. Finally, we implement a protocol which operates efficiently under this model.

We outline a token model for Truebit, a retrofitting, blockchain enhancement which enables secure, community-based computation. The model addresses the challenge of stable task pricing, as raised in the Truebit whitepaper, without appealing to external oracles, exchanges, or hierarchical nodes. The system's sustainable economics and fair market pricing derive from a mintable token format which leverages existing tokens for liquidity. Finally, we introduce a governance layer whose lifecycles culminates with permanent dissolution into utility tokens, thereby tending the network towards autonomous decentralization.

In December 2015, a bounty emerged to establish both reliable communication and secure transfer of value between the Dogecoin and Ethereum blockchains. This prized “Dogethereum bridge” would allow parties to “lock” a DOGE coin on Dogecoin and in exchange receive a newly minted WOW token in Ethereum. Any subsequent owner of the WOW token could burn it and, in exchange, earn the right to “unlock” a DOGE on Dogecoin.

We describe an efficient, trustless, and retrofitting Dogethereum construction which requires no fork but rather employs economic collateral to achieve a “lock” operation in Dogecoin. The protocol relies on bulletproofs, Truebit, and parametrized tokens to efficiently and trustlessly relay events from the “true” Dogecoin blockchain into Ethereum. The present construction not only enables cross-platform exchange but also allows Ethereum smart contracts to trustlessly access Dogecoin. A similar technique adds Ethereum-based smart contracts to Bitcoin and Bitcoin data to Ethereum smart contracts.

Nakamoto consensus, the protocol underlying Bitcoin, has the potential to secure a new class of systems which agree on non-mathematical truths. As an example of this capability, we propose a design for a trustless, data availability oracle. This exposition reduces the problem of determining whether or not a registered datum is publicly available to the problem of constructing a network in which either almost all nodes can download a given datum, or almost none of them can.

Ethereum has emerged as a dynamic platform for exchanging cryptocurrency tokens. While token crowdsales cannot simultaneously guarantee buyers both certainty of valuation and certainty of participation, we show that if each token buyer specifies a desired purchase quantity at each valuation then everyone can successfully participate. Our implementation introduces smart contract techniques which recruit outside participants in order to circumvent computational complexity barriers.

We discuss research developments on the complexity of shortest programs since the turn of the millennium. In particular, we will delve into the phenomenon of list approximation: while it's impossible to compute the shortest description for a given string, we can efficiently generate a short list of candidates which includes a (nearly) shortest description.

Motivated by an application in network security, we investigate the following “linear” case of Directed Multicut. Let G be a directed graph which includes some distinguished vertices t₁, ..., t_k. What is the size of the smallest edge cut which eliminates all paths from t_i to t_j for all i < j? We show that this problem is fixed-parameter tractable when parametrized in the cutset size p via an algorithm running in O(4^p p n⁴) time.

I review a book by Rod Downey and Denis Hirschfeldt.

It is possible to enumerate all computer programs. In particular, for every partial computable function, there is a shortest program which computes that function. f-MIN is the set of indices for shortest programs. In 1972, Meyer showed that f-MIN is Turing equivalent to ∅′′, the halting set with halting set oracle. This paper generalizes the notion of shortest programs, and we use various measures from computability theory to describe the complexity of the resulting "spectral sets." We show that under certain Godel numberings, the spectral sets are exactly the canonical sets ∅′, ∅′′, ∅′′′, ... up to Turing equivalence. This is probably not true in general, however we show that spectral sets always contain some useful information. We show that immunity, or "thinness" is a useful characteristic for distinguishing between spectral sets. In the final chapter, we construct a set which neither contains nor is disjoint from any infinite arithmetic set, yet it is 0-majorized and contains a natural spectral set. Thus a pathological set becomes a bit more friendly. Finally, a number of interesting open problems are left for the inspired reader.