[1] 
Jason Teutsch.
On decentralized oracles for data availability.
(submitted).
[ .pdf ]
Nakamoto consensus, the protocol underlying Bitcoin, has the potential to secure a new class of systems which agree on nonmathematical 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.

[2] 
Sanjay Jain and Jason Teutsch.
Enumerations
including laconic enumerators.
Theoretical Computer Science, 700:8995, 2017.
[ .pdf ]
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 partialcomputable function. One cannot even achieve a laconic enumerator for nearlyminimal indices of partialcomputable functions.

[3] 
Sanjay Jain, Frank Stephan, and Jason Teutsch.
Closed leftr.e. sets.
Computability, 6(1):121, 2017.
[ .pdf ]
A set is called rclosed leftr.e. iff every set rreducible to it is also a leftr.e. set. It is shown that some but not all leftr.e. cohesive sets are manyone closed leftr.e. sets. Ascending reductions are manyone reductions via an ascending function; leftr.e. cohesive sets are also ascending closed leftr.e. sets. Furthermore, it is shown that there is a weakly 1generic manyone closed leftr.e. set. We also consider initial segment complexity of closed leftr.e. sets. We show that initial segment complexity of ascending closed leftr.e. sets is of sublinear order. Furthermore, this is near optimal as for any nondecreasing unbounded recursive function g, there are ascending closed leftr.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 leftr.e. set satisfies, for all ε>0, for all but finitely many n, C(A(0)A(1)...A(n)) ≤ (2+ε) log(n).

[4] 
George Barmpalias, Andrew LewisPye, and Jason Teutsch.
Lower bounds on the
redundancy in computations from random oracles via betting strategies with
restricted wagers.
Information and Computation, 251:287300, December 2016.
[ .pdf ]
The KučeraGács theorem is a landmark result in algorithmic randomness asserting that every real is computable from a MartinLö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 MartinLöf random oracle satisfies Σ_{n} 2^{g(n)} < ∞. We also show that every real which is generalized nonlow_{2} computes a real with the above property. Our results both use and develop the theory of effective betting strategies with restricted wagers.

[5] 
Jason Teutsch and Marius Zimand.
On approximate decidability
of minimal programs.
ACM Transactions on Computational Theory, 7(4):17:117:16,
August 2015.
[ .pdf ]
An index e in a numbering of partialrecursive 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 nonminimal. 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.

[6] 
Greg Clark and Jason Teutsch.
Maximizing
Tcomplexity.
Fundamenta Informaticae, 139(1):119, 2015.
[ .pdf ]
We investigate Mark Titchener's Tcomplexity, an algorithm which measures the information content of finite strings. After introducing the Tcomplexity 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 Tcomplexity among strings of a given length, and our estimates of these maxima show that Tcomplexity differs asymptotically from Kolmogorov complexity. Finally, we examine how closely de Bruijn sequences resemble strings with high Tcomplexity.

[7] 
Jason Teutsch.
Short lists for
shortest descriptions in short time.
Computational Complexity, 23(4):565583, December 2014.
[ .pdf ]
Is it possible to find a shortest description for a binary string? The wellknown 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 polynomialsize 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.

[8] 
Frank Stephan and Jason Teutsch.
Things that can be
made into themselves.
Information and Computation, 237:174186, October 2014.
[ .pdf ]
我们说一个自然数的性质P可以成为自己的一员，指的是所有左递归集有一个编码使得满足性质P的指标集也具有性质P。 例如，MartinLof随机性质就可以变成自己的一员。 在此，我们刻画所有可以成为自己一员的单元集性质。我们接着研究，有限同余情况下，左递归集所组成的类在包含关系下的结构。这种结构不仅有极大元而且有极小元。相比而言，相应的递归集所组成的类只有极大元没有极小元。 而且，我们构造左递归集的极大元和极小元的方法与经典的Friedberg关于递归类的极大元的方法有很大不同。最后，本文研究极大和极小左递归集的性质是否可以变成自己的一员。

