VLDB 2026 Research / reviewers in the wild / expert
Sudhir K. Jha
dblp:10/984
· DBLP profile ↗
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
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › structural complexity
complexity class separation |
0.0 | 1 | 1995 | Defying Upward and Downward Separation · Inf. Comput. 1995 |
Computational complexity
relativization |
0.0 | 1 | 1995 | Defying Upward and Downward Separation · Inf. Comput. 1995 |
Computational complexity › structural complexity
sparse sets |
0.0 | 1 | 1995 | Defying Upward and Downward Separation · Inf. Comput. 1995 |
| Year | Publication | Venue | Position |
|---|---|---|---|
| 1995 | Defying Upward and Downward Separationabstract"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 |
STACS | 2 |