| Publication | Date of Publication | Type |
|---|
Robustness for space-bounded statistical zero knowledge
| 2025-01-14 | Paper |
Kolmogorov complexity characterizes statistical zero knowledge
| 2024-09-25 | Paper |
Circuit complexity before the dawn of the new millennium
| 2024-07-05 | Paper |
scientific article; zbMATH DE number 7799585 (Why is no real title available?)
| 2024-02-05 | Paper |
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
Lecture Notes in Computer Science | 2024-01-29 | Paper |
Cryptographic hardness under projections for time-bounded Kolmogorov complexity
| 2024-01-15 | Paper |
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
Computability | 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
Theoretical Computer Science | 2023-04-20 | Paper |
scientific article; zbMATH DE number 7650083 (Why is no real title available?)
| 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
Acta Informatica | 2022-08-30 | Paper |
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
New Zealand Journal of Mathematics | 2021-09-28 | Paper |
The non-hardness of approximating circuit size
Theory of Computing Systems | 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
Complexity and Approximation | 2020-07-20 | Paper |
Better complexity bounds for cost register automata
| 2020-05-26 | Paper |
scientific article; zbMATH DE number 7204388 (Why is no real title available?)
| 2020-05-26 | Paper |
New insights on the (non-)hardness of circuit minimization and related problems
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
The non-hardness of approximating circuit size
Computer Science – Theory and Applications | 2019-10-22 | Paper |
Better complexity bounds for cost register automata
Theory of Computing Systems | 2019-06-27 | Paper |
Complexity of regular functions
Journal of Computer and System Sciences | 2019-06-25 | Paper |
Minimum circuit size, graph isomorphism, and related problems
SIAM Journal on Computing | 2018-07-19 | Paper |
The minimum oracle circuit size problem
Computational Complexity | 2017-10-18 | Paper |
Dual VP classes
Computational Complexity | 2017-10-18 | Paper |
Zero knowledge and circuit minimization
Information and Computation | 2017-09-28 | Paper |
The Complexity of Complexity
Computability and Complexity | 2017-04-04 | Paper |
The Minimum Oracle Circuit Size Problem.
| 2017-01-24 | Paper |
Investigations concerning the structure of complete sets
Perspectives in Computational Complexity | 2016-09-22 | Paper |
Complexity of Regular Functions
Language and Automata Theory and Applications | 2016-04-08 | Paper |
On the power of algebraic branching programs of width two
Computational Complexity | 2016-03-21 | Paper |
Complexity of finite-horizon Markov decision process problems
Journal of the ACM | 2015-12-17 | Paper |
Dual VP classes
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
Uniform derandomization from pathetic lower bounds
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2015-08-21 | Paper |
Depth reduction for noncommutative arithmetic circuits
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Width-parametrized SAT: time-space tradeoffs
Theory of Computing | 2015-02-03 | Paper |
Low-depth uniform threshold circuits and the bit-complexity of straight line programs
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Zero knowledge and circuit minimization
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
scientific article; zbMATH DE number 6351511 (Why is no real title available?)
Theory of Computing | 2014-10-06 | Paper |
Reductions to the set of random strings: the resource-bounded case
Logical Methods in Computer Science | 2014-09-05 | Paper |
Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic
Chicago Journal of Theoretical Computer Science | 2014-05-07 | Paper |
Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication
Journal of Computer and System Sciences | 2013-12-13 | Paper |
Comments on ``Arithmetic complexity, Kleene closure, and formal power series
Theory of Computing Systems | 2013-10-21 | Paper |
NL-printable sets and nondeterministic Kolmogorov complexity
Electronic Notes in Theoretical Computer Science | 2013-06-06 | Paper |
Limits on the computational power of random strings
Information and Computation | 2013-06-06 | Paper |
Avoiding simplicity is complex
Theory of Computing Systems | 2012-12-07 | Paper |
Reductions to the set of random strings: the resource-bounded case
Lecture Notes in Computer Science | 2012-09-25 | Paper |
Curiouser and curiouser: the link between incompressibility and complexity
Lecture Notes in Computer Science | 2012-08-14 | Paper |
scientific article; zbMATH DE number 6019541 (Why is no real title available?)
| 2012-03-29 | Paper |
On the power of algebraic branching programs of width two
Automata, Languages and Programming | 2011-07-06 | Paper |
Limits on the Computational Power of Random Strings
Automata, Languages and Programming | 2011-07-06 | Paper |
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Uniform Derandomization from Pathetic Lower Bounds
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Avoiding simplicity is complex
Programs, Proofs, Processes | 2010-07-29 | Paper |
Amplifying lower bounds by means of self-reducibility
Journal of the ACM | 2010-07-14 | Paper |
Measure on P: Robustness of the notion
Lecture Notes in Computer Science | 2010-06-17 | Paper |
On the Complexity of Numerical Analysis
SIAM Journal on Computing | 2009-11-06 | Paper |
Planar and grid graph reachability problems
Theory of Computing Systems | 2009-10-19 | Paper |
The complexity of satisfiability problems: Refining Schaefer's theorem
Journal of Computer and System Sciences | 2009-04-30 | Paper |
Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
SIAM Journal on Computing | 2009-03-16 | Paper |
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds
Computer Science – Theory and Applications | 2008-06-05 | Paper |
Reachability Problems: An Update
Lecture Notes in Computer Science | 2007-11-13 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Mathematical Foundations of Computer Science 2005
Lecture Notes in Computer Science | 2006-10-20 | Paper |
Power from Random Strings
SIAM Journal on Computing | 2006-06-01 | Paper |
NL-printable sets and nondeterministic Kolmogorov complexity
Theoretical Computer Science | 2006-04-28 | Paper |
What can be efficiently reduced to the Kolmogorov-random strings?
Annals of Pure and Applied Logic | 2005-12-29 | Paper |
scientific article; zbMATH DE number 2196509 (Why is no real title available?)
| 2005-08-22 | Paper |
scientific article; zbMATH DE number 2156271 (Why is no real title available?)
| 2005-04-15 | Paper |
Complexity of some arithmetic problems for binary polynomials
Computational Complexity | 2004-12-13 | Paper |
The complexity of planarity testing
Information and Computation | 2004-11-23 | Paper |
scientific article; zbMATH DE number 2081089 (Why is no real title available?)
| 2004-08-04 | Paper |
The division breakthroughs
Bulletin of the European Association for Theoretical Computer Science EATCS | 2004-01-15 | Paper |
Arithmetic complexity, Kleene closure, and formal power series
Theory of Computing Systems | 2003-08-26 | Paper |
A lower bound for primality
Journal of Computer and System Sciences | 2003-05-19 | Paper |
Uniform constant-depth threshold circuits for division and iterated multiplication.
Journal of Computer and System Sciences | 2003-05-14 | Paper |
Basic complexity
| 2002-07-22 | Paper |
Reducing the complexity of reductions
Computational Complexity | 2002-05-05 | Paper |
Characterizing small depth and small space classes by operators of higher types
Chicago Journal of Theoretical Computer Science | 2001-05-15 | Paper |
scientific article; zbMATH DE number 1500509 (Why is no real title available?)
| 2001-04-26 | Paper |
On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
Journal of Computer and System Sciences | 2001-03-12 | Paper |
scientific article; zbMATH DE number 1559593 (Why is no real title available?)
| 2001-03-01 | Paper |
scientific article; zbMATH DE number 1860651 (Why is no real title available?)
| 2001-01-01 | Paper |
The complexity of matrix rank and feasible systems of linear equations
Computational Complexity | 2000-12-05 | Paper |
scientific article; zbMATH DE number 1361472 (Why is no real title available?)
| 2000-11-08 | Paper |
scientific article; zbMATH DE number 1335883 (Why is no real title available?)
| 2000-05-04 | Paper |
scientific article; zbMATH DE number 1405642 (Why is no real title available?)
| 2000-04-25 | Paper |
Making Nondeterminism Unambiguous
SIAM Journal on Computing | 2000-03-19 | Paper |
Isolation, matching, and counting uniform and nonuniform upper bounds
Journal of Computer and System Sciences | 2000-03-02 | Paper |
scientific article; zbMATH DE number 1351078 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 1999-10-20 | Paper |
scientific article; zbMATH DE number 1346528 (Why is no real title available?)
| 1999-10-03 | Paper |
Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Journal of Computer and System Sciences | 1999-09-29 | Paper |
scientific article; zbMATH DE number 1256731 (Why is no real title available?)
| 1999-05-18 | Paper |
scientific article; zbMATH DE number 1283991 (Why is no real title available?)
| 1999-05-03 | Paper |
RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
Theory of Computing Systems | 1999-02-18 | Paper |
Non-commutative arithmetic circuits: depth reduction and size lower bounds
Theoretical Computer Science | 1999-01-12 | Paper |
A First-Order Isomorphism Theorem
SIAM Journal on Computing | 1997-05-26 | Paper |
Relationships among $PL$, $\#L$, and the determinant
RAIRO - Theoretical Informatics and Applications | 1996-11-10 | Paper |
scientific article; zbMATH DE number 549851 (Why is no real title available?)
| 1994-12-04 | Paper |
A Uniform Circuit Lower Bound for the Permanent
SIAM Journal on Computing | 1994-11-29 | Paper |
Depth reduction for circuits of unbounded fan-in
Information and Computation | 1994-09-13 | Paper |
Lower bounds for the low hierarchy
Journal of the ACM | 1994-08-21 | Paper |
The complexity of computing maximal word functions
Computational Complexity | 1994-05-08 | Paper |
scientific article; zbMATH DE number 512825 (Why is no real title available?)
| 1994-03-10 | Paper |
Almost-everywhere complexity hierarchies for nondeterministic time
Theoretical Computer Science | 1993-09-16 | Paper |
Relating Equivalence and Reducibility to Sparse Sets
SIAM Journal on Computing | 1993-01-16 | Paper |
Rudimentary reductions revisited
Information Processing Letters | 1992-06-28 | Paper |
scientific article; zbMATH DE number 15884 (Why is no real title available?)
| 1992-06-25 | Paper |
scientific article; zbMATH DE number 8788 (Why is no real title available?)
| 1992-06-25 | Paper |
Limitations of the upward separation technique
Mathematical Systems Theory | 1991-01-01 | Paper |
scientific article; zbMATH DE number 4211971 (Why is no real title available?)
| 1990-01-01 | Paper |
scientific article; zbMATH DE number 4205978 (Why is no real title available?)
| 1990-01-01 | Paper |
Kolmogorov complexity and degrees of tally sets
Information and Computation | 1990-01-01 | Paper |
Some consequences of the existnce of pseudorandom generators
Journal of Computer and System Sciences | 1989-01-01 | Paper |
P-uniform circuit complexity
Journal of the ACM | 1989-01-01 | Paper |
P-Printable Sets
SIAM Journal on Computing | 1988-01-01 | Paper |
Isomorphisms and 1-L reductions
Journal of Computer and System Sciences | 1988-01-01 | Paper |
scientific article; zbMATH DE number 3984573 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3984574 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3960998 (Why is no real title available?)
| 1986-01-01 | Paper |
On the number of cycles possible in digraphs with large girth
Discrete Applied Mathematics | 1985-01-01 | Paper |
Improved lower bounds for the cycle detection problem
Theoretical Computer Science | 1985-01-01 | Paper |
