| Publication | Date of Publication | Type |
|---|
| Exponential lower bounds for monotone span programs | 2025-08-06 | Paper |
| A survey of classes of primitive recursive functions | 2025-05-25 | Paper |
| Pebbles and branching programs for tree evaluation | 2025-05-25 | Paper |
| A time-space tradeoff for sorting on a general sequential model of computation | 2025-05-25 | Paper |
| Towards a complexity theory of synchronous parallel computation | 2025-05-25 | Paper |
| Feasibly constructive proofs and the propositional calculus (preliminary version) | 2025-05-25 | Paper |
| The relative efficiency of propositional proof systems | 2025-05-25 | Paper |
| Characterizations of pushdown machines in terms of time-bounded computers | 2025-05-25 | Paper |
| The complexity of theorem-proving procedures | 2025-05-25 | Paper |
| The 1982 ACM Turing Award lecture. An overview of computational complexity | 2025-05-25 | Paper |
| Average case lower bounds for monotone switching networks | 2025-05-20 | Paper |
Uniform, Integral, and Feasible Proofs for the Determinant Identities
Journal of the ACM | 2022-12-08 | Paper |
| scientific article; zbMATH DE number 7526282 (Why is no real title available?) | 2022-05-12 | Paper |
| Uniform, integral and efficient proofs for the determinant identities | 2021-01-19 | Paper |
The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy
Distributed Computing | 2020-12-03 | Paper |
| Lower bounds for nondeterministic semantic read-once branching programs | 2017-12-19 | Paper |
The strength of replacement in weak arithmetic
ACM Transactions on Computational Logic | 2017-07-12 | Paper |
| Theories for subexponential-size bounded-depth Frege proofs | 2017-02-02 | Paper |
The complexity of the comparator circuit value problem
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
The importance of the P versus NP question
Journal of the ACM | 2015-12-07 | Paper |
Pebbles and branching programs for tree evaluation
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Complexity theory for operators in analysis
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
The hardness of being private
ACM Transactions on Computation Theory | 2015-09-07 | Paper |
Complexity theory for operators in analysis
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Variations on pushdown machines (Detailed Abstract)
Proceedings of the first annual ACM symposium on Theory of computing - STOC '69 | 2014-03-14 | Paper |
| Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk) | 2012-11-22 | Paper |
| Fractional pebbling and thrifty branching programs | 2012-10-24 | Paper |
| A formal theory for the complexity class associated with the stable marriage problem | 2012-09-18 | Paper |
Formalizing randomized matching algorithms
Logical Methods in Computer Science | 2012-08-15 | Paper |
Formal theories for linear algebra
Logical Methods in Computer Science | 2012-04-03 | Paper |
| scientific article; zbMATH DE number 5787962 (Why is no real title available?) | 2010-09-20 | Paper |
Formal theories for linear algebra
Computer Science Logic | 2010-09-03 | Paper |
Branching Programs for Tree Evaluation
Mathematical Foundations of Computer Science 2009 | 2009-10-16 | Paper |
Consequences of the provability of <i>NP</i> ⊆ <i>P</i>/<i>poly</i>
Journal of Symbolic Logic | 2008-02-25 | Paper |
| Computing over the reals: foundations for scientific computing. | 2006-03-13 | Paper |
Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
Archive for Mathematical Logic | 2005-09-13 | Paper |
| scientific article; zbMATH DE number 2196512 (Why is no real title available?) | 2005-08-22 | Paper |
The proof complexity of linear algebra
Annals of Pure and Applied Logic | 2004-11-18 | Paper |
A second-order system for polytime reasoning based on Grädel's theorem.
Annals of Pure and Applied Logic | 2003-11-25 | Paper |
A Complete Axiomatization for Blocks World
Journal Of Logic And Computation | 2003-11-10 | Paper |
| scientific article; zbMATH DE number 1263206 (Why is no real title available?) | 2002-01-30 | Paper |
| scientific article; zbMATH DE number 1471980 (Why is no real title available?) | 2000-07-09 | Paper |
The relative complexity of NP search problems
Journal of Computer and System Sciences | 1999-09-13 | Paper |
An exponential lower bound for the size of monotone real circuits
Journal of Computer and System Sciences | 1999-05-11 | Paper |
| scientific article; zbMATH DE number 1114018 (Why is no real title available?) | 1998-06-30 | Paper |
| scientific article; zbMATH DE number 1113991 (Why is no real title available?) | 1998-06-02 | Paper |
A tight relationship between generic oracles and type-2 complexity theory
Information and Computation | 1997-10-07 | Paper |
A new Characterization of Type-2 Feasibility
SIAM Journal on Computing | 1996-06-05 | Paper |
| scientific article; zbMATH DE number 619538 (Why is no real title available?) | 1994-09-13 | Paper |
Parallel pointer machines
Computational Complexity | 1994-02-09 | Paper |
Functional interpretations of feasibly constructive arithmetic
Annals of Pure and Applied Logic | 1993-10-13 | Paper |
| scientific article; zbMATH DE number 176200 (Why is no real title available?) | 1993-05-18 | Paper |
| scientific article; zbMATH DE number 176201 (Why is no real title available?) | 1993-05-18 | Paper |
A new recursion-theoretic characterization of the polytime functions
Computational Complexity | 1993-04-01 | Paper |
An Optimal Parallel Algorithm for Formula Evaluation
SIAM Journal on Computing | 1993-01-16 | Paper |
| scientific article; zbMATH DE number 65741 (Why is no real title available?) | 1992-09-27 | Paper |
| scientific article; zbMATH DE number 66471 (Why is no real title available?) | 1992-09-27 | Paper |
A feasibly constructive lower bound for resolution proofs
Information Processing Letters | 1990-01-01 | Paper |
Complexity theory of parallel time and hardware
Information and Computation | 1989-01-01 | Paper |
Two Applications of Inductive Counting for Complementation Problems
SIAM Journal on Computing | 1989-01-01 | Paper |
Short propositional formulas represent nondeterministic computations
Information Processing Letters | 1988-01-01 | Paper |
Problems complete for deterministic logarithmic space
Journal of Algorithms | 1987-01-01 | Paper |
The Parallel Complexity of Abelian Permutation Group Problems
SIAM Journal on Computing | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4009816 (Why is no real title available?) | 1987-01-01 | Paper |
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
SIAM Journal on Computing | 1986-01-01 | Paper |
Log Depth Circuits for Division and Related Problems
SIAM Journal on Computing | 1986-01-01 | Paper |
A taxonomy of problems with fast parallel algorithms
Information and Control | 1985-01-01 | Paper |
A Depth-Universal Circuit
SIAM Journal on Computing | 1985-01-01 | Paper |
An overview of computational complexity
Communications of the ACM | 1983-01-01 | Paper |
The recognition of deterministic CFLs in small time and space
Information and Control | 1983-01-01 | Paper |
Parallel computation for well-endowed rings and space-bounded probabilistic machines
Information and Control | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3841223 (Why is no real title available?) | 1983-01-01 | Paper |
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
SIAM Journal on Computing | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3761405 (Why is no real title available?) | 1982-01-01 | Paper |
Corrigendum: Soundness and Completeness of an Axiom System for Program Verification
SIAM Journal on Computing | 1981-01-01 | Paper |
Towards a complexity theory of synchronous parallel computation
L'Enseignement Mathématique. 2e Série | 1981-01-01 | Paper |
Space Lower Bounds for Maze Threadability on Restricted Machines
SIAM Journal on Computing | 1980-01-01 | Paper |
The relative efficiency of propositional proof systems
Journal of Symbolic Logic | 1979-01-01 | Paper |
Soundness and Completeness of an Axiom System for Program Verification
SIAM Journal on Computing | 1978-01-01 | Paper |
On the Number of Additions to Compute Specific Polynomials
SIAM Journal on Computing | 1976-01-01 | Paper |
Storage requirements for deterministic polynomial time recognizable languages
Journal of Computer and System Sciences | 1976-01-01 | Paper |
| scientific article; zbMATH DE number 3566230 (Why is no real title available?) | 1975-01-01 | Paper |
| scientific article; zbMATH DE number 3557241 (Why is no real title available?) | 1975-01-01 | Paper |
| scientific article; zbMATH DE number 3560698 (Why is no real title available?) | 1975-01-01 | Paper |
| scientific article; zbMATH DE number 3594622 (Why is no real title available?) | 1975-01-01 | Paper |
An observation on time-storage trade off
Journal of Computer and System Sciences | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3583767 (Why is no real title available?) | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3453572 (Why is no real title available?) | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3640911 (Why is no real title available?) | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3596151 (Why is no real title available?) | 1974-01-01 | Paper |
Time bounded random access machines
Journal of Computer and System Sciences | 1973-01-01 | Paper |
A hierarchy for nondeterministic time complexity
Journal of Computer and System Sciences | 1973-01-01 | Paper |
| scientific article; zbMATH DE number 3478425 (Why is no real title available?) | 1973-01-01 | Paper |
| scientific article; zbMATH DE number 3562523 (Why is no real title available?) | 1972-01-01 | Paper |
| scientific article; zbMATH DE number 3557235 (Why is no real title available?) | 1972-01-01 | Paper |
| scientific article; zbMATH DE number 3403734 (Why is no real title available?) | 1972-01-01 | Paper |
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
Journal of the ACM | 1971-01-01 | Paper |
| The complexity of theorem-proving procedures | 1971-01-01 | Paper |
| scientific article; zbMATH DE number 3365225 (Why is no real title available?) | 1971-01-01 | Paper |
| On the Minimum Computation Time of Functions | 1969-01-01 | Paper |
The Solvability of the Derivability Problem for One-Normal Systems
Journal of the ACM | 1966-01-01 | Paper |
Characterizations of ordinal numbers in set theory
Mathematische Annalen | 1966-01-01 | Paper |