[9] 
Randall Dougherty, Jack H. Lutz, Daniel R. Mauldin, and Jason Teutsch.
Translating
the Cantor set by a random real.
Transactions of the American Mathematical Society,
366:30273041, 2014.
[ .pdf ]
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 MartinLö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.

[10] 
Jason Teutsch.
A savings paradox
for integervalued gambling strategies.
International Journal of Game Theory, 43(1):145151, February
2014.
[ .pdf ]
Under the assumption that wagers remain integervalued, 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.

[11] 
Wolfgang Merkle and Jason Teutsch.
Constant compression and
random weights.
Computability, 1(2):153169, 2012.
[ .pdf ]
A real number which equals the probability that a universal prefixfree 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 prefixfree machine compresses by at least a certain constant number of bits. For any universal prefixfree 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.

[12] 
Bjørn KjosHanssen, Frank Stephan, and Jason Teutsch.
Arithmetic
complexity via effective names for random sequences.
ACM Transactions on Computational Logic, 13(3):24:124:18,
August 2012.
[ .pdf ]
We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or leftr.e. sets. In addition to pinpointing the complexity of leftr.e. MartinLöf, computably, Schnorr, and Kurtz random sets, weakly 1generics 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 leftr.e. sets with shiftpersistent elements. While some classes (such as MartinLöf randoms and Kurtz nonrandoms) have leftr.e. numberings, there is no canonical, or acceptable, leftr.e. numbering for any class of leftr.e. randoms. Finally, we note some fundamental differences between leftr.e. numberings for sets and reals.

[13] 
Frank Stephan and Jason Teutsch.
An incomplete
set of shortest descriptions.
The Journal of Symbolic Logic, 77(1):291307, March 2012.
[ .pdf ]
The truthtable 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 domainrandom strings, and show that the truthtable degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truthtable incomplete versions of these sets, namely retraceability and approximability. We give priorityfree constructions of bounded truthtable chains and bounded truthtable antichains inside the truthtable complete degree by identifying an acceptable set of domainrandom strings within each degree.

[14] 
Adam Chalcraft, Randall Dougherty, Chris Freiling, and Jason Teutsch.
How to build a
probabilityfree casino.
Information and Computation, 211:160164, February 2012.
[ .pdf ]
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 nonempty finite sets A and B, every Avalued random is Bvalued random if and only if there exists a k ≥ 0 such that B ⊆ A⋅k.

[15] 
Laurent Bienvenu, Frank Stephan, and Jason Teutsch.
How powerful are
integervalued martingales?
Theory of Computing Systems, 51(3):330351, October 2012.
Special issue for CiE 2010.
[ .pdf ]
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 realvalued, that is, the bets made by the martingale can be arbitrary real numbers. In this paper, we investigate a more restricted model, where only integervalued martingales are considered, and we study the class of random sequences induced by this model.

[16] 
Sanjay Jain, Frank Stephan, and Jason Teutsch.
Index sets and
universal numberings.
Journal of Computer and System Sciences, 77(4):760773, July
2011.
[ .pdf ]
This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partialrecursive 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 1generic Turing degree.

[17] 
Frank Stephan and Jason Teutsch.
Immunity and
hyperimmunity for sets of minimal indices.
Notre Dame Journal of Formal Logic, 49(2):107125, 2008.
[ .pdf ]
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 Π_{3}  Σ_{3} 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 sizefunction s.

[18] 
Jason Teutsch.
On the Turing
degrees of minimal index sets.
Annals of Pure and Applied Logic, 148:6380, September 2007.
[ .pdf ]
We study generalizations of shortest programs as they pertain to Schaefer's MIN^{*} problem. We identify sets of mminimal and Tminimal indices and characterize their truthtable and Turing degrees. In particular, we show MIN^{m} ⊕ ∅′′ ≡_{T} ∅′′′, MIN^{T(n)} ⊕ ∅^{(n+2)} ≡_{T} ∅^{(n+4)}, and that there exists a Kolmogorov numbering ψ satisfying both MIN^{m}_{ψ} ≡_{tt} ∅′′′ and MIN^{T(n)}_{ψ} ≡_{T} ∅^{(n+4)}. This Kolmogorov numbering also achieves maximal truthtable degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, fR, is 2c.e. but not co2c.e. Some open problems are left for the reader.

