Sudhir K. Jha

dblp:10/984 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
0since 2021 · last 1995
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 100%

Topics — the 3 heaviest of 3, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › structural complexity
complexity class separation
0.011995
Defying Upward and Downward Separation · Inf. Comput. 1995
Computational complexity
relativization
0.011995
Defying Upward and Downward Separation · Inf. Comput. 1995
Computational complexity › structural complexity
sparse sets
0.011995
Defying Upward and Downward Separation · Inf. Comput. 1995
YearPublicationVenuePosition
1995 Defying Upward and Downward Separation
abstract
"Downward separation" results show that when small classes collapse, larger ones also collapse. For example, Stockmeyer proved that if P=NP, then the polynomial hierarchy collapses to P, and this result itself holds in every relativized world. In contrast, we construct a relativized world in which the exponential-time limited nondeterminism hierarchy does not display such behavior: its tower levels collapse yet its upper levels separate. "Upward separation" results typically show that polynomial-time classes differ on sparse or tally sets if and only if their exponential analogs differ. For example, Hartmanis, Immerman, and Sewelson proved that NP-P contains sparse sets if and only if E ≠ NE, and this result itself holds in every relativized world. In contrast, we construct relativized worlds in which probabilistic classes do not display upward separation, e.g., a world A in which BPPA-PA contains sparse sets even though BPEA = EA. We also construct a relativized world B in which NPB has PB-immune sparse sets yet NEB is not EB-immune. On the other hand, we provide a structural sufficient condition for upward separation.
Lane A. Hemaspaandra, Sudhir K. Jha
Inf. Comput.2
1993 Defying Upward and Downward Separation
Lane A. Hemaspaandra, Sudhir K. Jha
STACS2