| 2009 |
|---|
| 112 | EE | Jack H. Lutz,
Elvira Mayordomo:
Inseparability and Strong Hypotheses for Disjoint NP Pairs
CoRR abs/0902.2674: (2009) |
| 111 | EE | James I. Lathrop,
Jack H. Lutz,
Scott M. Summers:
Strict Self-Assembly of Discrete Sierpinski Triangles
CoRR abs/0903.1818: (2009) |
| 110 | EE | James I. Lathrop,
Jack H. Lutz,
Scott M. Summers:
Strict self-assembly of discrete Sierpinski triangles.
Theor. Comput. Sci. 410(4-5): 384-405 (2009) |
| 2008 |
|---|
| 109 | EE | Jack H. Lutz,
Elvira Mayordomo:
Dimensions of Points in Self-similar Fractals.
COCOON 2008: 215-224 |
| 108 | | Jack H. Lutz:
A Divergence Formula for Randomness and Dimension.
CSP 2008: 191-200 |
| 107 | EE | Xiaoyang Gu,
Jack H. Lutz:
Effective Dimensions and Relative Frequencies.
CiE 2008: 231-240 |
| 106 | EE | James I. Lathrop,
Jack H. Lutz,
Matthew J. Patitz,
Scott M. Summers:
Computability and Complexity in Self-assembly.
CiE 2008: 349-358 |
| 105 | EE | Jack H. Lutz:
A Divergence Formula for Randomness and Dimension
CoRR abs/0811.1825: (2008) |
| 104 | EE | Jack H. Lutz,
Klaus Weihrauch:
Connectivity Properties of Dimension Level Sets.
Electr. Notes Theor. Comput. Sci. 202: 295-304 (2008) |
| 103 | EE | James I. Lathrop,
Jack H. Lutz,
Matthew J. Patitz,
Scott M. Summers:
Computability and Complexity in Self-Assembly.
Electronic Colloquium on Computational Complexity (ECCC) 15(031): (2008) |
| 102 | EE | James I. Lathrop,
Jack H. Lutz,
Scott M. Summers:
Strict Self-Assembly of Discrete Sierpinski Triangles.
Electronic Colloquium on Computational Complexity (ECCC) 15(035): (2008) |
| 101 | EE | Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo:
Curves That Must Be Retraced.
Electronic Colloquium on Computational Complexity (ECCC) 15(037): (2008) |
| 100 | EE | Jack H. Lutz:
A Divergence Formula for Randomness and Dimension.
Electronic Colloquium on Computational Complexity (ECCC) 15(106): (2008) |
| 99 | EE | Jack H. Lutz,
Klaus Weihrauch:
Connectivity properties of dimension level sets.
Math. Log. Q. 54(5): 483-491 (2008) |
| 98 | EE | Jack H. Lutz,
Elvira Mayordomo:
Dimensions of Points in Self-Similar Fractals.
SIAM J. Comput. 38(3): 1080-1112 (2008) |
| 2007 |
|---|
| 97 | EE | James I. Lathrop,
Jack H. Lutz,
Scott M. Summers:
Strict Self-assembly of Discrete Sierpinski Triangles.
CiE 2007: 455-464 |
| 96 | EE | John M. Hitchcock,
Jack H. Lutz,
Sebastiaan Terwijn:
The arithmetical complexity of dimension and randomness.
ACM Trans. Comput. Log. 8(2): (2007) |
| 95 | EE | Xiaoyang Gu,
Jack H. Lutz:
Dimension and Relative Frequencies
CoRR abs/cs/0703085: (2007) |
| 94 | EE | David Doty,
Jack H. Lutz,
Satyadev Nandakumar:
Finite-state dimension and real arithmetic.
Inf. Comput. 205(11): 1640-1651 (2007) |
| 93 | EE | Xiaoyang Gu,
Jack H. Lutz,
Philippe Moser:
Dimensions of Copeland-Erdös sequences.
Inf. Comput. 205(9): 1317-1333 (2007) |
| 92 | EE | Krishna B. Athreya,
John M. Hitchcock,
Jack H. Lutz,
Elvira Mayordomo:
Effective Strong Dimension in Algorithmic Information and Computational Complexity.
SIAM J. Comput. 37(3): 671-705 (2007) |
| 2006 |
|---|
| 91 | EE | Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo:
Points on Computable Curves.
FOCS 2006: 469-474 |
| 90 | EE | David Doty,
Jack H. Lutz,
Satyadev Nandakumar:
Finite-State Dimension and Real Arithmetic.
ICALP (1) 2006: 537-547 |
| 89 | EE | Xiaoyang Gu,
Jack H. Lutz:
Dimension Characterizations of Complexity Classes.
MFCS 2006: 471-479 |
| 88 | EE | David Doty,
Jack H. Lutz,
Satyadev Nandakumar:
Finite-State Dimension and Real Arithmetic
CoRR abs/cs/0602032: (2006) |
| 87 | EE | David Doty,
Jack H. Lutz,
Satyadev Nandakumar:
Finite-State Dimension and Real Arithmetic.
Electronic Colloquium on Computational Complexity (ECCC) 13(038): (2006) |
| 86 | EE | John M. Hitchcock,
Jack H. Lutz:
Why Computational Complexity Requires Stricter Martingales.
Theory Comput. Syst. 39(2): 277-296 (2006) |
| 2005 |
|---|
| 85 | EE | Jack H. Lutz:
The Dimension of a Point: Computability Meets Fractal Geometry.
CiE 2005: 299-299 |
| 84 | EE | Xiaoyang Gu,
Jack H. Lutz,
Philippe Moser:
Dimensions of Copeland-Erdös Sequences.
FSTTCS 2005: 250-260 |
| 83 | EE | David Doty,
Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo,
Philippe Moser:
Zeta-Dimension.
MFCS 2005: 283-294 |
| 82 | EE | David Doty,
Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo,
Philippe Moser:
Zeta-Dimension
CoRR abs/cs/0503052: (2005) |
| 81 | EE | Xiaoyang Gu,
Jack H. Lutz,
Philippe Moser:
Dimensions of Copeland-Erdos Sequences
CoRR abs/cs/0508001: (2005) |
| 80 | EE | Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo:
Points on Computable Curves
CoRR abs/cs/0512042: (2005) |
| 79 | EE | Xiaoyang Gu,
Jack H. Lutz,
Philippe Moser:
Dimensions of Copeland-Erdös Sequences
Electronic Colloquium on Computational Complexity (ECCC)(089): (2005) |
| 78 | EE | Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo:
Points on Computable Curves
Electronic Colloquium on Computational Complexity (ECCC)(157): (2005) |
| 77 | EE | Xiaoyang Gu,
Jack H. Lutz:
Dimension Characterizations of Complexity Classes
Electronic Colloquium on Computational Complexity (ECCC)(160): (2005) |
| 76 | EE | Stephen A. Fenner,
Jack H. Lutz,
Elvira Mayordomo,
Patrick Reardon:
Weakly useful sequences.
Inf. Comput. 197(1-2): 41-54 (2005) |
| 75 | EE | Lance Fortnow,
Jack H. Lutz:
Prediction and dimension.
J. Comput. Syst. Sci. 70(4): 570-589 (2005) |
| 74 | EE | Jack H. Lutz:
Effective fractal dimensions.
Math. Log. Q. 51(1): 62-72 (2005) |
| 2004 |
|---|
| 73 | EE | Krishna B. Athreya,
John M. Hitchcock,
Jack H. Lutz,
Elvira Mayordomo:
Effective Strong Dimension in Algorithmic Information and Computational Complexity.
STACS 2004: 632-643 |
| 72 | EE | John M. Hitchcock,
Jack H. Lutz,
Sebastiaan Terwijn:
The Arithmetical Complexity of Dimension and Randomness
CoRR cs.LO/0408043: (2004) |
| 71 | EE | John M. Hitchcock,
Jack H. Lutz,
Sebastiaan Terwijn:
The Arithmetical Complexity of Dimension and Randomness
Electronic Colloquium on Computational Complexity (ECCC)(079): (2004) |
| 70 | EE | Jack H. Lutz:
Computability versus exact computability of martingales.
Inf. Process. Lett. 92(5): 235-237 (2004) |
| 69 | EE | John M. Hitchcock,
Jack H. Lutz,
Elvira Mayordomo:
Scaled dimension and nonuniform complexity.
J. Comput. Syst. Sci. 69(2): 97-122 (2004) |
| 68 | EE | Josef M. Breutzmann,
David W. Juedes,
Jack H. Lutz:
Baire category and nowhere differentiability for feasible real functions.
Math. Log. Q. 50(4-5): 460-472 (2004) |
| 67 | EE | Jack Jie Dai,
James I. Lathrop,
Jack H. Lutz,
Elvira Mayordomo:
Finite-state dimension.
Theor. Comput. Sci. 310(1-3): 1-33 (2004) |
| 2003 |
|---|
| 66 | EE | John M. Hitchcock,
Jack H. Lutz,
Sebastiaan Terwijn:
The Arithmetical Complexity of Dimension and Randomness.
CSL 2003: 241-254 |
| 65 | EE | John M. Hitchcock,
Jack H. Lutz,
Elvira Mayordomo:
Scaled Dimension and Nonuniform Complexity.
ICALP 2003: 278-290 |
| 64 | EE | Jack H. Lutz:
The dimensions of individual strings and sequences.
Inf. Comput. 187(1): 49-79 (2003) |
| 63 | EE | Jack H. Lutz:
Dimension in Complexity Classes.
SIAM J. Comput. 32(5): 1236-1259 (2003) |
| 2002 |
|---|
| 62 | EE | Lance Fortnow,
Jack H. Lutz:
Prediction and Dimension.
COLT 2002: 380-395 |
| 61 | EE | John M. Hitchcock,
Jack H. Lutz:
Why Computational Complexity Requires Stricter Martingales.
ICALP 2002: 549-560 |
| 60 | EE | Jack H. Lutz:
Dimension in Complexity Classes
CoRR cs.CC/0203016: (2002) |
| 59 | EE | Jack H. Lutz:
The Dimensions of Individual Strings and Sequences
CoRR cs.CC/0203017: (2002) |
| 58 | EE | Krishna B. Athreya,
John M. Hitchcock,
Jack H. Lutz,
Elvira Mayordomo:
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
CoRR cs.CC/0211025: (2002) |
| 2001 |
|---|
| 57 | EE | Jack Jie Dai,
James I. Lathrop,
Jack H. Lutz,
Elvira Mayordomo:
Finite-State Dimension.
ICALP 2001: 1028-1039 |
| 56 | EE | Josef M. Breutzmann,
David W. Juedes,
Jack H. Lutz:
Baire Category and Nowhere Differentiability for Feasible Real Functions.
ISAAC 2001: 219-230 |
| 55 | | Jack H. Lutz,
Elvira Mayordomo:
Twelve Problems in Resource-Bounded Measure.
Current Trends in Theoretical Computer Science 2001: 83-101 |
| 2000 |
|---|
| 54 | EE | Jack H. Lutz:
Gales and the Constructive Dimension of Individual Sequences.
ICALP 2000: 902-913 |
| 53 | EE | Jack H. Lutz:
Dimension in Complexity Classes.
IEEE Conference on Computational Complexity 2000: 158-169 |
| 52 | EE | Jack H. Lutz,
Vikram Mhetre,
Sridhar Srinivasan:
Hard Instances of Hard Problems.
STACS 2000: 324-333 |
| 51 | EE | Jack H. Lutz,
Martin Strauss:
Bias Invariance of Small Upper Spans.
STACS 2000: 74-86 |
| 50 | EE | Jack H. Lutz,
Yong Zhao:
The Density of Weakly Complete Problems under Adaptive Reductions.
SIAM J. Comput. 30(4): 1197-1210 (2000) |
| 49 | EE | David W. Juedes,
Jack H. Lutz:
Modeling Time-Bounded Prefix Kolmogorov Complexity.
Theory Comput. Syst. 33(2): 111-123 (2000) |
| 1999 |
|---|
| 48 | EE | Jack Jie Dai,
Jack H. Lutz:
Query Order and NP-Completeness.
IEEE Conference on Computational Complexity 1999: 142-148 |
| 47 | | Jack H. Lutz,
Elvira Mayordomo:
Twelve Problems in Resource-Bounded Measure.
Bulletin of the EATCS 68: 64-80 (1999) |
| 46 | | James I. Lathrop,
Jack H. Lutz:
Recursive Computational Depth.
Inf. Comput. 153(1): 139-172 (1999) |
| 45 | | Josef M. Breutzmann,
Jack H. Lutz:
Equivalence of Measures of Complexity Classes.
SIAM J. Comput. 29(1): 302-326 (1999) |
| 44 | EE | Jack H. Lutz,
David L. Schweizer:
Feasible Reductions to Kolmogorov-Loveland Stochastic Sequences.
Theor. Comput. Sci. 225(1-2): 185-194 (1999) |
| 1998 |
|---|
| 43 | EE | Jack H. Lutz:
Resource-Bounded Measure.
IEEE Conference on Computational Complexity 1998: 236-248 |
| 42 | EE | Amy K. Lorentz,
Jack H. Lutz:
Genericity and Randomness over Feasible Probability Measures.
Theor. Comput. Sci. 207(1): 245-259 (1998) |
| 1997 |
|---|
| 41 | | Amy K. Lorentz,
Jack H. Lutz:
Genericity and Randomness over Feasible Probability Measures.
Advances in Algorithms, Languages, and Complexity 1997: 171-187 |
| 40 | | James I. Lathrop,
Jack H. Lutz:
Recursive Computational Depth.
ICALP 1997: 132-142 |
| 39 | EE | Jack H. Lutz,
Yong Zhao:
The Density of Weakly Complete Problems under Adaptive Reductions.
IEEE Conference on Computational Complexity 1997: 111-120 |
| 38 | | Josef M. Breutzmann,
Jack H. Lutz:
Equivalence of Measures of Complexity Classes.
STACS 1997: 535-545 |
| 37 | | Jack H. Lutz:
Report on the Workshop on Languages, Algorithms and Complexity, Minneapolis, USA, 12 April 1997.
Bulletin of the EATCS 62: (1997) |
| 36 | | Jack H. Lutz:
Observations on Measure and Lowness for \Delta^p_2.
Theory Comput. Syst. 30(4): 429-442 (1997) |
| 1996 |
|---|
| 35 | | Jack H. Lutz:
Observations on Measure and Lowness for Delta^P_2.
STACS 1996: 87-97 |
| 34 | | David W. Juedes,
Jack H. Lutz:
Completeness and Weak Completeness Under Polynomial-Size Circuits.
Inf. Comput. 125(1): 13-31 (1996) |
| 33 | EE | Jack H. Lutz,
Elvira Mayordomo:
Cook Versus Karp-Levin: Separating Completeness Notions if NP is not Small.
Theor. Comput. Sci. 164(1&2): 141-163 (1996) |
| 1995 |
|---|
| 32 | | Stephen A. Fenner,
Jack H. Lutz,
Elvira Mayordomo:
Weakly Useful Sequences.
ICALP 1995: 393-404 |
| 31 | | David W. Juedes,
Jack H. Lutz:
Completeness and Weak Completeness Under Polynomial-Size Circuits.
STACS 1995: 26-37 |
| 30 | | Jack H. Lutz:
A Small Span Theorem for P/Poly-Turing Reductions.
Structure in Complexity Theory Conference 1995: 324-330 |
| 29 | | Ronald V. Book,
Jack H. Lutz,
David M. Martin Jr.:
The Global Power of Additional Queries to Random Oracles
Inf. Comput. 120(1): 49-54 (1995) |
| 28 | | David W. Juedes,
Jack H. Lutz:
The Complexity and Distribution of Hard Problems.
SIAM J. Comput. 24(2): 279-295 (1995) |
| 27 | | Jack H. Lutz:
Weakly Hard Problems.
SIAM J. Comput. 24(6): 1170-1189 (1995) |
| 26 | EE | David W. Juedes,
Jack H. Lutz:
Weak Completeness in E and E_2.
Theor. Comput. Sci. 143(1): 149-158 (1995) |
| 1994 |
|---|
| 25 | | Ronald V. Book,
Jack H. Lutz,
David M. Martin Jr.:
The Global Power of Additional Queries to Random Oracles.
STACS 1994: 403-414 |
| 24 | | Jack H. Lutz,
Elvira Mayordomo:
Cook Versus Karp-Levin: Separating Completeness Notions if NP Is not Small (Extended Abstract).
STACS 1994: 415-426 |
| 23 | | Jack H. Lutz:
Weakly Hard Problems.
Structure in Complexity Theory Conference 1994: 146-161 |
| 22 | | Ronald V. Book,
Jack H. Lutz,
Klaus W. Wagner:
An Observation on Probability Versus Randomness with Applications to Complexity Classes.
Mathematical Systems Theory 27(3): 201-209 (1994) |
| 21 | | Jack H. Lutz,
Elvira Mayordomo:
Measure, Stochasticity, and the Density of Hard Languages.
SIAM J. Comput. 23(4): 762-779 (1994) |
| 20 | | David W. Juedes,
James I. Lathrop,
Jack H. Lutz:
Computational Depth and Reducibility.
Theor. Comput. Sci. 132(2): 37-70 (1994) |
| 1993 |
|---|
| 19 | | David W. Juedes,
Jack H. Lutz:
The Complexity and Distribution of Hard Problems (Extended Abstract)
FOCS 1993: 177-185 |
| 18 | | David W. Juedes,
James I. Lathrop,
Jack H. Lutz:
Computational Depth and Reducibility (Extended Abstract).
ICALP 1993: 277-288 |
| 17 | | Jack H. Lutz,
Elvira Mayordomo:
Measure, Stochasticity, and the Density of Hard Languages.
STACS 1993: 38-47 |
| 16 | | Jack H. Lutz:
The Quantitative Structure of Exponential Time.
Structure in Complexity Theory Conference 1993: 158-175 |
| 15 | | Ronald V. Book,
Jack H. Lutz:
On Languages With Very High Space-Bounded Kolmogorov Complexity.
SIAM J. Comput. 22(2): 395-402 (1993) |
| 14 | | Jack H. Lutz:
A Pseudorandom Oracle Characterization of BPP.
SIAM J. Comput. 22(5): 1075-1086 (1993) |
| 13 | | Jack H. Lutz,
William J. Schmidt:
Circuit Size Relative to Pseudorandom Oracles.
Theor. Comput. Sci. 107(1): 95-120 (1993) |
| 1992 |
|---|
| 12 | | Ronald V. Book,
Jack H. Lutz,
Klaus W. Wagner:
On Complexity Classes and Algorithmically Random Languages (Extended Abstract).
STACS 1992: 319-328 |
| 11 | | Ronald V. Book,
Jack H. Lutz:
On Languages with Very High Information Content.
Structure in Complexity Theory Conference 1992: 255-259 |
| 10 | | Jack H. Lutz:
Almost Everywhere High Nonuniform Complexity.
J. Comput. Syst. Sci. 44(2): 220-258 (1992) |
| 9 | | Jack H. Lutz:
On Independent Random Oracles.
Theor. Comput. Sci. 92(2): 301-307 (1992) |
| 1991 |
|---|
| 8 | | Jack H. Lutz:
A Pseudorandom Oracle Characterization of BPP.
Structure in Complexity Theory Conference 1991: 190-195 |
| 7 | | Jack H. Lutz,
William J. Schmidt:
Errata for Circuit Size to Pseudorandom Oracles.
Structure in Complexity Theory Conference 1991: 392 |
| 6 | | Jack H. Lutz:
An Upward Measure Separation Theorem.
Theor. Comput. Sci. 81(1): 127-135 (1991) |
| 1990 |
|---|
| 5 | | Ronald V. Book,
Jack H. Lutz,
Shouwen Tang:
Additional Queries to Random and Pseudorandom Oracles.
ICALP 1990: 283-293 |
| 4 | | Jack H. Lutz,
William J. Schmidt:
Circuit Size Relative to Pseudorandom Oracles.
Structure in Complexity Theory Conference 1990: 268-286 |
| 3 | | Jack H. Lutz:
Pseudorandom Sources for BPP.
J. Comput. Syst. Sci. 41(3): 307-320 (1990) |
| 2 | | Jack H. Lutz:
Category and Measure in Complexity Classes.
SIAM J. Comput. 19(6): 1100-1131 (1990) |
| 1989 |
|---|
| 1 | | Jack H. Lutz:
Almost Everywhere High Nonuniform Complexity.
Structure in Complexity Theory Conference 1989: 37-53 |
