Jack H. Lutz

Inf. Comput., October, 2023

Dimension and the Structure of Complexity Classes.

[BibT_eX]

[DOI]

Theory Comput. Syst., June, 2023

A Weyl Criterion for Finite-State Dimension and Applications.

[BibT_eX]

[DOI]

Satyadev Nandakumar

Subin Pulari

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

Finite-State Mutual Dimension.

[BibT_eX]

[DOI]

Proceedings of the 58th Annual Allerton Conference on Communication, 2022

2021

Asymptotic Divergences and Strong Dichotomy.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Computing absolutely normal numbers in nearly linear time.

[BibT_eX]

[DOI]

Inf. Comput., 2021

A Weyl Criterion for Finite-State Dimension.

[BibT_eX]

[DOI]

Satyadev Nandakumar

Subin Pulari

CoRR, 2021

The Point-to-Set Principle, the Continuum Hypothesis, and the Dimensions of Hamel Bases.

[BibT_eX]

[DOI]

CoRR, 2021

2020

Robust biomolecular finite automata.

[BibT_eX]

[DOI]

Titus H. Klinge

Theor. Comput. Sci., 2020

Algorithmic Fractal Dimensions in Geometric Measure Theory.

[BibT_eX]

[DOI]

CoRR, 2020

Algorithmically Optimal Outer Measures.

[BibT_eX]

[DOI]

CoRR, 2020

The Dimensions of Hyperspaces.

[BibT_eX]

[DOI]

CoRR, 2020

Nonregularity via Ordinal Extensions.

[BibT_eX]

[DOI]

Giora Slutzki

CoRR, 2020

Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on DNA Computing and Molecular Programming, 2020

Who Asked Us? How the Theory of Computing Answers Questions about Analysis.

[BibT_eX]

[DOI]

Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

2019

Runtime Fault Detection in Programmed Molecular Systems.

[BibT_eX]

[DOI]

ACM Trans. Softw. Eng. Methodol., 2019

Real-time computability of real numbers by chemical reaction networks.

[BibT_eX]

[DOI]

Nat. Comput., 2019

Quorum Sensing and Verification in Chemical Reaction Networks.

[BibT_eX]

[DOI]

CoRR, 2019

Robustness and games against nature in molecular programming.

[BibT_eX]

[DOI]

Proceedings of the 41st International Conference on Software Engineering: New Ideas and Emerging Results, 2019

Algorithmic Randomness in Continuous-Time Markov Chains.

[BibT_eX]

[DOI]

Xiang Huang

Andrei N. Migunov

Proceedings of the 57th Annual Allerton Conference on Communication, 2019

2018

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Mutual dimension and random sequences.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Writing Requirements for Molecular Programs.

[BibT_eX]

[DOI]

Robyn R. Lutz

Proceedings of the 26th IEEE International Requirements Engineering Conference, 2018

2017

Runtime Fault Detection in Programmed Molecular Systems.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Software engineering for molecular programming.

[BibT_eX]

[DOI]

Robyn R. Lutz

Proceedings of the 38th International Conference on Software Engineering, 2016

2015

Reachability Problems for Continuous Chemical Reaction Networks.

[BibT_eX]

[DOI]

Donald M. Stull

Electron. Colloquium Comput. Complex., 2015

Algorithmic information and plane Kakeya sets.

[BibT_eX]

[DOI]

CoRR, 2015

2014

The frequent paucity of trivial strings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Lines Missing Every Random Point.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Mutual Dimension.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Dimension spectra of random subfractals of self-similar fractals.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2014

Automated requirements analysis for a molecular watchdog timer.

[BibT_eX]

[DOI]

Proceedings of the ACM/IEEE International Conference on Automated Software Engineering, 2014

2012

Inseparability and Strong Hypotheses for Disjoint NP Pairs.

[BibT_eX]

[DOI]

Lance Fortnow

Theory Comput. Syst., 2012

Translating the Cantor set by a random

[BibT_eX]

[DOI]

CoRR, 2012

