Lane A. Hemachandra

Publication Activity (10 Years)

Years Active: 1986-1993
Publications (10 Years): 0

Publications

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