Author pages are created from data sourced from our academic publisher partnerships and public sources.

Publications Influence

Share This Author

A complexity theory for feasible closure properties

- M. Ogiwara, L. Hemachandra
- Mathematics
- 1 June 1993

The study of the complexity of sets encompasses two complementary aims: (1) establishing—usually via explicit construction of algorithms-that sets are feasible, and (2) studying the relative… Expand

The strong exponential hierarchy collapses

- L. Hemachandra
- Mathematics
- STOC
- 1 January 1987

The polynomial hierarchy, composed of the levels P, NP, PNP, NPNP, etc., plays a central role in classifying the complexity of feasible computations. It is not known whether the polynomial hierarchy… Expand

Collapsing degrees via strong computation

- L. Hemachandra, Albrecht Hoeno
- Mathematics
- 1 June 1993

An equivalence class with respect to a given type of reduction is called a degree. It is natural to expect that using more flexible reduction types will increase the size of a degree. When using more… Expand

The strong exponential hierarchy collapses

- L. Hemachandra
- Mathematics
- 1 December 1989

Abstract Composed of the levels E (i.e., ∪ c DTIME[2 cn ]), NE, P NE , NP NE , etc., the strong exponential hierarchy is an exponential-time analogue of the polynomial-time hierarchy. This paper… Expand

On the Power of Probabilistic Polynomial Time:PNP[log] ⊆ PP

- L. Hemachandra, G. Wechsung
- Computer Science
- 1988

We show that every set in the 0~ level of the polynomial hierarchy-every set polynomial time truth-table reducible to SAT~is accepted by a probabilistic polynomial-time Turing machine: pNP[log] ~… Expand

Exact Counting is as Easy as Approximate Counting

- Jin-Yi Cai, L. Hemachandra
- Computer Science
- 1 June 1986

Promises and fault-tolerant database access

- Jin-Yi Cai, L. Hemachandra, J. Vyskoc
- Computer Science
- 1 December 1993

TLDR

Counting in structural complexity theory

- L. Hemachandra
- Mathematics
- 1 June 1987

Structural complexity theory is the study of the form and meaning of computational complexity classes. Complexity classes--P, NP, ProbabilisticP, PSPACE, etc.--are formalizations of computational… Expand

Structure of Complexity Classes: Separations, Collapses, and Completeness

- L. Hemachandra
- Mathematics
- 29 August 1988

During the last few years, unprecedented progress has been made in structural complexity theory; class inclusions and relativized separations were discovered, and hierarchies collapsed. We survey… Expand

A complexity theory for feasible closure properties

- M. Ogiwara, L. Hemachandra
- Computer Science
- [] Proceedings of the Sixth Annual Structure in…
- 30 June 1991

TLDR

...

1

2

3

...