Reasoning As Though.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation and Natural Computation, 2012

Requirements analysis for a product family of DNA nanodevices.

[BibT_eX]

[DOI]

Proceedings of the 2012 20th IEEE International Requirements Engineering Conference (RE), 2012

The Computer Science of DNA Nanotechnology.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2012

Engineering and verifying requirements for programmable self-assembling nanomachines.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Software Engineering, 2012

The Tile Assembly Model is Intrinsically Universal.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

A divergence formula for randomness and dimension.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Effective dimensions and relative frequencies.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

The Computer Science of Molecular Programming.

[BibT_eX]

[DOI]

Proceedings of the DNA Computing and Molecular Programming - 17th International Conference, 2011

Multi-Resolution Cellular Automata for Real Computation.

[BibT_eX]

[DOI]

Brian Patterson

Proceedings of the Models of Computation in Context, 2011

Axiomatizing Resource Bounds for Measure.

[BibT_eX]

[DOI]

Proceedings of the Models of Computation in Context, 2011

2010

Approximate Self-Assembly of the Sierpinski Triangle.

[BibT_eX]

[DOI]

Brad Shutters

Electron. Colloquium Comput. Complex., 2010

Intrinsic Universality in Self-Assembly.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Strict self-assembly of discrete Sierpinski triangles.

[BibT_eX]

[DOI]

Scott M. Summers

Theor. Comput. Sci., 2009

Inseparability and Strong Hypotheses for Disjoint NP Pairs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Random Number Selection in Self-assembly.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation, 8th International Conference, 2009

2008

Dimensions of Points in Self-Similar Fractals.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Computability and Complexity in Self-Assembly.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Curves That Must Be Retraced.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

A Divergence Formula for Randomness and Dimension (Short Version)

[BibT_eX]

[DOI]

Proceedings of the Proceedings International Workshop on The Complexity of Simple Programs, 2008

Dimension Characterizations of Complexity Classes.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Complexes of on-line self assembly.

[BibT_eX]

[DOI]

Proceedings of the 2008 IEEE International Conference on Electro/Information Technology, 2008

2007

The arithmetical complexity of dimension and randomness.

[BibT_eX]

[DOI]

John M. Hitchcock

Sebastiaan Terwijn

ACM Trans. Comput. Log., 2007

Effective Strong Dimension in Algorithmic Information and Computational Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Connectivity Properties of Dimension Level Sets.

[BibT_eX]

[DOI]

Klaus Weihrauch

Proceedings of the Fourth International Conference on Computability and Complexity in Analysis, 2007

Dimension and Relative Frequencies

[BibT_eX]

[DOI]

CoRR, 2007

2006

Why Computational Complexity Requires Stricter Martingales.

[BibT_eX]

[DOI]

John M. Hitchcock

Theory Comput. Syst., 2006

Finite-State Dimension and Real Arithmetic.

[BibT_eX]

[DOI]

David Doty

Satyadev Nandakumar

Electron. Colloquium Comput. Complex., 2006

2005

Effective fractal dimensions.

[BibT_eX]

[DOI]

Math. Log. Q., 2005

Prediction and dimension.

[BibT_eX]

[DOI]

Lance Fortnow

J. Comput. Syst. Sci., 2005

Weakly useful sequences.

[BibT_eX]

[DOI]

Inf. Comput., 2005

Points on Computable Curves

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Dimensions of Copeland-Erdös Sequences

[BibT_eX]

[DOI]

Philippe Moser

Electron. Colloquium Comput. Complex., 2005

Zeta-Dimension.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

The Dimension of a Point: Computability Meets Fractal Geometry.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

2004

Finite-state dimension.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Baire category and nowhere differentiability for feasible real functions.

[BibT_eX]

[DOI]

Josef M. Breutzmann

Math. Log. Q., 2004

Scaled dimension and nonuniform complexity.

[BibT_eX]

[DOI]

John M. Hitchcock

J. Comput. Syst. Sci., 2004

Computability versus exact computability of martingales.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

2003

Dimension in Complexity Classes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