[1] 
Loi Luu, Yaron Velner, Jason Teutsch, and Prateek Saxena.
SmartPool:
Practical Decentralized Pooled Mining.
In 26th USENIX Security Symposium (USENIX 17), pages
14091426, Vancouver, BC, 2017. USENIX Association.
[ http 
.pdf ]
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.

[2] 
Yaron Velner, Jason Teutsch, and Loi Luu.
Smart contracts
make Bitcoin mining pools vulnerable.
In Financial Cryptography and Data Security (BITCOIN 2017),
pages 298316. Springer Cham, 2017.
To appear in 4th Workshop on Bitcoin and Blockchain Research.
[ .pdf ]
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).

[3] 
Jason Teutsch, Sanjay Jain, and Prateek Saxena.
When
cryptocurrencies mine their own business.
In Financial Cryptography and Data Security: 20th International
Conference (FC 2016) Christ Church, Barbados, pages 499514. Springer
Berlin / Heidelberg, 2017.
[ .pdf ]
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” nonmining transactions present on the honest blockchain. By subverting the consensus protocol, the attacking pool can doublespend 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 Nakamotoconsensusbased cryptocurrency which supports a scripting language that is sufficiently expressive to encode its own mining puzzles.

[4] 
Loi Luu, Jason Teutsch, Raghav Kulkarni, and Prateek Saxena.
Demystifying
incentives in the consensus computer.
In Proceedings of the 22nd ACM SIGSAC Conference on Computer and
Communications Security (CCS 2015), pages 706719, New York, NY, USA, 2015.
ACM.
[ .pdf ]
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 illfated choice, which we call the verifier's dilemma, in which rational miners are wellincentivized 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.

[5] 
Nirupama Talele, Jason Teutsch, Robert Erbacher, and Trent Jaeger.
Monitor placement
for largescale systems.
In Proceedings of the 19th ACM Symposium on Access Control
Models and Technologies (SACMAT 2014), pages 2940, New York, NY, USA,
2014. ACM.
[ .pdf ]
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 largescale 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 largescale networks automatically, leveraging the actual host configuration, to detect and prevent networkborne threats.

[6] 
Wolfgang Merkle, Frank Stephan, Jason Teutsch, Wei Wang, and Yue Yang.
Selection by
recursively enumerable sets.
In Theory and Applications of Models of Computation (TAMC
2013), volume 7876 of Lecture Notes in Computer Science, pages
144155. Springer, Berlin / Heidelberg, 2013.
[ .pdf ]
For given sets A, B and Z of natural numbers where the members of Z are z_{0}, z_{1}, ... 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_{0},E_{1},...,E_{n} such that E_{0} = 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 MartinLö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 MartinLöf random set in one step. Moreover, all sets selected from Chaitin's Ω in finitely many steps are MartinLöf random.

[7] 
Nirupama Talele, Jason Teutsch, Trent Jaeger, and Robert F. Erbacher.
Using security
policies to automate placement of network intrusion prevention.
In Engineering Secure Software and Systems (ESSoS 2013), volume
7781 of Lecture Notes in Computer Science, pages 1732. Springer,
Berlin / Heidelberg, 2013.
[ .pdf ]
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 networkwide defense placement for comprehensive security enforcement.

[8] 
Divya Muthukumaran, Sandra Rueda, Nirupama Talele, Hayawardh Vijayakumar, Trent
Jaeger, Jason Teutsch, and Nigel Edwards.
Transforming
commodity security policies to enforce ClarkWilson integrity.
In Proceedings of the 28th Annual Computer Security Applications
Conference (ACSAC 2012), December 2012.
[ .pdf ]
Modern distributed systems combine several offtheshelf 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 ClarkWilson 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.

