Jack H. Lutz

According to our database1, Jack H. Lutz authored at least 175 papers between 1987 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension.
TOCT, 2018

Mutual dimension and random sequences.
Theor. Comput. Sci., 2018

Reachability problems for continuous chemical reaction networks.
Natural Computing, 2018

Real-Time Computability of Real Numbers by Chemical Reaction Networks.
CoRR, 2018

Writing Requirements for Molecular Programs.
Proceedings of the 26th IEEE International Requirements Engineering Conference, 2018

2017
Runtime Fault Detection in Programmed Molecular Systems.
CoRR, 2017

Real-Time Computability of Real Numbers by Chemical Reaction Networks.
Proceedings of the Unconventional Computation and Natural Computation, 2017

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016
Computing Absolutely Normal Numbers in Nearly Linear Time.
CoRR, 2016

Mutual Dimension and Random Sequences.
CoRR, 2016

Reachability Problems for Continuous Chemical Reaction Networks.
Proceedings of the Unconventional Computation and Natural Computation, 2016

Software engineering for molecular programming.
Proceedings of the 38th International Conference on Software Engineering, 2016

2015
Mutual Dimension.
TOCT, 2015

Reachability Problems for Continuous Chemical Reaction Networks.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Algorithmic information and plane Kakeya sets.
CoRR, 2015

Robust Biomolecular Finite Automata.
CoRR, 2015

Reachability Problems for Continuous Chemical Reaction Networks.
CoRR, 2015

Lines missing every random point.
Computability, 2015

Mutual Dimension and Random Sequences.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014
The frequent paucity of trivial strings.
Inf. Process. Lett., 2014

Lines Missing Every Random Point.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Mutual Dimension.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Lines Missing Every Random Point.
CoRR, 2014

Mutual Dimension.
CoRR, 2014

Dimension spectra of random subfractals of self-similar fractals.
Ann. Pure Appl. Logic, 2014

Automated requirements analysis for a molecular watchdog timer.
Proceedings of the ACM/IEEE International Conference on Automated Software Engineering, 2014

Lines Missing Every Random Point.
Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe, 2014

2013
The Frequent Paucity of Trivial Strings.
Electronic Colloquium on Computational Complexity (ECCC), 2013

The Frequent Paucity of Trivial Strings.
CoRR, 2013

Mutual Dimension.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012
Approximate Self-Assembly of the Sierpinski Triangle.
Theory Comput. Syst., 2012

Inseparability and Strong Hypotheses for Disjoint NP Pairs.
Theory Comput. Syst., 2012

Translating the Cantor set by a random
CoRR, 2012

Reasoning As Though.
Proceedings of the Unconventional Computation and Natural Computation, 2012

Requirements analysis for a product family of DNA nanodevices.
Proceedings of the 2012 20th IEEE International Requirements Engineering Conference (RE), 2012

The Computer Science of DNA Nanotechnology.
Proceedings of the Language and Automata Theory and Applications, 2012

Engineering and verifying requirements for programmable self-assembling nanomachines.
Proceedings of the 34th International Conference on Software Engineering, 2012

The Tile Assembly Model is Intrinsically Universal.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
A divergence formula for randomness and dimension.
Theor. Comput. Sci., 2011

Effective dimensions and relative frequencies.
Theor. Comput. Sci., 2011

Computability and Complexity in Self-assembly.
Theory Comput. Syst., 2011

Curves that must be retraced.
Inf. Comput., 2011

The tile assembly model is intrinsically universal
CoRR, 2011

Axiomatizing Resource Bounds for Measure
CoRR, 2011

Resource Bounded Measure
CoRR, 2011

The Computer Science of Molecular Programming.
Proceedings of the DNA Computing and Molecular Programming - 17th International Conference, 2011

Multi-Resolution Cellular Automata for Real Computation.
Proceedings of the Models of Computation in Context, 2011

Axiomatizing Resource Bounds for Measure.
Proceedings of the Models of Computation in Context, 2011

2010
Approximate Self-Assembly of the Sierpinski Triangle.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Approximate Self-Assembly of the Sierpinski Triangle
CoRR, 2010

Intrinsic Universality in Self-Assembly
CoRR, 2010

Inseparability and Strong Hypotheses for Disjoint NP Pairs.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Intrinsic Universality in Self-Assembly.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Approximate Self-assembly of the Sierpinski Triangle.
Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009
Strict self-assembly of discrete Sierpinski triangles.
Theor. Comput. Sci., 2009

Inseparability and Strong Hypotheses for Disjoint NP Pairs.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Strict Self-Assembly of Discrete Sierpinski Triangles
CoRR, 2009