The dimensions of individual strings and sequences.

[BibT_eX]

[DOI]

Inf. Comput., 2003

2001

Twelve Problems in Resource-Bounded Measure.

[BibT_eX]

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

The Density of Weakly Complete Problems under Adaptive Reductions.

[BibT_eX]

[DOI]

Yong Zhao

SIAM J. Comput., 2000

Modeling Time-Bounded Prefix Kolmogorov Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2000

Bias Invariance of Small Upper Spans.

[BibT_eX]

[DOI]

Martin Strauss

Proceedings of the STACS 2000, 2000

Hard Instances of Hard Problems.

[BibT_eX]

[DOI]

Vikram Mhetre

Sridhar Srinivasan

Proceedings of the STACS 2000, 2000

Gales and the Constructive Dimension of Individual Sequences.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Feasible Reductions to Kolmogorov-Loveland Stochastic Sequences.

[BibT_eX]

[DOI]

David L. Schweizer

Theor. Comput. Sci., 1999

Equivalence of Measures of Complexity Classes.

[BibT_eX]

[DOI]

Josef M. Breutzmann

SIAM J. Comput., 1999

Recursive Computational Depth.

[BibT_eX]

[DOI]

Inf. Comput., 1999

Twelve Problems in Resource-Bounded Measure.

[BibT_eX]

Bull. EATCS, 1999

Query Order and NP-Completeness.

[BibT_eX]

[DOI]

Jack Jie Dai

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Genericity and Randomness over Feasible Probability Measures.

[BibT_eX]

[DOI]

Amy K. Lorentz

Theor. Comput. Sci., 1998

Resource-Bounded Measure.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Observations on Measure and Lowness for \Delta^p_2.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1997

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

[BibT_eX]

Bull. EATCS, 1997

1996

Cook Versus Karp-Levin: Separating Completeness Notions if NP is not Small.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Completeness and Weak Completeness Under Polynomial-Size Circuits.

[BibT_eX]

[DOI]

Inf. Comput., 1996

1995

The Global Power of Additional Queries to Random Oracles

[BibT_eX]

[DOI]

David M. Martin Jr.

Inf. Comput., July, 1995

Weak Completeness in E and E_2.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Weakly Hard Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

The Complexity and Distribution of Hard Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

Weakly Useful Sequences.

[BibT_eX]

[DOI]

Stephen A. Fenner

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

A Small Span Theorem for P/Poly-Turing Reductions.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Computational Depth and Reducibility.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Measure, Stochasticity, and the Density of Hard Languages.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

An Observation on Probability Versus Randomness with Applications to Complexity Classes.

[BibT_eX]

[DOI]

Klaus W. Wagner

Math. Syst. Theory, 1994

Cook Versus Karp-Levin: Separating Completeness Notions if NP Is not Small (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the STACS 94, 1994

1993

Circuit Size Relative to Pseudorandom Oracles.

[BibT_eX]

[DOI]

William J. Schmidt

Theor. Comput. Sci., 1993

A Pseudorandom Oracle Characterization of BPP.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

On Languages With Very High Space-Bounded Kolmogorov Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

Computational Depth and Reducibility (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

The Complexity and Distribution of Hard Problems (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

The Quantitative Structure of Exponential Time.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On Independent Random Oracles.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Almost Everywhere High Nonuniform Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

On Complexity Classes and Algorithmically Random Languages (Extended Abstract).

[BibT_eX]

[DOI]

Klaus W. Wagner

Proceedings of the STACS 92, 1992

On Languages with Very High Information Content.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

An Upward Measure Separation Theorem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

Errata for Circuit Size to Pseudorandom Oracles.

[BibT_eX]

[DOI]

William J. Schmidt

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Category and Measure in Complexity Classes.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Pseudorandom Sources for BPP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1990

Additional Queries to Random and Pseudorandom Oracles.

[BibT_eX]

[DOI]

Shouwen Tang

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1987

Resource bounded baire category and small circuits in exponential space.

[BibT_eX]

[DOI]