[9] 
Wolfgang Merkle and Jason Teutsch.
Constant
compression and random weights.
In 29th International Symposium on Theoretical Aspects of
Computer Science (STACS 2012), volume 14 of Leibniz International
Proceedings in Informatics (LIPIcs), pages 172181, Dagstuhl, Germany,
2012.
[ .pdf ]
See journal version.

[10] 
Sanjay Jain, Frank Stephan, and Jason Teutsch.
Closed
leftr.e. sets.
In Theory and Applications of Models of Computation (TAMC
2011), volume 6648 of Lecture Notes in Computer Science, pages
218229. Springer, Berlin / Heidelberg, 2011.
[ .pdf ]
See journal version.

[11] 
Laurent Bienvenu, Frank Stephan, and Jason Teutsch.
How powerful are
integervalued martingales?
In Programs, Proofs, Processes (CiE 2010), volume 6158 of
Lecture Notes in Computer Science, pages 5968. SpringerVerlag, Berlin /
Heidelberg, 2010.
[ .pdf ]
See journal version.

[12] 
Sanjay Jain, Frank Stephan, and Jason Teutsch.
Index sets and
universal numberings.
In Mathematical Theory and Computational Practice (CiE 2009),
volume 5635 of Lecture Notes in Computer Science, pages 270279.
SpringerVerlag, Berlin / Heidelberg, 2009.
[ .pdf ]
See journal version.

[13] 
Pascal O. Vontobel, Roxana Smarandache, Negar Kiyavash, Jason Teutsch, and
Dejan Vukobratovic.
On the minimal
pseudocodewords of codes from finite geometries.
In Proceedings of IEEE International Symposium on Information
Theory (ISIT 2005), pages 980984, Adelaide, Australia, 2005.
[ ArXiv ]
In order to understand the performance of a code under maximumlikelihood (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 pseudocodewords. This paper studies the minimal codewords and minimal pseudocodewords 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 pseudocodewords that are not multiples of a minimal codeword have an AWGNC pseudoweight 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.

[1] 
Jason Teutsch, Michael Straka, and Dan Boneh.
Retrofitting a twoway peg between blockchains.
[ .pdf ]
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.

[2] 
Jason Teutsch, Vitalik Buterin, and Christopher Brown.
Interactive coin offerings.
[ .pdf ]
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.

[3] 
Jason Teutsch and Christian Reitwießner.
A scalable verification solution for blockchains.
[ http 
.pdf ]
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.

[4] 
Sanjay Jain, Prateek Saxena, Frank Stephan, and Jason Teutsch.
How to verify computation with
a rational network.
2016.
[ .pdf ]
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.

[5] 
Jason Teutsch and Marius Zimand.
A brief on short
descriptions.
SIGACT News, 47(1):4267, March 2016.
[ .pdf ]
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.

[6] 
Robert F. Erbacher, Trent Jaeger, Nirupama Talele, and Jason Teutsch.
Directed Multicut with
linearly ordered terminals.
2014.
[ .pdf ]
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_{1}, ..., 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 fixedparameter tractable when parametrized in the cutset size p via an algorithm running in O(4^{p} p n^{4}) time.

[7] 
Jason Teutsch.
Review of
Algorithmic Randomness and Complexity by Downey and Hirschfeldt.
SIGACT News, 44(1):2528, March 2013.
[ .pdf ]
I review a book by Rod Downey and Denis Hirschfeldt.

[8] 
Jason R. Teutsch.
Noncomputable Spectral
Sets.
PhD thesis, Indiana University, 2007.
[ ArXiv ]
It is possible to enumerate all computer programs. In particular, for every partial computable function, there is a shortest program which computes that function. fMIN is the set of indices for shortest programs. In 1972, Meyer showed that fMIN 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 0majorized 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.

This file was generated by bibtex2html 1.95 or 1.96.