Inseparability and Strong Hypotheses for Disjoint NP Pairs
CoRR, 2009

Random Number Selection in Self-assembly.
Proceedings of the Unconventional Computation, 8th International Conference, 2009

A Divergence Formula for Randomness and Dimension.
Proceedings of the Mathematical Theory and Computational Practice, 2009

Curves That Must Be Retraced.
Proceedings of the Sixth International Conference on Computability and Complexity in Analysis, 2009

2008
Dimensions of Points in Self-Similar Fractals.
SIAM J. Comput., 2008

Connectivity properties of dimension level sets.
Math. Log. Q., 2008

Connectivity Properties of Dimension Level Sets.
Electr. Notes Theor. Comput. Sci., 2008

A Divergence Formula for Randomness and Dimension.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Strict Self-Assembly of Discrete Sierpinski Triangles.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Computability and Complexity in Self-Assembly.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Curves That Must Be Retraced.
Electronic Colloquium on Computational Complexity (ECCC), 2008

A Divergence Formula for Randomness and Dimension (Short Version)
Proceedings of the Proceedings International Workshop on The Complexity of Simple Programs, 2008

A Divergence Formula for Randomness and Dimension
CoRR, 2008

Curves That Must Be Retraced.
CoRR, 2008

Dimension Characterizations of Complexity Classes.
Computational Complexity, 2008

Complexes of on-line self assembly.
Proceedings of the 2008 IEEE International Conference on Electro/Information Technology, 2008

Dimensions of Points in Self-similar Fractals.
Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

Computability and Complexity in Self-assembly.
Proceedings of the Logic and Theory of Algorithms, 2008

Effective Dimensions and Relative Frequencies.
Proceedings of the Logic and Theory of Algorithms, 2008

2007
The arithmetical complexity of dimension and randomness.
ACM Trans. Comput. Log., 2007

Effective Strong Dimension in Algorithmic Information and Computational Complexity.
SIAM J. Comput., 2007

Dimensions of Copeland-Erdös sequences.
Inf. Comput., 2007

Finite-state dimension and real arithmetic.
Inf. Comput., 2007

Dimension and Relative Frequencies
CoRR, 2007

Strict Self-assembly of Discrete Sierpinski Triangles.
Proceedings of the Computation and Logic in the Real World, 2007

2006
Why Computational Complexity Requires Stricter Martingales.
Theory Comput. Syst., 2006

Finite-State Dimension and Real Arithmetic.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Finite-State Dimension and Real Arithmetic
CoRR, 2006

Dimension Characterizations of Complexity Classes.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Finite-State Dimension and Real Arithmetic.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Points on Computable Curves.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Effective fractal dimensions.
Math. Log. Q., 2005

Prediction and dimension.
J. Comput. Syst. Sci., 2005

Weakly useful sequences.
Inf. Comput., 2005

Dimension Characterizations of Complexity Classes
Electronic Colloquium on Computational Complexity (ECCC), 2005

Points on Computable Curves
Electronic Colloquium on Computational Complexity (ECCC), 2005

Dimensions of Copeland-Erdös Sequences
Electronic Colloquium on Computational Complexity (ECCC), 2005

Points on Computable Curves
CoRR, 2005

Dimensions of Copeland-Erdos Sequences
CoRR, 2005

Zeta-Dimension
CoRR, 2005

Zeta-Dimension.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Dimensions of Copeland-Erdös Sequences.
Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

The Dimension of a Point: Computability Meets Fractal Geometry.
Proceedings of the New Computational Paradigms, 2005

2004
Finite-state dimension.
Theor. Comput. Sci., 2004

Baire category and nowhere differentiability for feasible real functions.
Math. Log. Q., 2004

Scaled dimension and nonuniform complexity.
J. Comput. Syst. Sci., 2004

Computability versus exact computability of martingales.
Inf. Process. Lett., 2004

The Arithmetical Complexity of Dimension and Randomness
Electronic Colloquium on Computational Complexity (ECCC), 2004

The Arithmetical Complexity of Dimension and Randomness
CoRR, 2004

Effective Strong Dimension in Algorithmic Information and Computational Complexity.
Proceedings of the STACS 2004, 2004

2003
Dimension in Complexity Classes.
SIAM J. Comput., 2003

The dimensions of individual strings and sequences.
Inf. Comput., 2003

Scaled Dimension and Nonuniform Complexity.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

The Arithmetical Complexity of Dimension and Randomness.
Proceedings of the Computer Science Logic, 17th International Workshop, 2003

2002
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
CoRR, 2002

The Dimensions of Individual Strings and Sequences
CoRR, 2002

Dimension in Complexity Classes
CoRR, 2002

