Lane A. Hemachandra

65 papers A* 7A 3B 7C 1Misc 1Journal 28Unranked 17
YearRankTypeTitle / Venue / Authors
1993 J jnl
A Complexity Theory for Feasible Closure Properties.
J. Comput. Syst. Sci.
Mitsunori Ogiwara, Lane A. Hemachandra
1993 J jnl
Collapsing Degrees via Strong Computation.
J. Comput. Syst. Sci.
Lane A. Hemachandra, Albrecht Hoene
1993 A conf
Defying Upward and Downward Separation.
STACS
Lane A. Hemachandra, Sudhir K. Jha
1993 B conf
Easity Checked Self-Reducibility (Extended Abstract).
FCT
Lane A. Hemachandra, Riccardo Silvestri
1993 A* conf
Fault-Tolerance and Complexity (Extended Abstract).
ICALP
Lane A. Hemachandra
1993 — ch.
Is #P Closed Under Subtraction?
Current Trends in Theoretical Computer Science
Lane A. Hemachandra, Mitsunori Ogiwara
1993 J jnl
On Checking Versus Evaluation of Multiple Queries
Inf. Comput.
William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene
1993 C conf
Selectivity.
ICCI
Lane A. Hemachandra, Albrecht Hoene, Mitsunori Ogiwara, Alan L. Selman, Thomas Thierauf, Jie Wang
1993 J jnl
Using Inductive Counting to Simulate Nondeterministic Computation
Inf. Comput.
Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes
1992 Misc conf
Banishing Robust Turing Completeness.
LFCS
Lane A. Hemachandra, Sanjay Jain, Nikolai K. Vereshchagin
1992 — conf
How Hard Are Sparse Sets?
SCT
Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1992 J jnl
Is #P Closed under Substraction?
Bull. EATCS
Lane A. Hemachandra, Mitsunori Ogiwara
1992 J jnl
Lower Bounds for the Low Hierarchy.
J. ACM
Eric Allender, Lane A. Hemachandra
1992 J jnl
Polynomial-Time Compression.
Comput. Complex.
Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen
1992 B conf
Promise Problems and Access to Unambiguous Computation.
MFCS
Jin-Yi Cai, Lane A. Hemachandra, Jozef Vyskoc
1992 — conf
Promise Problems and Guarded Access to Unambiguous Computation.
Complexity Theory: Current Research
Jin-Yi Cai, Lane A. Hemachandra, Jozef Vyskoc
1992 — conf
Reductions to Sets of Low Information Content.
Complexity Theory: Current Research
Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf
1992 A* conf
Reductions to Sets of Low Information Content.
ICALP
Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf
1992 J jnl
Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput.
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1992 J jnl
Separating Complexity Classes With Tally Oracles.
Theor. Comput. Sci.
Lane A. Hemachandra, Roy S. Rubinstein
1992 J jnl
Simultaneous Strong Separations of Probabilistic and Unambiguous Complexity Classes.
Math. Syst. Theory
David Eppstein, Lane A. Hemachandra, James Tisdall, Bülent Yener
1991 — conf
A Complexity Theory for Feasible Closure Properties.
SCT
Mitsunori Ogiwara, Lane A. Hemachandra
1991 J jnl
A Note on Enumarative Counting.
Inf. Process. Lett.
Jin-Yi Cai, Lane A. Hemachandra
1991 A* conf
Collapsing Degrees via Strong Computation (Extended Abstract).
ICALP
Lane A. Hemachandra, Albrecht Hoene
1991 J jnl
Kolmogorov Characterizations of Complexity Classes.
Theor. Comput. Sci.
Lane A. Hemachandra, Gerd Wechsung
1991 J jnl
Near-Testable Sets.
SIAM J. Comput.
Judy Goldsmith, Lane A. Hemachandra, Deborah Joseph, Paul Young
1991 J jnl
On Sets Polynomially Enumerable by Iteration.
Theor. Comput. Sci.
Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes, Paul Young
1991 J jnl
On Sets with Efficient Implicit Membership Tests.
SIAM J. Comput.
Lane A. Hemachandra, Albrecht Hoene
1991 B conf
On the Complexity of Graph Reconstruction.
FCT
Dieter Kratsch, Lane A. Hemachandra
1991 J jnl
On the Limitations of Locally Robust Positive Reductions.
Int. J. Found. Comput. Sci.
Lane A. Hemachandra, Sanjay Jain
1991 — conf
On the Structure and Complexity of Infinite Sets with Minimal Perfect Hash Functions.
FSTTCS
Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen
1991 J jnl
One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Theor. Comput. Sci.
Juris Hartmanis, Lane A. Hemachandra
1991 J jnl
Probabilistic Polynomial Time is Closed under Parity Reductions.
Inf. Process. Lett.
Richard Beigel, Lane A. Hemachandra, Gerd Wechsung
1991 — conf
Relating Equivalence and Reducibility to Sparse Sets.
SCT
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
1990 — conf
A Note on Relativizing Complexity Classes with Tally Oracles.
SCT
Lane A. Hemachandra, Roy S. Rubinstein
1990 — conf
Algorithms from Complexity Theory: Polynominal-Time Operations for Complex Sets.
SIGAL International Symposium on Algorithms
Lane A. Hemachandra
1990 B conf
On Checking Versus Evaluation of Multiple Queries.
MFCS
William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene
1990 — conf
On Sets with Efficient Implicit Membership Tests.
SCT
Lane A. Hemachandra, Albrecht Hoene
1990 J jnl
On the Complexity of Ranking.
J. Comput. Syst. Sci.
Lane A. Hemachandra, Steven Rudich
1990 J jnl
On the Power of Parity Polynomial Time.
Math. Syst. Theory
Jin-Yi Cai, Lane A. Hemachandra
1990 J jnl
Robust Machines Accept Easy Sets.
Theor. Comput. Sci.
Juris Hartmanis, Lane A. Hemachandra
1990 B conf
Using Inductive Counting to Simulate Nondeterministic Computation.
MFCS
Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes
1989 J jnl
Enumerative Counting Is Hard
Inf. Comput.
Jin-Yi Cai, Lane A. Hemachandra
1989 A* conf
Lower Bounds for the Low Hierarchy (Extended Abstract).
ICALP
Eric Allender, Lane A. Hemachandra
1989 — conf
On the Limitations of Locally Robust Positive Reductions.
FSTTCS
Lane A. Hemachandra, Sanjay Jain
1989 A conf
On the Power of Parity Polynomial Time.
STACS
Jin-Yi Cai, Lane A. Hemachandra
1989 — conf
On the Power of Probabilistic Polynomial Time: P
SCT
Richard Beigel, Lane A. Hemachandra, Gerd Wechsung
1989 B conf
Polynomial-Time Functions Generate SAT: On P-Splinters.
MFCS
Lane A. Hemachandra, Albrecht Hoene, Dirk Siefkes
1989 J jnl
The Boolean Hierarchy II: Applications.
SIAM J. Comput.
Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
1989 J jnl
The Strong Exponential Hierarchy Collapses.
J. Comput. Syst. Sci.
Lane A. Hemachandra
1989 — conf
Using Randomness to Characterize the Complexity of Computation.
IFIP Congress
Lane A. Hemachandra, Gerd Wechsung
1988 J jnl
Complexity Classes without Machines: On Complete Languages for UP.
Theor. Comput. Sci.
Juris Hartmanis, Lane A. Hemachandra
1988 — conf
Enumerative counting is hard.
SCT
Jin-Yi Cai, Lane A. Hemachandra
1988 A* conf
On Generating Solved Instances of Computational Problems.
CRYPTO
Martín Abadi, Eric Allender, Andrei Z. Broder, Joan Feigenbaum, Lane A. Hemachandra
1988 J jnl
On Sparse Oracles Separating Feasible Complexity Classes.
Inf. Process. Lett.
Juris Hartmanis, Lane A. Hemachandra
1988 B conf
Structure of Complexity Classes: Separations, Collapses, and Completeness.
MFCS
Lane A. Hemachandra
1988 J jnl
The Boolean Hierarchy I: Structural Properties.
SIAM J. Comput.
Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
1987 — conf
On ranking.
SCT
Lane A. Hemachandra
1987 — conf
One-way functions, robustness, and the non-isomorphism of NP-complete sets.
SCT
Juris Hartmanis, Lane A. Hemachandra
1987 A* conf
The Strong Exponential Hierarchy Collapses
STOC
Lane A. Hemachandra
1987 — conf
The strong exponential hierarchy collapses.
SCT
Lane A. Hemachandra
1987 J jnl
Using simulated annealing to design good codes.
IEEE Trans. Inf. Theory
Abbas A. El Gamal, Lane A. Hemachandra, Itzhak Shperling, Victor K.-W. Wei
1986 A* conf
Complexity Classes Without Machines: On Complete Languages for UP.
ICALP
Juris Hartmanis, Lane A. Hemachandra
1986 A conf
On Sparse Oracles Separating Feasible Complexity Classes.
STACS
Juris Hartmanis, Lane A. Hemachandra
1986 — conf
The Boolean Hierarchy: Hardware over NP.
SCT
Jin-Yi Cai, Lane A. Hemachandra