BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jason Teutsch

Jason Teutsch appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Complexitymath.LOComputer Science and Game TheoryCryptography and SecurityLogic in Computer ScienceData Structures and AlgorithmsDiscrete MathematicsDistributed, Parallel, and Cluster ComputingInformation Theorymath.IT

Catalog footprint

What is connected

8works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2016arXiv

How to verify computation with a rational network

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Directed Multicut with linearly ordered terminals

Motivated by an application in network security, we investigate the following "linear" case of Directed Mutlicut. Let $G$ be a directed graph which includes some distinguished vertices $t_1, \ldots, 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^4)$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On approximate decidability of minimal programs

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 some negative results and leave the possibility of positive results as open questions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Short lists for shortest descriptions in short time

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. Our main result extends recent work by Bauwens, Mahklin, Vereschchagin, and Zimand.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Things that can be made into themselves

One says that a property $P$ of sets of natural numbers can be made into itself iff there is a numbering $α_0,α_1,\ldots$ of all left-r.e. sets such that the index set $\{e: α_e$ satisfies $P\}$ has the property $P$ as well. For example, the property of being Martin-Löf random can be made into itself. Herein we characterize those singleton properties which can be made into themselves. A second direction of the present work is the investigation of the structure of left-r.e. sets under inclusion modulo a finite set. In contrast to the corresponding structure for r.e. sets, which has only maximal but no minimal members, both minimal and maximal left-r.e. sets exist. Moreover, our construction of minimal and maximal left-r.e. sets greatly differs from Friedberg's classical construction of maximal r.e. sets. Finally, we investigate whether the properties of minimal and maximal left-r.e. sets can be made into themselves.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Translating the Cantor set by a random

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-Lof 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

How powerful are integer-valued martingales?

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.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

On the Minimal Pseudo-Codewords of Codes from Finite Geometries

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.

0 citations0 reviewsNo code linkedOpen access