Why Computational Complexity Requires Stricter Martingales.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Prediction and Dimension.
Proceedings of the Computational Learning Theory, 2002

2001
Baire Category and Nowhere Differentiability for Feasible Real Functions.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

Finite-State Dimension.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Twelve Problems in Resource-Bounded Measure.
Current Trends in Theoretical Computer Science, 2001

2000
The Density of Weakly Complete Problems under Adaptive Reductions.
SIAM J. Comput., 2000

Modeling Time-Bounded Prefix Kolmogorov Complexity.
Theory Comput. Syst., 2000

Bias Invariance of Small Upper Spans.
Proceedings of the STACS 2000, 2000

Hard Instances of Hard Problems.
Proceedings of the STACS 2000, 2000

Gales and the Constructive Dimension of Individual Sequences.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Dimension in Complexity Classes.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
Feasible Reductions to Kolmogorov-Loveland Stochastic Sequences.
Theor. Comput. Sci., 1999

Equivalence of Measures of Complexity Classes.
SIAM J. Comput., 1999

Recursive Computational Depth.
Inf. Comput., 1999

Twelve Problems in Resource-Bounded Measure.
Bulletin of the EATCS, 1999

Query Order and NP-Completeness.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Genericity and Randomness over Feasible Probability Measures.
Theor. Comput. Sci., 1998

Resource-Bounded Measure.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
Observations on Measure and Lowness for \Delta^p_2.
Theory Comput. Syst., 1997

Report on the Workshop on Languages, Algorithms and Complexity, Minneapolis, USA, 12 April 1997.
Bulletin of the EATCS, 1997

Equivalence of Measures of Complexity Classes.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Recursive Computational Depth.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

The Density of Weakly Complete Problems under Adaptive Reductions.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Genericity and Randomness over Feasible Probability Measures.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996
Cook Versus Karp-Levin: Separating Completeness Notions if NP is not Small.
Theor. Comput. Sci., 1996

Completeness and Weak Completeness Under Polynomial-Size Circuits.
Inf. Comput., 1996

Observations on Measure and Lowness for Delta^P_2.
Proceedings of the STACS 96, 1996

1995
The Global Power of Additional Queries to Random Oracles
Inf. Comput., July, 1995

Weak Completeness in E and E_2.
Theor. Comput. Sci., 1995

Weakly Hard Problems.
SIAM J. Comput., 1995

The Complexity and Distribution of Hard Problems.
SIAM J. Comput., 1995

Completeness and Weak Completeness Under Polynomial-Size Circuits.
STACS, 1995

Weakly Useful Sequences.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

A Small Span Theorem for P/Poly-Turing Reductions.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
Computational Depth and Reducibility.
Theor. Comput. Sci., 1994

Measure, Stochasticity, and the Density of Hard Languages.
SIAM J. Comput., 1994

An Observation on Probability Versus Randomness with Applications to Complexity Classes.
Mathematical Systems Theory, 1994

Cook Versus Karp-Levin: Separating Completeness Notions if NP Is not Small (Extended Abstract).
Proceedings of the STACS 94, 1994

The Global Power of Additional Queries to Random Oracles.
Proceedings of the STACS 94, 1994

Weakly Hard Problems.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
Circuit Size Relative to Pseudorandom Oracles.
Theor. Comput. Sci., 1993

A Pseudorandom Oracle Characterization of BPP.
SIAM J. Comput., 1993

On Languages With Very High Space-Bounded Kolmogorov Complexity.
SIAM J. Comput., 1993

Measure, Stochasticity, and the Density of Hard Languages.
Proceedings of the STACS 93, 1993

Computational Depth and Reducibility (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

The Complexity and Distribution of Hard Problems (Extended Abstract)
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

The Quantitative Structure of Exponential Time.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
On Independent Random Oracles.
Theor. Comput. Sci., 1992

Almost Everywhere High Nonuniform Complexity.
J. Comput. Syst. Sci., 1992

On Complexity Classes and Algorithmically Random Languages (Extended Abstract).
Proceedings of the STACS 92, 1992

On Languages with Very High Information Content.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
An Upward Measure Separation Theorem.
Theor. Comput. Sci., 1991

Errata for Circuit Size to Pseudorandom Oracles.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

A Pseudorandom Oracle Characterization of BPP.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990
Category and Measure in Complexity Classes.
SIAM J. Comput., 1990

Pseudorandom Sources for BPP.
J. Comput. Syst. Sci., 1990

Additional Queries to Random and Pseudorandom Oracles.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Circuit Size Relative to Pseudorandom Oracles.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Almost Everywhere High Nonuniform Complexity.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Pseudorandom sources for BPP.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Resource bounded baire category and small circuits in exponential space.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987


  Loading...