| Publication | Date of Publication | Type |
|---|
| Magic functions | 2026-05-06 | Paper |
Compactly encoding unstructured inputs with differential compression
Journal of the ACM | 2015-12-07 | Paper |
Cosmological lower bound on the circuit complexity of a small problem in logic
Journal of the ACM | 2015-12-07 | Paper |
Magic functions
Journal of the ACM | 2015-11-12 | Paper |
What can be computed locally?
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
2-round zero knowledge and proof auditors
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
An Architecture for Provably Secure Computation
LATIN 2006: Theoretical Informatics | 2008-09-18 | Paper |
Links between complexity theory and constrained block coding
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
| scientific article; zbMATH DE number 1775416 (Why is no real title available?) | 2002-08-01 | Paper |
The closure of monadic NP
Journal of Computer and System Sciences | 2000-08-27 | Paper |
| scientific article; zbMATH DE number 1256670 (Why is no real title available?) | 1999-04-22 | Paper |
The complexity of PDL with interleaving
Theoretical Computer Science | 1997-02-27 | Paper |
What Can be Computed Locally?
SIAM Journal on Computing | 1996-09-15 | Paper |
Efficiently extendible mappings for balanced data distribution
Algorithmica | 1996-08-12 | Paper |
On monadic NP vs monadic co-NP
Information and Computation | 1995-09-17 | Paper |
Finite state verifiers I
Journal of the ACM | 1994-11-13 | Paper |
Finite state verifiers II
Journal of the ACM | 1994-11-13 | Paper |
Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
Theoretical Computer Science | 1994-08-29 | Paper |
Bounds on the time to reach agreement in the presence of timing uncertainty
Journal of the ACM | 1994-06-29 | Paper |
| scientific article; zbMATH DE number 218387 (Why is no real title available?) | 1993-06-29 | Paper |
| scientific article; zbMATH DE number 4180787 (Why is no real title available?) | 1990-01-01 | Paper |
Flipping Persuasively in Constant Time
SIAM Journal on Computing | 1990-01-01 | Paper |
A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
SIAM Journal on Computing | 1990-01-01 | Paper |
The Distributed Firing Squad Problem
SIAM Journal on Computing | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4120160 (Why is no real title available?) | 1989-01-01 | Paper |
Parallel Algorithms for Term Matching
SIAM Journal on Computing | 1988-01-01 | Paper |
On the minimal synchronism needed for distributed consensus
Journal of the ACM | 1987-01-01 | Paper |
Classifying the computational complexity of problems
Journal of Symbolic Logic | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4049127 (Why is no real title available?) | 1986-01-01 | Paper |
Bounded-depth, polynomial-size circuits for symmetric functions
Theoretical Computer Science | 1985-01-01 | Paper |
Pseudorandom number generation and space complexity
Information and Control | 1985-01-01 | Paper |
On Approximation Algorithms for # P
SIAM Journal on Computing | 1985-01-01 | Paper |
Simulation of Parallel Random Access Machines by Circuits
SIAM Journal on Computing | 1984-01-01 | Paper |
Constant Depth Reducibility
SIAM Journal on Computing | 1984-01-01 | Paper |
Alternating Pushdown and Stack Automata
SIAM Journal on Computing | 1984-01-01 | Paper |
Alternation bounded auxiliary pushdown automata
Information and Control | 1984-01-01 | Paper |
Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
Journal of the ACM | 1984-01-01 | Paper |
Optimal orientations of cells in slicing floorplan designs
Information and Control | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3876586 (Why is no real title available?) | 1983-01-01 | Paper |
NP-completeness of some generalizations of the maximum matching problem
Information Processing Letters | 1982-01-01 | Paper |
Alternation
Journal of the ACM | 1981-01-01 | Paper |
Uniform data encodings
Theoretical Computer Science | 1980-01-01 | Paper |
| scientific article; zbMATH DE number 3735142 (Why is no real title available?) | 1980-01-01 | Paper |
Provably Difficult Combinatorial Games
SIAM Journal on Computing | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3695102 (Why is no real title available?) | 1979-01-01 | Paper |
Evaluation of polynomials with super-preconditioning
Journal of Computer and System Sciences | 1978-01-01 | Paper |
The polynomial-time hierarchy
Theoretical Computer Science | 1977-01-01 | Paper |
Storage schemes for boundedly extendible arrays
Acta Informatica | 1977-01-01 | Paper |
Hashing Schemes for Extendible Arrays
Journal of the ACM | 1977-01-01 | Paper |
On the combinational complexity of certain symmetric Boolean functions
Mathematical Systems Theory | 1977-01-01 | Paper |
Some simplified NP-complete graph problems
Theoretical Computer Science | 1976-01-01 | Paper |
A characterization of the power of vector machines
Journal of Computer and System Sciences | 1976-01-01 | Paper |
| scientific article; zbMATH DE number 3591381 (Why is no real title available?) | 1976-01-01 | Paper |
| scientific article; zbMATH DE number 3557205 (Why is no real title available?) | 1975-01-01 | Paper |
Fast on-line integer multiplication
Journal of Computer and System Sciences | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3592964 (Why is no real title available?) | 1974-01-01 | Paper |
| scientific article; zbMATH DE number 3560737 (Why is no real title available?) | 1973-01-01 | Paper |
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
SIAM Journal on Computing | 1973-01-01 | Paper |
Fast on-line integer multiplication
Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73 | 1973-01-01 | Paper |
