| Publication | Date of Publication | Type |
|---|
| https://portal.mardi4nfdi.de/entity/Q6187019 | 2024-02-05 | Paper |
| A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) | 2024-01-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6187822 | 2024-01-15 | Paper |
| On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 | 2023-09-13 | Paper |
| Depth-First Search in Directed Planar Graphs, Revisited | 2023-08-08 | Paper |
| Cryptographic hardness under projections for time-bounded Kolmogorov complexity | 2023-04-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875468 | 2023-02-03 | Paper |
| StUSPACE(log n) ⊂-DSPACE(log2 n/log log n) | 2023-01-25 | Paper |
| Depth-first search in directed planar graphs, revisited | 2022-08-30 | Paper |
| Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization | 2021-09-28 | Paper |
| The non-hardness of approximating circuit size | 2021-08-03 | Paper |
| Minimum Circuit Size, Graph Isomorphism, and Related Problems | 2021-06-15 | Paper |
| The new complexity landscape around circuit minimization | 2020-07-27 | Paper |
| Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity | 2020-07-20 | Paper |
| Better complexity bounds for cost register automata | 2020-05-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111269 | 2020-05-26 | Paper |
| New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems | 2019-12-16 | Paper |
| The non-hardness of approximating circuit size | 2019-10-22 | Paper |
| Better complexity bounds for cost register automata | 2019-06-27 | Paper |
| Complexity of regular functions | 2019-06-25 | Paper |
| Minimum Circuit Size, Graph Isomorphism, and Related Problems | 2018-07-19 | Paper |
| The minimum oracle circuit size problem | 2017-10-18 | Paper |
| Dual VP classes | 2017-10-18 | Paper |
| Zero knowledge and circuit minimization | 2017-09-28 | Paper |
| The Complexity of Complexity | 2017-04-04 | Paper |
| The Minimum Oracle Circuit Size Problem. | 2017-01-24 | Paper |
| Investigations Concerning the Structure of Complete Sets | 2016-09-22 | Paper |
| Complexity of Regular Functions | 2016-04-08 | Paper |
| On the power of algebraic branching programs of width two | 2016-03-21 | Paper |
| Complexity of finite-horizon Markov decision process problems | 2015-12-17 | Paper |
| Dual VP Classes | 2015-09-16 | Paper |
| Uniform derandomization from pathetic lower bounds | 2015-08-21 | Paper |
| Depth reduction for noncommutative arithmetic circuits | 2015-05-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5497123 | 2015-02-03 | Paper |
| Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs | 2014-10-14 | Paper |
| Zero Knowledge and Circuit Minimization | 2014-10-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191604 | 2014-10-06 | Paper |
| Reductions to the set of random strings: The resource-bounded case | 2014-09-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5414624 | 2014-05-07 | Paper |
| Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication | 2013-12-13 | Paper |
| Comments on ``Arithmetic complexity, Kleene closure, and formal power series | 2013-10-21 | Paper |
| Limits on the computational power of random strings | 2013-06-06 | Paper |
| NL-printable sets and Nondeterministic Kolmogorov Complexity | 2013-06-06 | Paper |
| Avoiding simplicity is complex | 2012-12-07 | Paper |
| Reductions to the set of random strings: The resource-bounded case | 2012-09-25 | Paper |
| Curiouser and Curiouser: The Link between Incompressibility and Complexity | 2012-08-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3224095 | 2012-03-29 | Paper |
| Limits on the Computational Power of Random Strings | 2011-07-06 | Paper |
| On the Power of Algebraic Branching Programs of Width Two | 2011-07-06 | Paper |
| The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory | 2011-01-18 | Paper |
| Uniform Derandomization from Pathetic Lower Bounds | 2010-09-10 | Paper |
| Avoiding Simplicity Is Complex | 2010-07-29 | Paper |
| Amplifying lower bounds by means of self-reducibility | 2010-07-14 | Paper |
| Measure on P: Robustness of the notion | 2010-06-17 | Paper |
| On the Complexity of Numerical Analysis | 2009-11-06 | Paper |
| Planar and grid graph reachability problems | 2009-10-19 | Paper |
| The complexity of satisfiability problems: Refining Schaefer's theorem | 2009-04-30 | Paper |
| Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table | 2009-03-16 | Paper |
| Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds | 2008-06-05 | Paper |
| Reachability Problems: An Update | 2007-11-13 | Paper |
| STACS 2004 | 2007-10-01 | Paper |
| FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science | 2006-11-14 | Paper |
| Mathematical Foundations of Computer Science 2005 | 2006-10-20 | Paper |
| Power from Random Strings | 2006-06-01 | Paper |
| NL-printable sets and nondeterministic Kolmogorov complexity | 2006-04-28 | Paper |
| What can be efficiently reduced to the Kolmogorov-random strings? | 2005-12-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5465356 | 2005-08-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4668729 | 2005-04-15 | Paper |
| Complexity of some arithmetic problems for binary polynomials | 2004-12-13 | Paper |
| The complexity of planarity testing | 2004-11-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474202 | 2004-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2743685 | 2004-01-15 | Paper |
| Arithmetic complexity, Kleene closure, and formal power series | 2003-08-26 | Paper |
| A lower bound for primality | 2003-05-19 | Paper |
| Uniform constant-depth threshold circuits for division and iterated multiplication. | 2003-05-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2776267 | 2002-07-22 | Paper |
| Reducing the complexity of reductions | 2002-05-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2709238 | 2001-05-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4501524 | 2001-04-26 | Paper |
| On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits | 2001-03-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527042 | 2001-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4790379 | 2001-01-01 | Paper |
| The complexity of matrix rank and feasible systems of linear equations | 2000-12-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4699290 | 2000-11-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258574 | 2000-05-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4938621 | 2000-04-25 | Paper |
| Making Nondeterminism Unambiguous | 2000-03-19 | Paper |
| Isolation, matching, and counting uniform and nonuniform upper bounds | 2000-03-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4267800 | 1999-10-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4266552 | 1999-10-03 | Paper |
| Reductions in circuit complexity: An isomorphism theorem and a gap theorem | 1999-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228466 | 1999-05-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4240333 | 1999-05-03 | Paper |
| RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\) | 1999-02-18 | Paper |
| Non-commutative arithmetic circuits: depth reduction and size lower bounds | 1999-01-12 | Paper |
| A First-Order Isomorphism Theorem | 1997-05-26 | Paper |
| Relationships among $PL$, $\#L$, and the determinant | 1996-11-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4287355 | 1994-12-04 | Paper |
| A Uniform Circuit Lower Bound for the Permanent | 1994-11-29 | Paper |
| Depth reduction for circuits of unbounded fan-in | 1994-09-13 | Paper |
| Lower bounds for the low hierarchy | 1994-08-21 | Paper |
| The complexity of computing maximal word functions | 1994-05-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281518 | 1994-03-10 | Paper |
| Almost-everywhere complexity hierarchies for nondeterministic time | 1993-09-16 | Paper |
| Relating Equivalence and Reducibility to Sparse Sets | 1993-01-16 | Paper |
| Rudimentary reductions revisited | 1992-06-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3971277 | 1992-06-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3972530 | 1992-06-25 | Paper |
| Limitations of the upward separation technique | 1991-01-01 | Paper |
| Kolmogorov complexity and degrees of tally sets | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3355230 | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3360127 | 1990-01-01 | Paper |
| Some consequences of the existnce of pseudorandom generators | 1989-01-01 | Paper |
| P-uniform circuit complexity | 1989-01-01 | Paper |
| Isomorphisms and 1-L reductions | 1988-01-01 | Paper |
| P-Printable Sets | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3730021 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3747725 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3747726 | 1986-01-01 | Paper |
| On the number of cycles possible in digraphs with large girth | 1985-01-01 | Paper |
| Improved lower bounds for the cycle detection problem | 1985-01-01 | Paper |
