Jack H. Lutz

Renrui Qi

Liang Yu

Comput., 2024

Algorithmic Dimensions via Learning Functions.

[BibT_eX]

[DOI]

Andrei N. Migunov

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

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

Extending the Reach of the Point-To-Set Principle.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Finite-State Mutual Dimension.

[BibT_eX]

[DOI]

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

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

Asymptotic Divergences and Strong Dichotomy.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 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

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

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

Real-Time Computability of Real Numbers by Chemical Reaction Networks.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation and Natural Computation, 2017

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016

Reachability Problems for Continuous Chemical Reaction Networks.

[BibT_eX]

[DOI]

Donald M. Stull

Proceedings of the Unconventional Computation and Natural Computation, 2016

Software engineering for molecular programming.

[BibT_eX]

[DOI]

Robyn R. Lutz

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

2015

Algorithmic information and plane Kakeya sets.

[BibT_eX]

[DOI]

CoRR, 2015

Mutual Dimension and Random Sequences.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

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

Lines Missing Every Random Point.

[BibT_eX]

[DOI]

Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe, 2014

2013

The Frequent Paucity of Trivial Strings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Mutual Dimension.

[BibT_eX]

[DOI]

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

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

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

Inseparability and Strong Hypotheses for Disjoint NP Pairs.

[BibT_eX]

[DOI]

Lance Fortnow

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

Intrinsic Universality in Self-Assembly.

[BibT_eX]

[DOI]

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

Approximate Self-assembly of the Sierpinski Triangle.

[BibT_eX]

[DOI]

Brad Shutters

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

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

A Divergence Formula for Randomness and Dimension.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

Curves That Must Be Retraced.

[BibT_eX]

[DOI]

Proceedings of the Sixth International Conference on Computability and Complexity in Analysis, 2009

2008

Connectivity properties of dimension level sets.

[BibT_eX]

[DOI]

Klaus Weihrauch

Math. Log. Q., 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

Complexes of on-line self assembly.

[BibT_eX]

[DOI]

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

Dimensions of Points in Self-similar Fractals.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

Computability and Complexity in Self-assembly.

[BibT_eX]

[DOI]

Proceedings of the Logic and Theory of Algorithms, 2008

Effective Dimensions and Relative Frequencies.

[BibT_eX]

[DOI]

Proceedings of the Logic and Theory of Algorithms, 2008

2007

Dimension and Relative Frequencies

[BibT_eX]

[DOI]

CoRR, 2007

Strict Self-assembly of Discrete Sierpinski Triangles.

[BibT_eX]

[DOI]

Scott M. Summers

Proceedings of the Computation and Logic in the Real World, 2007

2006

Dimension Characterizations of Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Finite-State Dimension and Real Arithmetic.

[BibT_eX]

[DOI]

David Doty

Satyadev Nandakumar

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Points on Computable Curves.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

2005

Effective fractal dimensions.

[BibT_eX]

[DOI]

Math. Log. Q., 2005

Weakly useful sequences.

[BibT_eX]

[DOI]

Inf. Comput., 2005

Zeta-Dimension.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Dimensions of Copeland-Erdös Sequences.

[BibT_eX]

[DOI]

Philippe Moser

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

The Dimension of a Point: Computability Meets Fractal Geometry.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

2004

Computability versus exact computability of martingales.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Effective Strong Dimension in Algorithmic Information and Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

2003

The dimensions of individual strings and sequences.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Scaled Dimension and Nonuniform Complexity.

[BibT_eX]

[DOI]

John M. Hitchcock

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

The Arithmetical Complexity of Dimension and Randomness.

[BibT_eX]

[DOI]

John M. Hitchcock

Sebastiaan Terwijn

Proceedings of the Computer Science Logic, 17th International Workshop, 2003

2002

Why Computational Complexity Requires Stricter Martingales.

[BibT_eX]

[DOI]

John M. Hitchcock

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Prediction and Dimension.

[BibT_eX]

[DOI]

Lance Fortnow

Proceedings of the Computational Learning Theory, 2002

2001

Baire Category and Nowhere Differentiability for Feasible Real Functions.

[BibT_eX]

[DOI]

Josef M. Breutzmann

Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

Finite-State Dimension.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Twelve Problems in Resource-Bounded Measure.

[BibT_eX]

Proceedings of the Current Trends in Theoretical Computer Science, 2001

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

Dimension in Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Feasible Reductions to Kolmogorov-Loveland Stochastic Sequences.

[BibT_eX]

[DOI]

David L. Schweizer

Theor. Comput. Sci., 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

Resource-Bounded Measure.

[BibT_eX]

[DOI]

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

1997

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

[BibT_eX]

Bull. EATCS, 1997

Equivalence of Measures of Complexity Classes.

[BibT_eX]

[DOI]

Josef M. Breutzmann

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

Recursive Computational Depth.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

The Density of Weakly Complete Problems under Adaptive Reductions.

[BibT_eX]

[DOI]

Yong Zhao

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Genericity and Randomness over Feasible Probability Measures.

[BibT_eX]

Amy K. Lorentz

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Observations on Measure and Lowness for Delta^P_2.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

1995

Weak Completeness in E and E_2.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

The Complexity and Distribution of Hard Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

Completeness and Weak Completeness Under Polynomial-Size Circuits.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 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

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

The Global Power of Additional Queries to Random Oracles.

[BibT_eX]

[DOI]

David M. Martin Jr.

Proceedings of the STACS 94, 1994

Weakly Hard Problems.

[BibT_eX]

[DOI]

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

1993

On Languages With Very High Space-Bounded Kolmogorov Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

Measure, Stochasticity, and the Density of Hard Languages.

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 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

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

A Pseudorandom Oracle Characterization of BPP.

[BibT_eX]

[DOI]

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

Additional Queries to Random and Pseudorandom Oracles.

[BibT_eX]

[DOI]

Shouwen Tang

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

Circuit Size Relative to Pseudorandom Oracles.

[BibT_eX]

[DOI]

William J. Schmidt

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Almost Everywhere High Nonuniform Complexity.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Pseudorandom sources for BPP.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Resource bounded baire category and small circuits in exponential space.

[BibT_eX]

[DOI]